Problem 10

もう一つ解くよ。

10以下の素数の和は2 + 3 + 5 + 7 = 17である.
200万以下の全ての素数の和を計算しなさい.

Problem 10 - PukiWiki

Problem 7で使ったis_prime関数を流用して素数判定する予定だったけど、Wikipediaの素数判定の項にあるサンプルプログラムを見たらそっちの方が少しだけ効率が良さそうだったので改良。
(2008/10/5追記)答えが間違っていたのでプログラムと結果を修正

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

typedef long long int llong;
#define NUM_MAX 2000000
//#define NUM_MAX 10

int is_prime(llong num) {
    llong i;

    if (num < 2) {
        return 0;
    } else if (num == 2) {
        return 1;
    }
    if (num % 2 == 0) {
        return 0;
    }
    for (i=3; i*i<=num; i+=2) {
        if (num % i == 0) {
            return 0;
        }
    }
    return 1;
}

void problem010()
{
    llong ans;
    llong i;

    /* solve this problem here */
    ans = 0;
    for (i=2; i<=NUM_MAX; i++) {
        if (is_prime(i)>0) {
            ans += i;
        }
    }

    printf("%s: answer = %lld\n", __FUNCTION__, ans);
}

int main(int argc, char* argv[]) 
{
    problem010();
    return 0;
}

実行結果

3秒ぐらいかかったんだけどそんなものですよね？

$ ./problem010
problem010: answer = 142913828922