エラトステネスのふるい（その他表記）sieve of Eratosthenēs

ブリタニカ国際大百科事典 小項目事典

エラトステネスのふるい
sieve of Eratosthenēs

エラトステネスが考案した素数検出法。その方法は，合成数を順次ふるいにかけるように落して，任意の正の整数をこえない素数を見出すことにある。まず1は素数でないから落す。次に2と N の間にあるすべての正の整数を大きさの順に並べる。そこで，その最初の素数2を残し，2の倍数 4 ，6，8，… すなわち2から2つ目ごとにくるすべての数を落す。次に2を除き残っているもののなかで最小の素数は3であるから，3を残し，3の倍数 6 ，9，… すなわち3から3つ目ごとにくるすべての数を落す。さらに2，3を除き残っているもののなかで最小の素数は5であるから，5を残し，5の倍数 10 ，15，… すなわち5から5つ目ごとにくるすべての数を落す。このようなふるいにかける操作を，√N より小さいすべての素数の倍数が，√N より小さい素数だけを除いて，すべて落されてしまうまで続ける。こうすれば，残っている数は，N より小さい素数全体の集合をつくることになる。

出典　ブリタニカ国際大百科事典 小項目事典