コトバンクはYahoo!辞書と技術提携しています。

エラトステネスのふるい エラトステネスのふるい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 より小さい素数全体の集合をつくることになる。

出典|ブリタニカ国際大百科事典 小項目事典ブリタニカ国際大百科事典 小項目事典について | 情報

エラトステネスのふるいの関連キーワードエラトステネス整数論倍数

今日のキーワード

処暑

二十四節気の一つ。元来,太陰太陽暦の7月中 (7月後半) のことで,太陽の黄経が 150°に達した日 (太陽暦の8月 23日か 24日) に始り,白露 (9月8日か9日) の前日までの約 15日間であ...

続きを読む

コトバンク for iPhone

コトバンク for Android