代表的な方法から、前半部分のポイント
- 「素数かどうか順番に確定作戦」
- ある数i (i <= N) を調べる。
- i より小さい全ての素数 j で割り切れないなら、その数は素数。次のi を調べる。
- 「pで割りきれれば消去作戦」
- ある数i が素数のとき、
- i より後ろの数から、Nまでの各数 j について、iで割った余りが0かどうかをチェックする。0なら、素数ではない。
- i についてNまで繰り返す。最後まで残っている数は素数
- 「pの倍数消去作戦」
- ある数 i が素数のとき、
- i より後ろの数について、i の倍数 (i * j j ≥ 2) は素数ではない。
- i についてNまで繰り返す。最後まで残っている数は素数
3が、よい。ここまでが、エラトステネスのふるいの前半部分。後半部分が、以下。
後半部分のポイント
ある数Nが素数なのかどうかを調べる → Nが 「2からN－１までの素数で割りきれるか」調べる作戦しかなさそう。でも、もっと、少ない範囲で終わるのではないか。。
- 自然数について、次のことが成り立つ。
- 自然数Nが合成数ならば、必ず√N以下の約数をもつ
- なぜなら N = P×Q (1 < P ≤ Q < N) と表 されるから N ＝ P × Q ≥ P × P
- よって、√N ＞＝ P
- したがって、2以上、√N以下の約数がなければ、Nは素数である。（数学B p162 数研出版）
上のことは、こんなことを言っている。
- N = xy (x ≥ y xとyは自然数) （これは反比例の関係式）とするとき、yの最大値は、いくつだろう。（Nを100にしてイメージしてみる）
- x = yのとき、つまり、Nの平方根である。N=xyとなるのなら、yの最大値は√Nを超えない最大の整数のはず。
だとすると、
- Nが合成数なのか（素数で割れないか）を調べるには、２からN－１まで調べるのではなくて、２から√Nを超えない最大の素数までを調べれば十分。√Nまでの素数で割り切れないなら、Nは素数だ。
- たとえば、97の場合は、√97で、9まで。しかし、8や9は素数ではないので、7まで調べて、割り切れないのだから、97は「素数」とできる。
- 97が素数かどうかを考えるのに、89なんか調べる必要はないだろう、と直感的にわかる。
- 31は、気になるかもしれない。やらなくてよい。30のあたりの数をかけて97になるのなら、相手は3くらいのはず。3のあたりは、7までに、もう調べてしまっている。
おわりに
- ある合成数が与えられたときに素因数分解をするにも、上とよく似たアルゴリズムになる。√Ｎまでの素数リストを使って、どんどん割り続けるしかない。よい方法（アルゴリズム）が、発見されていません。
- だから、ある数Ｎは素因数分解できる、とわかっていても、しかも、２つの素数のかけ算だ、とわかっていても、Ｎが非常に大きい数の場合、その２つの素数を見つけるのは、大変な時間がかかってしまう。
エラトステネスのふるいとは
まとめると：