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

请注意,即使没有明确检查素数,此代码也只会添加素数因子.