エラトステネスのふるい

正の約数が、１とその数自身だけである、2 以上の自然数を素数と呼びます。
素数が無限にあることは、古代ギリシア時代から知られています。

素数は無限にある

『素数の個数は、いかなる定められた素数の個数より多い』
ユークリッドによる証明

定められた個数（\(n\)個とする）の素数を小さい順に、\(p_{1},p_{2},\cdots,p_{n}\)とする
\(p=p_{1}p_{2}\cdots p_{n}+1\)とすると、\(p\)は素数か合成数のいずれかである。

\(p\)が素数のとき、最大の素数\(p_{n}\)より大きな素数になり、定められた個数の素数より多くの素数が存在することになる。

\(p\)が合成数のとき、\(p\)を割り切る素数が存在するが、\(p\)の定義では全ての\(p_{i}\)で割ったあまりが１となり、割り切れない。すなわち、全ての\(p_{i}\)以外に素数が存在することになり、定められた個数の素数より多くの素数が存在することになる。

上記より、素数の個数は、いかなる定められた素数の個数より多く存在する。

エラトステネスのふるい

エラトステネスのふるいは、ある自然数\(n\)以下の素数を列挙する方法です。原始的な方法と比べてみましょう。

①試し割り（原始的な方法）

・\(n\)まで順々に、素数かどうかを判定する。

・素数を自然数\(k\)が合成数なら、\(k\)は素数の積で表せる。\(k=p_{1}p_{2}\cdots p_{n}\)
つまり、約数の１つは必ず\(\sqrt{k}\)より小さいので、\(\sqrt{k}\)以下の素数で割り切れなければ、\(k\)は素数になる。

例）\(30\)までの素数を求める

\(2\)は、\(1\)と自分自身でしか割り切れないので素数
\(3\)は、\(2\)で割り切れないので素数
\(4\)は、\(2\)で割り切れるので、素数ではない
\(5\)は、\(2，3\)で割り切れないので素数

\(5<\sqrt{30}<6\)なので、以下の試し割りは\(2,3,5\)まででよい

\(6\)は、\(2\)で割り切れるので、素数ではない
\(7\)は、\(2,3,5\)で割り切れないので素数
・・・中略　（\(8\)から\(29\)まで同様の判定）
\(30\)は、\(2\)で割り切れるので、素数ではない

\(2,3,5,7,11,13,17,19,23,29\)が素数

②エラトステネスの篩

\(n \)以下の素数の求め方
・\(２からｎ\)までの整数を並べる
↓
・残っている数の中で、一番小さい数字(\(p\)とする)を残して、\(p\) 以外の \(p\)の倍数を消していき、\(p\)が\(\sqrt{n}\) を超えたら終了
↓
・残った数字が、素数

例）\(30\)までの素数を求める

・２の倍数を消す