Need help optimizing the algorithm - the sum of all primes up to two million

Question

I am trying to complete a project Euler question.

I am looking for the sum of all primes less than 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 age to run, so it does not satisfy the 1 minute rule for Euler task execution time.

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

My guess is there is some kind of algorithm that can reduce the work being done. The problem is that I do not know what it is.

Can anyone point me in the right direction?

Thanks.

Answer 1

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

You do not need to check these numbers - you know that they are not simple.

As you go through your testNumbers array and eliminate the number from this list, the numbers you know now are not the first, you significantly reduce the numbers that you really need for testing.

Yes, this is the Sieve of Eratosthenes.

Answer 2

You can shorten the prime time. There are many ways to do this. I think you do not need to test before num, but only before sqrt (num), but this will only help you a bit (in actual primes)

There are statistical methods for checking whether a prime is simple, the faster, and it can be mistakenly taken only once in 2 ^ alo ...

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

You can also look here:

Wiki

Answer 3

You can speed up your isPrime(int num) function by passing in the array of primes found so far, and check if num multiple of these primes. Also you do not need to loop to num , only sqrt(num) .

Answer 4

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

Answer 5

Hint: Use the BitArray and seive method.

See the code if you cannot figure it out. The code is in Java, but it will not be difficult to translate to C.

Answer 6

 #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 will be the output:

 $kpwr 148933 numbers largest prime 1999993 sum: 142913828922 $ 

Answer 7

For reference (if you are here, then you are already trying to find the answer), I quote Lucy_Hedgehog (in the development team for PE):

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

The main idea is this: let S (v, m) be the sum of integers in the range 2..v, which remains after sifting with all strokes less than or equal to m. That is, S (v, m) is the sum of integers up to v, which are either prime or the product of primes greater than m.

S (v, p) is equal to S (v, p-1) if p is not simple or v is less than p * n. Otherwise (p prime, p * p <= v) S (v, p) can be calculated from S (v, p-1) by finding the sum of integers that are removed by sifting with p. In this step, the integer is removed if it is the product of p with another integer that does not have a divisor less than p. It can be expressed as

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

To implement this, you can use dynamic programming. It is enough to calculate S (v, p) for all natural numbers v, which are representable as (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 $ O (n ^ {0.75}) $ and needs 9 ms to find a solution.

Answer 8

if you can handle the case test for 2 , then run a cycle of three and put i+=2 instead of i++ , reducing the loop iteration by half