java - 如何改进我的素数和算法？

Question

我编写了一个代码，它返回值低于 200 万的所有素数的总和。但结果需要花费大量时间（等待 30 分钟才能得到答案）。

谁能建议如何使算法更有效？

public static void main(String[] args){

    int i,primeNum=1,sumPrime=0,c=0;
    while (primeNum<2000000){
            int factors=0;
            for(i=1;i<=primeNum;i++){
                if((primeNum%i)==0) {
                    factors++;  // total number of factors                  
                }
            }               
            if(factors==2){ 
                if(primeNum<2000000){
                    sumPrime=primeNum+c;
                    c=sumPrime;
                }
                System.out.println(primeNum);   
            }

            primeNum++;

        }
        System.out.println(sumPrime);
    }

score 3 · Accepted Answer

3

Atkin算法的检查筛。它是埃拉托色尼古筛的优化版本。

于 2013-05-17T10:06:20.160 回答

score 1 · Accepted Answer

作为一个开始：

循环是否for(i=1;i<=primeNum;i++){必须运行到primeNum或可能只是到的平方根primeNum？
i必须增加 1 还是 2 更有效？
...

score 1 · Accepted Answer

我不会为您提供完整的答案，因为 Project Euler 的目标（我猜您是从那里得到这个问题的）是思考问题并提出解决方案。

无论如何，我将留下一些步骤，以正确的方式指导您：

将您的代码分解为两种方法：
- Eratosthenes 筛子（http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes）非常简单，它会返回一个包含 2M 以下的所有素数的列表。
- 一种简单地汇总 Sieve 返回的所有值的方法。

这将非常有效，如果您正确实施筛子，它应该将您的执行时间缩短到几秒钟。

score 1 · Accepted Answer

有很多事情：

当你想确定一个以上的素筛算法时要好得多。（谷歌搜索 Eratosthenes 的筛子，然后总结）。
即使像您一样使用朴素算法，也有一些改进可能：
1. 想一想：除了第一个偶数素数之外，所有其他都是奇数，所以你不应该primeNumber++在你的循环中使用 /，而应该更多地使用 a primeNumber+=2（实际上循环不是从 1 开始的）。[运行时间减半]
2. 如果它们是其中的一个因素，则检查所有小于主要候选者的数字的内部循环。在那里，您还可以跳过所有偶数（并始终增加 2）。[运行时间几乎减半]。
3. 在您的内部循环中，您可以节省更多。您不需要检查所有数字 < 素数，但最多只能检查 < sqrt(prime)。因为当一个数除以素数时，总是有两个因数，其中一个必须小于（或等于）平方根。[运行时“扎根”]
4. 你不想要素数的因数，你只想知道这个数是否是素数。所以当你知道它不是素数时，不要继续测试它（即当你得到第一个因素时打破你的循环（为了更容易，你不应该测试 1 和数字本身） - 这会节省你大量的时间。[运行时间更加减少。]

因此，有了这个提示，即使您没有筛子的幼稚方法也会导致运行时间少于 2 分钟 (sqrt(15/4))。

score 1 · Accepted Answer

这部分非常无效：-

for(i=1;i<=primeNum;i++){
  if((primeNum%i)==0) {
    factors++;  // total number of factors                  
  }
}

计算因子的总数。由于您只关心数字是否为素数，因此不需要因子的数量。如果有一个因素不是 1 或被测试的数字，则应该进行测试。所以你可以这样做： -

boolean is_prime = true;
// start at 3 as 1 is always a factor and even numbers above 2 are definately not prime, terminate at n-1 as n is also a factor
for(i=3;i<primeNum;i+=2){
  if((primeNum%i)==0) {
    is_prime = false;
    break;
  }
}

这现在对非素数更有效。对于素数，它做的太多了，因素成对出现：如果 ab == c 然后 a <= sqrt(c) 和 b >= sqrt(c)，因此循环可以安全地终止于 sqrt(primeNum)。您可以在循环之前计算 sqrt(primeNum) ，但这通常需要使用浮点函数。代替或在 i > sqrt(primeNum) 时终止，在 ii > primeNum 时终止循环。您还可以删除 ii 乘法并将其替换为一个额外的变量和几个加法（留给读者作为练习）。

另一种方法是使用筛子，正如其他人所提到的，当搜索空间有固定上限时，这是一种简单的方法。您可以制作一个没有上限（内存大小无法承受）但实施起来非常棘手的版本，因为它需要一些动态内存管理。不确定一个简单的筛子是否会比因子搜索更快，因为你会用筛子击中记忆，这对速度有很大影响。

score 1 · Accepted Answer

是循环中的循环导致代码变慢。这是我发现的一些代码，它们只需几秒钟就可以以相同的标准运行：

void setup() {
  for (int i = 1; i<2000000; i++) {
    if (isPrime(i)) {
      System.out.println(i);
    }
  }
}

boolean isPrime(int number) {
  if (number < 2) return false;
  if (number == 2) return true;
  if (number % 2 == 0) return false;
  for (int i = 3; (i*i)<=number; i+=2) {
    if (number % i == 0 ) return false;
  }
  return true;
}

score 0 · Accepted Answer

你的算法效率很低，计算素数的算法看这里。一旦你有了它们，总结它们不应该是问题。

score 0 · Accepted Answer

实际上代码没有得到足够的优化，因为在最坏的情况下，执行循环所花费的时间会更多。您甚至可以优化查找素数的代码。试试下面的代码，它工作正常

public static void main(String[] args) {
    //you know 2 is the only even prime.
    int sum = 2;
    for (int i = 3; i <= 2000000; i++) {
        boolean prime = isPrime(i);
        if(prime){
            sum+=i;
        }
    }
    System.out.println("Sum = " + sum);
}

/*
 * we know 2 is the “oddest” prime – it happens to be the only even prime
 * number. Because of this, we need only check 2 separately, then traverse
 * odd numbers up to the square root of n
 */
public static boolean isPrime(int n) {
    // check if n is a multiple of 2
    if (n % 2 == 0)
        return false;
    // if not, then just check the odds
    for (int i = 3; i * i <= n; i += 2) {
        if (n % i == 0)
            return false;
    }
    return true;
}

score 0 · Accepted Answer

此函数使用埃拉托色尼筛法对小于n的素数求和：

function sumPrimes(n)
    sum := 0
    sieve := makeArray(2..n, True)
    for p from 2 to n step 1
        if sieve[p]
            sum := sum + p
            for i from p * p to n step p
                sieve[i] := False
    return sum

我会把它留给你翻译成Java。对于n = 2000000，这应该在一两秒内运行。

score 0 · Accepted Answer

在 Python 中，您可以通过这种方式完成它。与以前的一些解决方案相比，一旦我越过 $\sqrt{n}$，我就会尽量不改变 isPrime 向量

import math
def sum_primes(nmax):
    maxDivisor=int(math.floor(math.sqrt(nmax)))
    isPrime=[False,False]+range(2,nmax+1)

    for i in range(2,maxDivisor+1):
       if isPrime[i] is not False:
           for dummy in range(i*2,nmax+1,i):
               isPrime[dummy]=False

    print (sum(isPrime))

score -2 · Accepted Answer

减少 if 条件的使用。它会减慢您的代码速度。如果可能，请尝试使用三元运算符，如果这会影响您的速度，即使在 java 1.5 中不建议这样做。

试试这个解决方案：

if( (factors==2)&&(primeNum<2000000) )

而不是重复 if 条件并发布任何差异。

java - 如何改进我的素数和算法？

11 回答 11

Related

Reference