如何有效地计算长数的最大质因数？

Question

我试图创建一个 Java 程序来计算任何长数的最大质因数（在本例中为 600851475143）。当我尝试运行它时，程序会无限期地编译，而不会产生警告或结果。我知道可能有 easier/more 直接的方法来解决这个问题，但我很好奇这个方法似乎不起作用的原因。我不认为逻辑本身是错误的，一个可能的错误可能是我使用了长变量（我以前没有经常使用它们）。

我已经声明了一些变量，只要允许它们 space 增加到 'long' 大小


    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);
    }
}

Answer 1

看起来你的程序编译得很好，但陷入了无限（或非常长的）循环如果您将 System.out.println("program started"); 放在 main 方法的开头，您可能会看到它显示出来。

此外，如果您降低 long num，您将看到您的方法完成。

编辑：您有两个嵌套的 for 循环。第一个执行 num/2 次，另一个执行 (num/2)/2.

如果我没记错的话，这意味着它将循环 (num^2)/8 次。 long num = 600851475143L; 很多。因此，您的应用程序被卡住迭代超过 4.51 × 10^22 次

Answer 2

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

下面给出了一种有效的方法：

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

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

变量flag已在外循环外声明，这意味着它一旦变成true就永远不会重置为false。
您需要检查 i % j == 0，而不是检查 i / j == 0。
您应该 break 内循环尽快 i % j == 0。
此外，largestPrimeFactor 的检查需要从内循环移到外循环。

顺便说一下，你的素数测试也不是很有效。不用检查数字的一半，检查数字的平方根就足够了。查看 https://en.wikipedia.org/wiki/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;
}

Answer 3

查找因素是一项计算密集型操作。

因此，计算机在进行此类计算时需要很长时间是正常的。

计算的运行时间可以通过减少迭代次数来减少。

例如，可以避免对所有大于 2 的偶数进行迭代，因为它们不可能是质数。

这是 link 在 Github 上找到的工作代码：

https://gist.github.com/joseporiol/8559440

Answer 4

这并没有具体解决算法中的所有问题，但它可以提供一些指导。您给定的数字应该很快因式分解，因为它的素因数在数量级上非常接近。这使得它更快，因为随着其他因素的发现，目标数量减少得更快。

考虑以下示例。第一个值是你的，下一个要大得多，第三个是最小的（最后一个是有原因的）。

输出如下所示：事实上，这是您的号码。 adding 部分是一个新因子，continuing 部分是除以该因子后剩下的部分，需要进一步分解。括号中的值是给定数字的找到的因子。

Checking: 600851475143
Adding 71, continuing with 8462696833
Adding 839, continuing with 10086647
Adding 1471, continuing with 6857
Adding 6857, continuing with 1
[71, 839, 1471, 6857]

结果是前两个数字的因数很快。第三个需要很长时间。那是因为它是质数，使用这种方法我必须生成所有不超过该值的质数来验证这一事实。因此，大小不是唯一的因素（双关语），而是主要因素的相对大小。

这是测试程序。

        for (long test : new long[] { 600851475143L,
                14385829455476874L,  300851475157L }) {
            System.out.println();
            System.out.println("Checking: " + test);
            List<Long> factors = findFactors(test);
            System.out.println(factors);
        }
    
    static private int lastReturnedPrimeIdx = 0;
    static private List<Long> primes = new ArrayList<>(
            List.of(2L, 3L));
    
   // find all prime factors in a supplied number.
    public static List<Long> findFactors(long n) {
        List<Long> factors = new ArrayList<>();
        lastReturnedPrimeIdx = 0;
        while (n > 1) {
            long p = nextPrime();
            while (n % p == 0) {
                factors.add(p);
                n /= p;
                System.out.println("Adding " + p
                        + ", continuing with " + n);
            }
        }
        return factors;
    }

    // Get the next prime. This memoizes the primes as they are computed.
    // Future tests on the same run can thus take advantage of the cached values.
    // Prime are computed in bulk.
    private static long nextPrime() {
        if (lastReturnedPrimeIdx < primes.size()) {
            return primes.get(lastReturnedPrimeIdx++);
        }

        // start where the it left off last time.
        long candidate = primes
                .get(lastReturnedPrimeIdx - 1);
        long max = primes.size() + 1_000; // generate 1000 more primes.

        outer:
        while (primes.size() < max) {
            candidate += 2;
            long bound = (long)Math.sqrt(candidate);
            for (int i = 0; i < primes.size(); i++) {
                long p = primes.get(i);
                if (candidate % p == 0 ) {
                    continue outer;
                }
                if (p > bound) {
                    break;
                }
                
            }
            primes.add(candidate);
        }
        return (primes.get(lastReturnedPrimeIdx++));
    }
}

最后一点：我建议您通过以下方式计算未来的候选素数：

仅将候选项除以已找到的素数。
只检查 2 之后的奇数候选人。
只检查 primes 到候选人的平方根。

另一种选择是 Sieve of Eratosthenes

如何有效地计算长数的最大质因数？

How to calculate the largest prime factor of a long number efficiently?

java

primes

prime-factoring

long-integer