欧拉计划 #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 亿的数字无效。我想知道，但不给出答案：

我可以采用一些明显的改变来减少运行 time/checks 有必要吗？
虽然这里显然没有效果，但是这个方法是不是否则可以接受或者发布此挑战的人，即使人数较少，也在寻找不同的东西吗？
我第一次尝试使用整数并遇到了与溢出相关的错误，是否有类似的事情发生在引擎盖下实际上会阻止它终止？

Answer 1

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

您可以改用以下数学公式 "trick"，我认为它与 UNIX factor 程序使用的相同。

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

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

现在您可能认为这可能很繁琐，但是因为您已经剔除了所有 'two' 因素，所以该数字不可能可能是四的倍数（或与此相关的任何其他偶数）。所以我们检测到它并移动到下一个五的除数并开始除以它。

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

例如，考虑数字 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}。

现在我建议你在看下面之前自己尝试一下这个算法，因为欧拉的整个 point 都是为了测试你的 own能力。我只是提供完整的解决方案：

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.

Answer 2

程序可以这么简单，运行不到一秒：

long val = 600851475143L;
long ans = 0;
for(long i = 2; i*i <= val; i++){
    if(val % i == 0){
       ans = i;
       while(val % i == 0)//This step will make sure that i is prime
           val /= i;
    }
}
if(val != 1){//If val is not 1, so val is a prime
   ans = val > ans ? val : ans;
}
System.out.println(ans);

答案是6857，正确答案:)

请注意，我们只检查 i*i 小于 val 的所有 i 值。

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

Project Euler #3 - Solution runs forever

java

algorithm

primes