Need help optimizing algorithm - sum of all prime numbers under two million

Question

I'm trying to do a Project Euler question.

I'm looking for the sum of all prime numbers under 2,000,000.

This is what I have...

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;
}

It takes ages to run, therefore it does not satisfy the one minute rule of run time for Euler problems.

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?

Thanks.

Answer 1

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.

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.