There's not much to explain here, just summing all the primes below 2,000,000.
I believe the technique used for problem 7 (sieve of erastosthenes) is the same as the technique used in this problem with some minor tweaks.
I should probably create a sieve of erastosthenes since the questions from Project Euler deal with a lot of primes..
#include <stdio.h> #include <stdlib.h> #include <inttypes.h> int sieve[2000000]; int main(){ memset(sieve, -1, sizeof(int)*2000000); sieve[2] = 1; int i, j, div; for (i = 4; i <= 2000000; i+=2){ sieve[i] = 0; } i = 3, j = 3, div = 3; while (i <= 2000000){ if (sieve[i] == -1){ div = i; sieve[i] = 1; for (j = div*2; j<=2000000; j+=div) sieve[j] = 0; } i++; } __int64 sum = 0; i = 2; while(i < 2000000){ if (sieve[i] == 1) sum += i; i++; } printf("%lld\n", sum); return 0; }
Best Execution Time: 0.136s
Answer:
No comments:
Post a Comment