Monday, June 17, 2013

[Project Euler] Problem 10 in C

Problem: Project Euler Problem 10

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