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

you can short the time you look for prime number. there is million ways to do it. I think you don't need to test until num, but only to sqrt(num) but this will only help you a little (on the actual prime numbers)

There are statistical methods to check if a prime number is actually prime which are faster and can only be mistaken once in 2^alot....

The fastest way to find a prime number was found by a researcher from India, but I can't find the link.

you can also look here:

Wiki

Answer 2

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.

Answer 3

You can speed up your isPrime(int num) function by passing the array of primes discovered so far and check if num is a multiple of these primes. Also you don't need to loop up to num, only sqrt(num).

Answer 4

Use sieve of Atkin, its an optimized version of sieve of Eratosthenes link.

Answer 5

http://en.wikipedia.org/wiki/Sieve_of_Sundaram

Answer 6

Hint: Use BitArray and seive method.

See the code if you cannot figure it out.The code is in Java but wouldn't be difficult to translate to C.