1

解决方案：
事实证明，代码本身（可能）“没有错”；它只是效率低下。如果我的数学是正确的，如果我让它继续运行，它将在 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 的“整数太大”错误消息

4

4 回答 4

5

代码很慢；它可能是正确的，但会运行不可接受的大量时间（关于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);

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

于 2011-02-18T14:49:04.900 回答
2

几乎所有的 Project Euler 问题都可以使用 64 位的有符号数据类型来解决（除了像问题 13 那样有目的地尝试变大的问题）。

如果您要使用素数（嘿，它的项目 Euler，您将使用素数），请先启动并实施Eratosthenes筛、阿特金筛或 Sundaram 筛。

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

于 2011-02-18T15:18:34.640 回答
0

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

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

对于非常大的数字，使用筛子进行实验确实比强制使用它更快，特别是如果您正在测试大量数字的素数。请注意，您不会在算法上低效地实现筛子（例如，从列表中添加或删除素数将花费您额外的 O(n)）。

于 2011-02-18T14:51:20.977 回答
0

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

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 毫秒。

于 2014-11-09T19:44:32.177 回答