Aritalab:Lecture/Algorithm/Eratosthenes

エラトステネスのふるい

ここでは素数をみつける最も簡単なアルゴリズム、「エラトステネスのふるい」を考えましょう。 まず動作のアニメーションとして日本語版ウィキペディアの記事「エラトステネスの篩」をみてください。

アルゴリズム1

なぜ x の平方根までで十分なのか
x の平方根を超える数 y が素数でない場合、y = ab という形に書けるはず。しかし a か b どちらかは x 以下になるので、既に除かれています。

1. 探索リストに 2 から x までの整数を並べる。
2. 探索リストの先頭の数を素数リストに移動し、その倍数を探索リストから除く。
3. 上記の操作を探索リストの先頭値が x の平方根に達するまで行う。
4. 探索リストに残った数を素数リストに移動して終了。

このアルゴリズムの利点は x の平方根まで計算するだけで x 以下の素数を全て得られるところです。しかしサイズ x の列をあらかじめ用意しなくてはなりません。1億以下の素数を求めるのにサイズ1億の列を用意はできません。

アルゴリズム2

1. 素数リストに2を入れる。
2. 2から x までの数 a について昇順に以下を繰り返す。
   1. a が素数リストにある数で割り切れるかチェック。
   2. a の平方根以下の素数で割り切れなかったら素数リストに追加。

この利点は探索リストが不要なところです。これなら大きい素数もすぐわかります。実際にJavaで書いてみましょう。

import java.util.Vector;

public class Eratosthenes {
  static public void main(String[] args) {
    Vector<Long> V = new Vector<Long>();
    V.addElement(2L);
    for (long c = 3L; c < 1000000; c = c + 2L) {
      boolean flag = true;
      for (int i = 0; i < V.size(); i++) {
        long p = V.get(i);
        if (Math.sqrt(c) < p)
          break;
        if (c % p == 0) {
          flag = false;
          break;
        }
      }
    if (flag)
      V.addElement(c);
    }
  System.out.println(V.elementAt(V.size() - 1));
  }
}

このプログラムを走らせると、ノートPC 2秒程度で100万以下の最大の素数 999,983 が求まります。