euler10

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

#include <stdio.h>
#include <math.h>
#include <string.h>

#define N 2000000
int prime[N/2];

int is_prime(int num)
{
    int i;
    int sqrt_num = sqrt(num);

    for (i = 0; i < N; i++) {
        if (prime[i]) {
            if (!(num % prime[i]))
                return 0;
            else if (prime[i] > sqrt_num)
                break;

        } else
            break;
    }

    return 1;
}

int main(int argc, const char *argv[])
{
    long long result;
    int i, count;

    memset(prime, 0, sizeof(prime));
    result = prime[0] = 2;
    count = 1;
    for (i = 3; i < N; i += 2) {
        if (is_prime(i)) {
            prime[count++] = i;
            result += i;
        }
    }

    printf("result: %lld\n", result);

    return 0;
}

用于存放prime的数组有些浪费内存了。