1

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

我已经对这个程序进行了几次修改。我从整数值开始，却发现这个数字太大而无法放入 int 中。然后我改用 BigIntegers，这被证明很麻烦，但可行。从那里，我切换到 longs （从一开始就应该这样做）并将我的代码的运行时间缩短 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的数据=/。

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

非常感谢，

贾斯蒂安

编辑：

优化代码：

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

和

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

运行

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

4 回答 4

3

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

于 2010-07-28T19:14:37.973 回答
3

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

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;
}
于 2010-08-29T22:24:04.527 回答
0

您不需要测试每个数字是否为素数。您会看到这一点，因此您只测试每个奇数（以及 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++;
    }
}
于 2010-07-28T19:15:18.430 回答
0

在 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))
于 2014-09-22T21:17:35.250 回答