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.

Answer 2

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

if you can handle the case test for 2 then start loop from three and put i+=2 instead of i++ reducing loop iteration by half

Answer 5

For reference (if you are here then you are already trying to lookup the answer), I quote Lucy_Hedgehog (on the Development Team for PE):

Here is a solution that is more efficient than the sieve of Eratosthenes. It is derived from similar algorithms for counting primes. The advantage is that there is no need to find all the primes to find their sum.

The main idea is as follows: Let S(v,m) be the sum of integers in the range 2..v that remain after sieving with all primes smaller or equal than m. That is S(v,m) is the sum of integers up to v that are either prime or the product of primes larger than m.

S(v, p) is equal to S(v, p-1) if p is not prime or v is smaller than p * p. Otherwise (p prime, p*p<=v) S(v,p) can be computed from S(v,p-1) by finding the sum of integers that are removed while sieving with p. An integer is removed in this step if it is the product of p with another integer that has no divisor smaller than p. This can be expressed as

$S(v,p) = S(v, p-1) - p (S(v/p, p-1) - S(p-1,p-1)).$

Dynamic programming can be used to implement this. It is sufficient to compute S(v,p) for all positive integers v that are representable as floor(n/k) for some integer k and all $p\leq\sqrt v$.

def P10(n):
    r = int(n**0.5)
    assert r*r <= n and (r+1)**2 > n
    V = [n//i for i in range(1,r+1)]
    V += list(range(V[-1]-1,0,-1))
    S = {i:i*(i+1)//2-1 for i in V}
    for p in range(2,r+1):
        if S[p] > S[p-1]:  # p is prime
            sp = S[p-1]  # sum of primes smaller than p
            p2 = p*p
            for v in V:
                if v < p2: break
                S[v] -= p*(S[v//p] - sp)
    return S[n]

The complexity of this algorithm is about $O(n^{0.75})$ and needs 9 ms to find the solution.

The ideas are similar to finding totient sum and is an application of the Dirichlet hyperbola method.

Answer 6

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

Answer 7

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.

Answer 8

#include <windows.h>
#include <stdio.h>
#include <stdlib.h>

struct prime_list_t {
    long                n;
    struct prime_list_t *next;
};

void add_prime_list_t(struct prime_list_t** list, long n);
void free_prime_list_t(struct prime_list_t** list);
long count_prime_list_t(struct prime_list_t* list);
long last_prime_list_t(struct prime_list_t* list);

/* if one of the primes in list divides n, is not a prime */
int is_prime(struct prime_list_t* pl, long n) {
    struct prime_list_t* p;

    if(pl == NULL) {
        abort();
    }
    p = pl;
    while(p != NULL) {
        if(n % p->n == 0) {
            return 1;
        }
        p = p->next;
    }
    return 0;
}

int main() {
    struct prime_list_t* pl = NULL;
    struct prime_list_t* p;
    long n_up = 2000000;
    long long p_sum = 0;
    long ppr;
    int done;

    /* add first prime number */
    add_prime_list_t(&pl, 2);

    /* from now on add to this list up to the number of items */
    done = 0;
    do {
        /* get the last prime plus one */
        ppr = last_prime_list_t(pl) + 1;
        while(is_prime(pl, ppr) != 0) {
            ppr++;
            if(ppr >= n_up) {
                /* hit the upper limit */
                done = 1;
                break;
            }
        }
        if(done) {
            break;
        }

        /* ppr is prime */
        add_prime_list_t(&pl, ppr);

        /* display status */
        printf("%ld numbers largest prime %ld\r", count_prime_list_t(pl), last_prime_list_t(pl));
    } while(!done);

    p = pl;
    p_sum = 0;
    while(p) {
        // printf("%d ", p->n);
        p_sum += p->n;
        p = p->next;
    }
    printf("\nsum: %I64d\n", p_sum);


    free_prime_list_t(&pl);
    return 0;
}

void add_prime_list_t(struct prime_list_t** list, long n) {
    struct prime_list_t* node;

    if(list == NULL) {
        abort();
    }

    node = (struct prime_list_t*)malloc(sizeof(struct prime_list_t));
    if(node == NULL) {
        abort();
    }

    node->n = n;
    node->next = NULL;

    if(*list == NULL) {
        *list = node;
    }
    else {
        struct prime_list_t* p;

        p = *list;
        while(p->next != NULL) {
            p = p->next;
        }
        p->next = node;
    }
}

void free_prime_list_t(struct prime_list_t** list) {
    struct prime_list_t* node;

    if(list == NULL) {
        return;
    }
    node = *list;
    while(node != NULL) {
        struct prime_list_t* p;

        p = node;
        node = node->next;
        free(p);
    }
    *list = NULL;
}

long count_prime_list_t(struct prime_list_t* list) {
    long c;
    struct prime_list_t* p;

    for(p = list, c = 0; p != NULL; p = p->next, c++)
        ;
    return c;
}

long last_prime_list_t(struct prime_list_t* list) {
    long n;
    struct prime_list_t* p;

    n = 0;
    p = list;
    while(p->next != NULL) {
        p = p->next;
    }
    return p->n;
}

And this would be the output:

$kpwr
148933 numbers largest prime 1999993
sum: 142913828922

$