需要帮助优化算法-2百万以下所有素数之和

Question

我正在尝试做一个Euler项目问题。

我在找2,000,000以下的所有素数之和。

这就是我拥有的..。

int main(int argc, char *argv[]) {


    unsigned long int sum = 0;

    for (unsigned long int i = 0; i < 2000000; i++) {


        if (isPrime(i)) {
            sum += i;
        }
    }

    printf("sum => %lu\n", sum);


}

int isPrime(int num) {

    if (num < 2) {
        return 0;
    }

    for (int i = 2; i < num; ++i) {
        if (num % i == 0) {
            return 0;
        }
    }
    return 1;
}

它需要很长时间才能运行，因此它不满足Euler问题的一分钟运行时间规则。

当我以10为限运行它时，它得到了正确的答案，就像问题中的17。

我猜想有一些算法可以减少正在做的工作。问题是，我不知道这是什么。

谁能帮我指出正确的方向吗？

谢谢。

Answer 1

使用i从2到2000000 (或任何上限)，一旦确定i是素数，您就知道{2i, 3i, 4i, ..., ni}不是素数，其中ni <= 2000000。

你不需要测试这些数字--你知道它们不是质数。

当您通过testNumbers数组并从这个列表中删除数字时，您现在知道的数字并不是素数，您将显著减少实际需要测试的数字。

是的，这是埃拉托斯提尼的筛子。

Answer 2

你可以缩短你寻找素数的时间。有无数种方法可以做到。我认为你不需要在num之前进行测试，但是只需要对sqrt(num)进行测试，但是这只会对你(实际的素数)有一点帮助。

有统计方法可以检查质数是否实际上是素数，它速度更快，只能在2^alot中出错一次.

找到质数最快的方法是印度的一位研究人员，但我找不到联系。

你也可以在这里看到：

维基

Answer 3

您可以通过传递到目前为止发现的素数数组来加快isPrime(int num)函数的速度，并检查num是否是这些素数的倍数。另外，您不需要循环到num，只需要循环到sqrt(num)。