エラトステネスの篩
今日の計算機の授業で「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; }
こんな感じかね。 おそらく授業でやってた方法とは若干違うと思うが。