c - 需要帮助优化算法 - 两百万以下所有质数的总和

Question

我正在尝试做一个 Project 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;
}

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

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

我的猜测是有一些算法可以减少正在完成的工作。问题是，我不知道它是什么。

有人能给我指出正确的方向吗？

谢谢。

Answer 1

与 i来自 2至 2000000 (或任何上限)，一旦你确定 i是质数，然后你知道 {2i, 3i, 4i, ..., ni}不是质数，其中 ni <= 2000000 .

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

随着您逐步浏览 testNumbers 数组并从此列表中删除数字，您现在知道的数字不是素数，您可以显着减少实际需要测试的数字。

是的，这就是埃拉托色尼筛法。