需要帮助优化算法 - 所有素数的总和低于200万

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此列表中的数字并从中删除数字时,您现在知道的数字不是素数,您可以显着减少实际需要测试的数字.

是的,这是Eratosthenes的筛子.