java - 欧拉计划 #3 - 解决方案永远运行

Question

第一次遇到这种问题。感觉它永远不会结束。

我的方法:

import java.util.TreeSet;

public class Euler3 {
    public static void main(String[] args) {
        long result = 0;
        long startTime = System.nanoTime();

        long numberGiven = 600851475143L;
        TreeSet<Long> nums = new TreeSet<>();

        for (long i = 2L; i < numberGiven; i++) {
            if (numberGiven % i == 0 && isPrime(i)) {
                nums.add(i);
            }
        }

        result = nums.last();   

        System.out.print("Result: " + result +
            ".\nTime used for calculation in nanoseconds: " +
            (System.nanoTime() - startTime) + ".");
    }

    public static boolean isPrime(long n) {
        if (n <= 3) {
            return n == 1 ? false : true;
        } else if (n % 2 == 0 || n % 3 == 0) {
            return false;
        } else {
            for (int i = 5; i * i <= n; i += 6) {
                if (n % i == 0 || n % (i + 2) == 0) {
                    return false;
                }
            }
        return true;
        }
    }
}

当然，这适用于较小的数字，但可能正如预期的那样，对超过 6000 亿的数字似乎并不有效。我想知道，但没有给出答案:

1. 我可以采用一些明显的改变来减少运行时间/检查是否必要？

2. 虽然在这里显然不能有效地工作，但这种方法是否则可以接受或者发布此挑战的人，即使人数较少，也在寻找不同的东西吗？

3. 我第一次尝试使用整数并遇到了一个与溢出相关的错误，是否有类似的事情发生在引擎盖下实际上会阻止它终止？

Answer 1

对于要检查的每个 数是否是因数，您正在执行一个内部 循环以确定它是否是素数。这意味着您的算法正在有效地执行 n * m 操作。

您可以改为使用以下数学“技巧”，我认为它与 UNIX factor 程序使用的相同。

由于每个大于 1 的数字要么是素数，要么是一组素数的唯一乘积(集合中可能有重复项)，我们可以开始将数字除以第一个素数的二(实际上是减少了这个过程中的数字)直到那不再可能(即，它变得奇怪)。到那时，减少的数字将不会有两个或任何两个的倍数作为一个因素。

然后我们通过连续除以三来做同样的事情，直到不再可能为止。

现在您可能认为这可能很麻烦，但是因为您已经去掉了所有“二”因数，所以该数字可能不能是四的倍数(或任何其他偶数那件事)。所以我们检测到它并移动到下一个五的除数并开始除以它。

所以除法运算只对质因数进行，大大加快了速度。此外，一旦除数超过(减少的)数字的平方根，就没有更多的因素了，所以我们退出。在那种情况下，减少的数字给了我们最终的(因此是最高的)质因数。

例如，考虑数字 924:

Number  Divisor  Result
------  -------  ------
   924        2*    462
   462        2*    231
   231        2     not divisible, go to 3
   231        3*     77
    77        3     not divisible, go to 4
    77        4     not divisible, go to 5
    77        5     not divisible, go to 6
    77        6     not divisible, go to 7
    77        7*    11
    11*       7     stop since 7 * 7 > 11

所以 924 的质因数是 {2, 2, 3, 7, 11}。

---

现在我强烈建议您在阅读下文之前自行尝试该算法，因为欧拉的整个要点都是为了测试您自己的能力。我只是提供完整性的解决方案:

public class Test
{
    public static void main(String[] args) {
        long startTime = System.nanoTime();

        long number = 600851475143L;

        // Start with a divisor of two,
        // continue until over sqrt(number).

        long divisor = 2L;
        while (divisor * divisor <= number) {
            if ((number % divisor) == 0) {
                // If factor, output then reduce number.

                System.out.println(divisor);
                number = number / divisor;
            } else {
                // Otherwise, move to next divisor.

                divisor++;
            }
        }

        // Final number is final divisor.

        System.out.println(number);

        System.out.print("Time used for calculation in nanoseconds: " +
                (System.nanoTime() - startTime) + ".");
    }
}

这会在大约五 千分之一 秒内给出四个质因数(无论如何在我的盒子上):

71
839
1471
6857
Time used for calculation in nanoseconds: 458826.