java - Java-无法使ProjectEuler 3大量工作(600851475143)

解析度：
  事实证明，代码本身“可能没有错”。这只是效率低下。如果我的数学正确，那么如果我让它继续运行，它将在2011年10月14日星期五之前完成。我会告诉您！


警告：如果您尝试解决欧拉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的较大值不起作用？



密切相关（但不是欺骗）："Integer number too large" error message for 600851475143

最佳答案

代码很慢；它可能是正确的，但是会运行不可接受的大量时间（大约是输入n^2/2的最内层循环的n迭代）。尝试计算从最小到最大的因子，并在找到因子时将其分解，例如：

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

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