100までの素数を求める

配列に「エラトステネスのふるい」を応用して100までの素数を求めます。

エラトステネスのふるい

  1. 素数とは「2以上の1と自分自身以外に約数を持たない整数」のことを言います。
    例えば13は、2でも3でも・・・7でも割り切れず、13を割りきることのできる数は、1と13だけなので13は素数です。
    15は「3*5=15」で3と5で割り切れるので素数ではなく合成数です。
  2. 素数を求める「エラトステネスのふるい」の説明です。
    エラトステネスはギリシアの博物学者で素数を見つける方法「エラトステネスの篩(ふるい)」を案出しました。
    また地球の形を球体と考え、その全周を推定しています。
    年代は古く「紀元前 276 ~ 紀元前 195 頃」で、もちろんコンピュータの面影もありません。
    従って、この説明もコンピュータを意識したものではありません。
    1. step 1: 2からnまでのすべての整数を「ふるい」に入れる。
    2. step 2: 「ふるい」に入っている数の中で最小の数を取り出し「素数」に加える。
    3. step 3: この数の倍数を全て「ふるい」から除く。
    4. step 4: 「ふるい」が空になるまで、step 2,3 を繰り返す。
  3. 配列に「エラトステネスのふるい」を応用して100までの素数を求めます。

プログラムの作成

array_sosu.php のソースコードを Shift-JIS でタイプして c:\DATA\PHP\ に格納して下さい。
<?php
for($n=0; $n<100; $n++) $array[$n]= $n;
for($i=2; $i<8; $i++)
{   for($j=$i+$i; $j<100; $j+= $i)   $array[$j]= 0;
}
for($n=2; $n<100; $n++)
    if ($array[$n]>1)   print($n . " : ");
?>

【実行画面】
コマンドプロンプトを起動して array_sosu.php をコンパイルします。
C:\Windows\System32>cd \data\php

C:\DATA\PHP>php array_sosu.php
2 : 3 : 5 : 7 : 11 : 13 : 17 : 19 : 23 : 29 : 31 : 37 : 41 : 43 : 47 : 53 : 59 :
 61 : 67 : 71 : 73 : 79 : 83 : 89 : 97 :

C:\DATA\PHP>

プログラムの説明

  1. 配列 $array に0~99までの数を格納します。
    for($n=0; $n<100; $n++) $array[$n]= $n;
    
  2. 配列 $array から2~7までの倍数を取り除きます。
    for($i=2; $i<8; $i++)
    
    何故7までで良いかと言うと、本当は sqrt(100)=10 で10まで消し込めば良いのですが、10は2の倍数、9は3の倍数、8は2の倍数で、実質的に7で良いことになります。
    sqrt(100) の根拠は、もし a を割り切る整数 n が存在すると a = n * m で、n と m のどちらかは sqrt(a) より小さい値になるからです。
  3. $i を残して、$i の倍数を取り除きます。
    $j を $i+$i から始めて、$i ずつ配列 $array から取り除きます。
    {   for($j=$i+$i; $j<100; $j+= $i)   $array[$j]= 0;
    }
    
    1. テーブルに格納されている最初の値「2」は素数です。
      素数が見つかれば、その倍数をテーブルから取り除きます。
      2のときは「4,6,8,・・・98」を取り除きます。
      プログラムでは、取り除く代わりにゼロを格納します。
    2. 次に見つかる値は「3」なので「6,9,12,・・・99」を取り除きます。
    3. 4は2の倍数として取り除かれているので、次の値は「5」なのでその倍数を取り除きます。
    4. 7の倍数まで取り除けば残っている値は全て素数です。
  4. 配列 $array に残された数値(素数)を拾い出して印字します。
    for($n=2; $n<100; $n++)
        if ($array[$n]>1)   print($n . " : ");
    
  5. 1000までの素数を求めて下さい。
    1000までの素数の数は168個です。

前田稔の超初心者のプログラム入門
PHP Program