コトバンクは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 より小さい素数全体の集合をつくることになる。

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

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

今日のキーワード

スタットキャスト

大リーグの全30球場に高精度カメラやレーダーを設置し、ボールや選手の動きを細かく分析。走攻守全てで、これまで分からなかったデータを解析し、試合やチーム作りに生かせる。例えば投手では、投げる球種の回転数...

続きを読む

コトバンク for iPhone

コトバンク for Android