Webであなたの夢が叶う！のHirokoです。
Webで数学、
今回はエラトステネスのふるいをご紹介します。
エラトステネスは今から2200年以上前に
エジプトのアレクサンドリアというところで
図書館の館長をしていた数学者です。
グノモンというL字型の定木を使って
地球の大きさを測った人物としても有名です。
そのエラトステネスが、数学の分野でも
素数を発見する手法を考案しています。
それが「エラトステネスのふるい」です。
素数とは、
１と自分自身以外には約数を持たない数のことでしたね。
また、素数でない数のことを合成数といいます。
自然数をふるいにかけて素数と合成数にわける
という簡単な手法で、手順は以下になります。
① 奇数を昇順に並べて
ふるいにかける数字リストをつくる
（偶数は２で割り切れるので省く）
② １は素数でも合成数でもない特別な数なので
ふるいにかける数字リストから省く。
③ ふるいにかける数字リストの
トップに位置する数を素数リストに移動して、
その数の倍数をリストからふるい落とす。
④ ③の作業をふるいにかける数字リストの先頭値が、
ふるいにかける数字リストの最大数の平方根に
なるまで続ける
⑤ ④の用件を満たしたタイミングで
残りの数を素数リストに移動する
これで素数を見つけることができます。
単純ですが根気のいる作業ですね。
プログラムを組む人は、
Loopの勉強のときに「エラトステネスのふるい」を
課題として取り組んだ経験があるのではないでしょうか？
PHPで書くと、
<?php
function eratosthenes($max) {
// maxの平方根
$sqrt = floor(sqrt($max));
// keyで配列
$lists = array_fill(2, $max-1, true);
// 倍数を取り除く
for ($i=2; $i<=$sqrt; $i++) {
if (isset($lists[$i])) {
for ($j=$i*2; $j<=$max; $j+=$i) {
unset($lists[$j]);
}
}
}
return array_keys($lists);
}
?>
となるでしょうか？
ちなみに・・・
NHKEテレの2355で、2～100までの数を対象にした
「エラトステネスの篩」を中尾ミエさんが、
おやすみソングとして歌われていたようです。
またCDも発売中ということですので、
聴いてみたいと思います。
今日も最後まで読んでいただいてありがとうございました。