Java - 无法使 ProjectEuler 3 处理非常大的数字 (600851475143)

Question

分辨率：
事实证明，代码本身（可能）“没有任何问题”；它只是效率低下。如果我的数学正确，如果我继续运行，它将在 2011 年 10 月 14 日星期五之前完成。我会让你知道的！

警告：如果您尝试解决 Project Euler #3，这可能包含剧透。

问题是这样说的：

13195 的质因数是 5、7、13 和 29。

数字 600851475143 的最大质因数是多少？

这是我尝试解决它的方法。我刚刚开始学习 Java 和一般编程，我知道这不是最好或最有效的解决方案。

import java.util.ArrayList;

public class Improved {
    public static void main(String[] args) {
        long number = 600851475143L;
        // long number = 13195L;
        long check = number - 1;
        boolean prime = true;

        ArrayList<Number> allPrimes = new ArrayList<Number>();

        do {
            for (long i = check - 1; i > 2; i--) {
                if (check % i == 0) {
                    prime = false;
                }
            }

            if (prime == true && number % check == 0) {
                allPrimes.add(check);
            }

            prime = true;
            check--;
        } while (check > 2);

        System.out.println(allPrimes);
    }
}

当 number 设置为 13195 时，程序运行良好，生成应有的结果 [29, 13, 7, 5]。

为什么这不适用于较大的 number 值？

---

密切相关（但不是欺骗）：600851475143 的“整数太大”错误消息

Answer 1

代码非常慢；它可能是正确的，但会运行非常长的时间（对于输入n，大约是最内层循环的n^2/2次迭代）。尝试从小到大计算因子，并在找到每个因子时将其除掉，例如：

for (i = 2; i*i <= n; ++i) {
  if (n % i == 0) {
    allPrimes.add(i);
    while (n % i == 0) n /= i;
  }
}
if (n != 1) allPrimes.add(n);

请注意，即使没有显式检查素数，此代码也只会添加素因子。

Answer 2

几乎所有的欧拉计划问题都可以使用 64 位的有符号数据类型来解决（除了像问题 13 那样故意尝试变得更大的问题）。

如果您要使用素数（嘿，它的项目 Euler，您将使用素数）先行一步并实现 埃拉托斯特尼筛法、阿特金筛法，或
Sundaram 筛。

在许多问题中使用的一种数学技巧是通过计算目标的平方根来短路查找因子。任何大于平方的值都对应于小于平方的因子。

Answer 3

您还可以通过仅检查 2 到目标数字的平方根来加快速度。每个因子都是一对，一个在平方根上方，一个在平方根下方，因此当您找到一个因子时，您也会找到它的对。在素数测试的情况下，一旦找到任何因素，您就可以跳出循环。

另一种优化可能是在检查因子是否为质数之前找到它们。

对于非常大的数字，用筛子进行试验确实比暴力破解更快，特别是当您正在测试大量数字的素数时。只是要小心，不要做一些算法效率低下的事情来实现筛子（例如，从列表中添加或删除素数将花费额外的 O(n) 时间）。

Answer 4

另一种方法（不需要存储所有素数）：

private static boolean isOddPrime(long x) {
    /* because x is odd, the even factors can be skipped */
    for ( int i = 3 ; i*i <= x ; i+=2 ) {
        if ( x % i == 0 ) {
            return false;
        }               
    }
    return true;
}

public static void main(String[] args) {
    long nr = 600851475143L;
    long max = 1;
    for ( long i = 3; i <= nr ; i+=2 ) {
        if ( nr % i == 0 ) {
            nr/=i;
            if ( isOddPrime(i) ){
                max = i;
            }
        }   
    }
    System.out.println(max);
}

需要不到 1 毫秒。