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