上のプログラムに対する補足

上のプログラムでは, 数学関数ライブラリを使用しますので, コンパイル時にオプション -lm が必要です.

プログラムでは, 次の点に注意して効率をあげています.

1. MAX 以下の合成数は, $\sqrt{\rm {MAX}}$以下の数の倍数である.
2. $i$ から, $i^2$ までの合成数は, $i$ 未満の数の倍数である.

なお, 多くの C言語の本では, 上のプログラムの変数 j の範囲を 2からはじめる 様に書いてありますが, これは上に述べた意味で効率が悪いばかりでなく, 本来のエラトステネスの方法ではありません. エラトステネスは 効率の良い方を知っていましたし, それが記録に残っているようです.