c++ - C++中素数的求和

Question

嗨，伙计们，我正在开发一个程序，以给出 200 万以下的所有质数的总和。这就是我所拥有的......而且我知道这种方法适用于查找素数，因为我以前使用过它......但是当我运行这个程序时，我不断得到一个无限循环并且没有输出......任何帮助都会很大赞赏！

#include <iostream>
using namespace std;

int main (int argc, char * const argv[]) {
    bool isPrime=true;
    int i = 2;
    int sum = 0;
    do{

        for ( int j = 2; j < i; j++)
        {
            if ( i % j == 0 )
            {
                isPrime=false;
                break;
            }
        }
        if (isPrime)
        {
            cout << "Prime: " << i << endl;
            sum += i; // add prime number to sum
        }
        i++;

    }while(i < 2000000);

    cout << "the sum of all the primes below two million is: " << sum << endl;
    getchar();
    return 0;
}

Answer 1

我能找到的唯一合乎逻辑的错误是你永远不会重新设置isPrime到true循环内部，但这不应该导致无限循环，只是错误的结果。

我怀疑它会进入无限循环，我只是认为这需要很长时间，因为它不是最佳的。在 之前，您不需要检查每个数字i，sqrt(i)甚至不需要检查i/2。

更好的是，您可以生成一个素数筛（谷歌这个），然后将它们相加 - 这将大大提高效率。

Answer 2

我不认为你有一个无限循环。正如 Luchian Grigore 所说，您忘记设置isPrime为，但您的代码也将需要很长时间才能运行。true请注意，您可以停止试除一次j*j > i。

Answer 3

如果您还担心以最少的努力使事情变得更高效——要获得素数，您只需检查 (6n + 1) 和 (6n + 5) 形式的数字

所以在你的主循环中包括类似的东西：

int p6 = p % 6;
if (p6 == 1) {
    result = isPrime(p);
    p += 4;
} else if (p6 == 5) {
    result = isPrime(p):
    p += 2;
}

会加快你的倍数。不要忘记角落案例 2 和 3。