エラトステネスの篩

今日の計算機の授業で「100万以下の素数をすべて出力するプログラムを(Cで)書け」というレポートが出たのでちゃちゃっと書いてみた。

#include 
#define MAX 1000000

int main(void) {
    char flag[(MAX - 3) / 2 + 1] = "";
    int p, i, j;

    printf("Prime numbers under %d\n", MAX);
    printf(" %7d", 2);
    for (i = 0; i < sizeof(flag); ++i) {
        if (!flag[i]) {
            printf(" %7d", (p = i + i + 3));
            for (j = i + p; j < sizeof(flag); j += p) {
                flag[j] = 1;
            }
        }
    }
    return 0;
}

こんな感じかね。 おそらく授業でやってた方法とは若干違うと思うが。