エラトステネスのふるい
エラトステネスさんは古代ギリシャの学者。初めて天球儀を作成したり、地球の周の長さを計算したりと活躍した。「エラトステネスのふるい」は、そんなエラトステネスさんが「素数」を簡単に見つけようと考案した方法で、これもエラトステネスの業績の1つとして知られている。
素数とは、約数を2つしかもたない数のこと。ある数\(n\) の約数が\(1\) と\(n\) の2つしかないとき（逆に言うと、答えが\(n\) となる自然数の掛け算は\(1\times n\) しかないとき）、その数\(n\) を素数という。\(2\) は\(1 \times 2\)でしか作ることができないので素数、\(3\) も\(1 \times 3\) でしか作ることができないので素数。\(4\) は\(1 \times 4\) 以外に\(2 \times 2\) でも作ることができるので素数ではない、というわけだ。
\(1\) は素数なのか？ という疑問は、素数の勉強を始めると必ず出てくる疑問。先の定義「約数が\(1\) と\(n\) の2つしかない」に当てはめてみれば、答えは簡単。\(1\) の約数は\(1\) だけ。約数が2つではないので、\(1\)は素数ではない。
エラトステネスのふるいは、この素数の定義を逆に使って、素数以外の数を数の並びからふるい落としてしまおうという方法。ある数が素数だとわかったら、その倍数は素数ではないので消してしまう。下に1から100までの数を用意したので、次の手順で作業をしていこう
- 1は素数ではない
- リストに残っている最小の数は素数なので、2は素数
- リストに残っている最小の数は素数なので、3は素数
- リストに残っている最小の数は素数なので、5は素数
- リストに残っている最小の数は素数なので、7は素数
- 以下同様……
100以下の素数を知りたいなら、実は6の手順は不要。上の数の並びに残っている数は、すべて素数だ。なぜ、7の倍数を消すところまでやれば100までの素数がわかるのか。次にそれを考えてみよう。