エラトステネスの篩（読み）エラトステネスノフルイ

デジタル大辞泉

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

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

出典　小学館

百科事典マイペディア

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

エラトステネスが発見した素数の見いだし方。自然数を１，２，３，……と並べ，１を消し，素数２を残してその倍数４，６，８，……を消し，次の素数３を残してその倍数９，15，……を消す。こうして素数pの倍数を消したとき，pの次の素数がqなら，q²より小さい数で残ったものはすべて素数。
→関連項目整数論

出典　株式会社平凡社

改訂新版　世界大百科事典

エラトステネスの篩 (エラトステネスのふるい)

→素数

出典　株式会社平凡社「改訂新版　世界大百科事典」

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

【エラトステネス】より

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

【素数】より

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

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

出典｜株式会社平凡社「世界大百科事典（旧版）」