如何有效地计算一个整数的最大素数? [英] How to calculate the largest prime factor of a long number efficiently?

问题描述

我试图创建一个Java程序来计算任何长数的最大素数(在这种情况下为600851475143).当我尝试运行它时，该程序将无限期编译，而不会产生警告或结果.我知道可能有更简单/更直接的方法来解决此问题，但是我很好奇为什么这个方法似乎行不通.我不认为逻辑本身是错误的，可能的错误可能是我使用了长变量(我以前从未经常使用过它们).

I tried to create a Java program to calculate the largest prime factor of any long number (in this case 600851475143). When I try to run it, the program compiles indefinitely, without producing warnings or a result. I understand there might be easier/more straightforward ways to solve this problem, but I'm curious on the reason why this one doesn't seem to work. I don't think the logic itself is wrong, a possible error might be my use of long variables (I have not used them often before).

我已经声明了一些变量，以允许它们将空间增加到长"大小

I have declared some variables as long to allow them the space to be increased to a 'long' size

    public class LargestPrimeFactor {
    public static void main(String []args){

        long num = 600851475143L;
        long largestPrimeFactor = 0L;
        boolean flag = false;

        //Find all factors of num
        for (long i = 2L; i <= num/2; i++){

            //If a number i is a factor of num
            if((num % i) == 0){

                //Find if the factor i is a prime number (only divisible by 1 and by itself)
                //by checking whether dividing it by any number results in an integer
                for (long j = 2L; j <= i/2; j++){

                    if (i/j == 0){

                        flag = true;
                    }
                    if (!flag){

                        if (i > largestPrimeFactor){

                            largestPrimeFactor = i;
                        }
                    }
                }
            }
        }
        System.out.print(largestPrimeFactor);
    }
}

推荐答案

当然，您的代码不会无限运行.只是您的代码效率不高，因此打印结果花费的时间太长.如果您使用较小的数字进行测试或使用有效的代码，则将得到结果.

Definitely, your code won't run infinitely. It's just that your code is not efficient and therefore it's taking too long to print the result. If you test with a smaller number or use an efficient code, you will get the result.

下面给出的是一种有效的方法:

Given below is an efficient way of doing it:

public class Main {
    public static void main(String[] args) {
        long num = 600851475143L;
        long divisor = 2, largestPrimeFactor;
        while (num != 0) {
            if (num % divisor != 0) {
                divisor++;
            } else {
                largestPrimeFactor = num;
                num /= divisor;
                if (num == 1) {
                    System.out.println("The largest prime factor: " + largestPrimeFactor);
                    break;
                }
            }
        }
    }
}

输出:

The largest prime factor: 6857

您的代码还存在以下逻辑问题:

Your code also has the following logical problems:

1. 变量 flag 已在外部循环外声明，这意味着一旦它变为 true ，就永远不会重置为 false .
2. 您无需检查 i/j == 0 ，而是需要检查 i％j == 0 .
3. 一旦 i％j == 0 ，您应该中断内循环.
4. 此外，对 largestPrimeFactor 的检查也需要从内部循环移动到外部循环.

1. The variable, flag has been declared outside the outer loop which means that it will never be reset to false once it will become true.
2. Instead of checking i / j == 0, you need to check i % j == 0.
3. You should break the inner loop as soon as i % j == 0.
4. Also, the check for largestPrimeFactor needs to be moved from the inner loop to the outer one.

顺便说一句，对素数的测试也不是很有效.而不是最多检查数字的一半，而最多检查数字的平方根就足够了.有关更多详细信息，请检查 https://en.wikipedia.org/wiki/Primality_test .下面给出的是用于素数测试的有效代码:

By the way, your test for primality is also not efficient. Instead of checking up to the half of the number, checking up to the square root of the number is sufficient. Check https://en.wikipedia.org/wiki/Primality_test for more details. Given below is an efficient code for primality test:

static boolean isPrime(int number) {
    boolean prime = true;
    if (number == 0 || number == 1 || number == -1)
        return false;
    for (int i = 2; i <= Math.sqrt(number); i++) {
        if (number % i == 0) {
            prime = false;
            break;
        }
    }
    return prime;
}

这篇关于如何有效地计算一个整数的最大素数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！