ブリタニカ国際大百科事典 小項目事典 「エラトステネスのふるい」の意味・わかりやすい解説 エラトステネスのふるい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 より小さい素数全体の集合をつくることになる。 出典 ブリタニカ国際大百科事典 小項目事典ブリタニカ国際大百科事典 小項目事典について 情報