Java - 无法使ProjectEuler 3适用于非常大的数字（600851475143） [英] Java - Can't make ProjectEuler 3 Work for a very big number (600851475143)

问题描述

解决方案：

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

Resolution:
It turns out there is (probably) "nothing wrong" with the code itself; it is just inefficient. If my math is correct, If I leave it running it will be done by Friday, October 14, 2011. I'll let you know!

警告：如果你想解决Project Euler＃3，这可能包含剧透。

Warning: this may contain spoilers if you are trying to solve Project Euler #3.

问题是：

13195的主要因素是5,7,13和29.

The prime factors of 13195 are 5, 7, 13 and 29.

什么是数字600851475143的最大素数因子？

What is the largest prime factor of the number 600851475143 ?

这是我尝试解决它的问题。我只是从Java和编程开始，我知道这不是最好或最有效的解决方案。

Here's my attempt to solve it. I'm just starting with Java and programming in general, and I know this isn't the nicest or most efficient solution.

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

当数字设置为 13195 ，程序运行正常，产生结果 [29,13,7,5] 。

When number is set to 13195, the program works just fine, producing the result [29, 13, 7, 5] as it should.

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

Why doesn't this work for larger values of number?

密切相关（但不是欺骗）：整数也是大"错误消息600851475143

Closely related (but not dupe): "Integer number too large" error message for 600851475143

推荐答案

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

The code is very slow; it is probably correct but will run for an unacceptably large amount of time (about n^2/2 iterations of the innermost loop for an input n). Try computing the factors from smallest to largest, and divide out each factor as you find it, such as:

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

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

Note that this code will only add prime factors, even without an explicit check for primality.

这篇关于Java - 无法使ProjectEuler 3适用于非常大的数字（600851475143）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！