需要帮助优化算法 - 2000000下的所有质数之和 [英] Need help optimizing algorithm - sum of all prime numbers under two million

问题描述

我试图做一个项目欧拉问题。

我要找的所有质数的总和200万之下。

I'm looking for the sum of all prime numbers under 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 像的问题。

When I run it with the limit of 10, it gets the correct answer, 17 like in the question.

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

My guess is there is some algorithm that can reduce the work being done. Problem is, I don't know what it is.

可有人请点我朝着正确的方向？

Can someone please point me in the right direction?

感谢。

推荐答案

通过 I 从 2 到 2000000 （或任何上限），一旦你确定 I 为素数，你后来才知道， {2I，3I，4I，...，NI} 不是素数，其中 NI＆LT; = 2000000 。

With i from 2 to 2000000 (or whatever upper limit), once you determine that i is prime, you then know that {2i, 3i, 4i, ..., ni} are not prime numbers, where ni <= 2000000.

您不必测试这些数字 - 你知道他们是不是素数

You don't need to test those numbers — you know they aren't prime.

当你通过你的 testNumbers 阵列进步和消除这个列表的数字，数字，你知道现在是不是素数，则显著减少你真正需要测试的数字

As you progress through your array of testNumbers and eliminate numbers from this list, numbers that you now know are not prime, you significantly reduce the numbers you actually need to test.

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

Yes, this is the Sieve of Eratosthenes.

这篇关于需要帮助优化算法 - 2000000下的所有质数之和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！