使欧拉计划的解决方案更加高效

Question

最初，我在让这段代码运行时遇到了一些问题，但经过一些调整后，我对其进行了调试并准备就绪。

我对这个程序进行了多次修改。我从整数值开始，却发现这个数字太大，无法放入 int 中。然后我改用 BigIntegers，事实证明这很麻烦，但可行。从那时起，我切换到长整型（就像从一开始就应该做的那样）并将代码的运行时间缩短了 8 倍（或更多）。

这是现在的代码：

long qNum = 600851475143L;

for (long i = qNum - 1L; i * i >= qNum; i -= 2L)
    if (qNum % i == 0 && isPrime(i)) {
        System.out.println("Solution:" + i); // for debugging
        return i;
    }
    else
        System.out.println(i);// for debugging

return 0L;

它

public static boolean isPrime(long num) {
    // unnecessary if statement for this problem (b/c of for loop), but useful for others 
    if (num % 2 == 0)
        return false;

    for (long i = 3; i * i <= num; i += 2)
        if (num % i == 0)
            return false;

    return true;
}

已经运行了多个小时，但仍然没有找到任何东西。我在网上看到解决这个难题的典型方法是解析560GB的数据=/。

有什么加快速度的技巧吗？

非常感谢，

Justian

编辑：

优化代码：

public static long greatestPrimeFactor(ArrayList<Long> factors, long num) {
    for (long i = 2; i <= Math.sqrt(num); i++) {
        if (num % i == 0) {
            factors.add(i);
            return greatestPrimeFactor(factors, num / i);
        }
    }

    for (int i = factors.size()-1; i > 0; i--)
        if (isPrime(factors.get(i)))
            return num;

    return 0;
}

AND

public static boolean isPrime(long num) {
if (num % 2 == 0)
    return false;

for (long i = 3; i * i <= num; i += 2)
    if (num % i == 0)
        return false;

    return true;
}

RUN WITH

greatestPrimeFactor(new ArrayList<Long>(), 600851475143L);

Answer 1

你做了太多不必要的事情。这是一个更简单的解决方案：

long greatestFactor(long n) {
    long p = 0;
    for (long k = 2; k * k <= n; k++)
        while (n % k == 0) {
            n /= k;
            p = k;
        }
    if (n > 1)
        p = n;
    return p;
}

Answer 2

您不需要测试每个数字是否是质数。您看到了这一点，因此您只测试每个奇数（好吧，还有 2）。你可以更进一步！快速构建一个包含前几百万个素数的表，并且仅针对这些素数进行测试。你会走得更快，而且开销很小。

编辑：这就是我所说的。这非常简单。请注意我如何仅将这些值与已计算的素数进行比较。一旦您计算出相当数量的素数（例如，前 10000000 个素数），就开始像您一样基于 +2 方法进行搜索。请记住，大多数人都会很早就被发现，因为您跳过了不必要的数字。您不需要测试 15,25,35,45,55 等，因为您已经测试了 5。这本身就会剔除大约 20% 的测试，这很容易计算出计算最初的几百万个数字。

示例输出

C:\files\j\misc>java sandbox2
resized to 200
resized to 400
resized to 800
resized to 1600
resized to 3200
resized to 6400
resized to 12800
resized to 25600
resized to 51200
resized to 102400
resized to 204800
resized to 409600
resized to 819200
664579 primes in 18 seconds. Last prime was 9999991

C:\files\j\misc>

示例代码：

public class sandbox2 {
    static int[] primes = new int[100]; // where the primes really are
    static int count = 0;
    static long mostRecentPrime;

    public static void main(String[] args) throws Exception {
        addPrime(2); // give it a couple to start
        addPrime(3);
        addPrime(5);
        long start = System.currentTimeMillis();
        for(long i = 7; i < 10000000; i++) { // all primes less than 10M
            if(isPrime(i)) addPrime(i);            
        }        
        long end = System.currentTimeMillis();
        long time = (end-start) / 1000;
        System.out.println(count + " primes in " + time + " seconds. Last prime was " + mostRecentPrime);
    }    
    public static boolean isPrime(long i) {
        long max = (long)(Math.sqrt(i))+1;
        for(int pos = 0; primes[pos] < max && pos < primes.length; pos++) {
            long prime = (long)(primes[pos]);
            if(i % prime == 0) return false;
        }
        return true;
    }    
    public static void addPrime(long p) {
        mostRecentPrime = p;
        if(count == primes.length) { // resize if necessary
            int size = primes.length * 2;
            int[] newprimes = new int[size];
            System.arraycopy(primes, 0, newprimes, 0, primes.length);
            primes = newprimes;
            System.out.println("resized to " + primes.length);
        }
        primes[(int)count] = (int)p;
        count++;
    }
}

Answer 3

在 python 中，您可以计算所有质因数，然后使用 max 函数，如下所示：

def calc_prime_factors(n,i=2,result=[]):
  while i<=n:
    while n%i!=0:
      i+=1
    result.append(i)
    if n!=1:
      n,i=n/i,2
    else:
      break
  return result

print max(calc_prime_factors(600851475143))

Answer 4

我的解决方案在不到百分之一秒的时间内完成。每次找到该数字的除数时，将该数字除以该除数，然后重新开始。您除以的最大数字就是您的目标。