エラトステネスの篩(読み)エラトステネスノフルイ

デジタル大辞泉の解説

エラトステネス‐の‐ふるい〔‐ふるひ〕【エラトステネスの×篩】

古代ギリシャの学者エラトステネスが考案した素数の選別法。自然数を小さい順に並べ、まず1を消去し、次に2、3、5…と小さい方の素数を残してそれらの倍数を消去することで、最終的にある整数以下のすべての素数が得られる。

出典 小学館デジタル大辞泉について 情報 | 凡例

百科事典マイペディアの解説

エラトステネスの篩【エラトステネスのふるい】

エラトステネスが発見した素数の見いだし方。自然数を1,2,3,……と並べ,1を消し,素数2を残してその倍数4,6,8,……を消し,次の素数3を残してその倍数9,15,……を消す。こうして素数pの倍数を消したとき,pの次の素数がqなら,q2より小さい数で残ったものはすべて素数。
→関連項目整数論

出典 株式会社平凡社百科事典マイペディアについて 情報

大辞林 第三版の解説

エラトステネスのふるい【エラトステネスの篩】

自然数を小さい順に並べ小さい方の素数の倍数を順次消去して素数を残していくという、素数の選別法。

出典 三省堂大辞林 第三版について 情報

世界大百科事典内のエラトステネスの篩の言及

【エラトステネス】より

…また地球表面を熱帯,温帯,寒帯のように地域分けしたとも伝えられる。数学においては,素数を見いだすための〈エラトステネスの篩(ふるい)〉によって知られる。この方法は自然数を小さい順に並べ,小さいほうの素数の倍数を次々に消去して素数を残していくという原始的なものである。…

【素数】より

…1よりも大きい自然数で,1と自分自身以外に約数をもたないもの。例えば,2,3,5,7,11などである。2以外の素数は奇数なので奇素数という。1以外の自然数で素数でないものおよびそれにマイナスの符号をつけたもの(±4,±6など)を合成数という。与えられた自然数nが素数かどうかを判定するには以下の素数で割れるかどうか調べてみればよい。以下の数が素数かどうかわからなければそれでも割ってみる。しかし大きな自然数が素数かどうかを判定するのは一般に容易でない。…

※「エラトステネスの篩」について言及している用語解説の一部を掲載しています。

出典|株式会社平凡社世界大百科事典 第2版について | 情報

今日のキーワード

夏至

二十四節気の一つであるが,二至 (夏至,冬至) ,二分 (春分,秋分) の四季の中央におかれた中気。夏至は太陰太陽暦の5月中 (5月の後半) のことで,太陽の黄経が 90°に達した日 (太陽暦の6月 ...

続きを読む

コトバンク for iPhone

コトバンク for Android