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

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

今日のキーワード

青天の霹靂

《陸游「九月四日鶏未鳴起作」から。晴れ渡った空に突然起こる雷の意》急に起きる変動・大事件。また、突然うけた衝撃。[補説]「晴天の霹靂」と書くのは誤り。[類語]突発的・発作的・反射的・突然・ひょっこり・...

青天の霹靂の用語解説を読む

コトバンク for iPhone

コトバンク for Android