第５回 エラトステネスのふるい

エラトステネスのふるいとは、素数を見つけ出すための方法です。解説はwikipediaにおまかせです。wikipediaのgif動画はすごいですね。

<?php

function furui()
{
  // 作業テーブルの初期化。trueなら素数、falseなら素数でないとする。
  $array = array();
  for ($i = 0; $i <= 100; $i++) {
    $array[$i] = true;
  }

  // 0と1は素数の定義上、素数ではない。
  $array[0] = false;
  $array[1] = false;

  // 2以上について素数を探す。
  for ($n = 2; $n <= 100; $n++) {
    // $nは素数候補。$nの２倍から素数ではなくなる。
    for ($m = $n + $n; $m <= 100; $m += $n) {
      $array[$m] = false;
    }
  }

  // 素数一覧を整形して返す。
  $ret = array();
  for ($j = 0; $j <= 100; $j++) {
    if ($array[$j]) {
      $ret[] = $j;
    }
  }
  return $ret;
}

echo "実行結果：\n";
echo join(', ', furui()) . "\n";

実行結果は

実行結果：
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

計算量は より小さく より大きいですが……すみません、正確な数式がパッと出てこないです。$mのループを回す前に

    if($array[$n] == false) {
      continue;
    }

とすればもっと早くなります（たとえば$n = 4の場合、4の倍数は2の倍数なので、$n = 2のときのループで処理が終わっています。それは$array[$n] == falseで見つかります）。
素数を見つけるのに足し算だけでいける、というのはなかなか興味深いです。

配列を使ったアルゴリズムはメモリを使う代わりに問題をすんなりと解かせてくれることが多いです。「A+D=P」という言葉がありますが、「Algorithms + Data Structures = Programs」（アルゴリズム＋データ構造＝プログラム）の略です。プログラムは処理（≒手順＝アルゴリズム）をガリガリ書くだけでは分かりにくくなりがちです。適切なデータ構造と組み合わせることで分かりやすく処理の速いプログラムになります。どういうデータ構造なら処理がしやすいか、を考えるのは設計のアプローチの１つで、データベース設計が重要な所以です。

次回からは探索アルゴリズムです。次回はデータ構造を考えない の「力まかせ探索（フルスキャン）」、次々回はデータの並びを利用した の「二分探索（バイナリサーチ）」、その次はデータ構造に工夫を持たせた の「ハッシュテーブル」です。