エラトステネスに学ぶ素因数の見つけ方
整数mに対し、mの約数となる素数pをmの素因数という。3は12の素因数、5は30の素因数である。
素数のリストを作ろうとするとき、ここで紹介するエラトステネス（紀元前275－前194）の篩（ふるい）の方法は素朴で素晴らしいものである。
この方法で100未満の素数の表を作ってみよう。パソコンを使うと、この方法で相当大きな素数表も作ることができる。
準備として、2以上100未満の整数mが素数でないとする。mの素因数のうちで一番小さいものをpとすると、mはp×p以上になる。
そこで、pが10より大きいならば、mとp×pは100より大きくなってしまうので矛盾である。したがって、pは10未満の素数となり、pは2，3，5，7のどれかになる。
つまり、2以上100未満の整数で素数でないものは、2，3，5，7のどれかを素因数としてもつ。それゆえ、2，3，5，7のどれでも割り切れない2以上100未満の整数は、必ず素数になる。
以上から、次のことが分かる。
2以上100未満の整数の表を書いて、2以外の2の倍数全部を線で消す。続けて、 3以外の3の倍数全部、5以外の5の倍数全部、7以外の7の倍数全部も線で消す。
100未満の素数全部
『大人のための算数力講義』芳沢光雄著線を引かれずに残った整数はこの通りとなる。
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
これらが100未満の素数全部なのである。
