Aritalab:Lecture/Algorithm/Eratosthenes

エラトステネスのふるい

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

アルゴリズム1

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

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

このアルゴリズムの利点は x の平方根まで計算するだけで x 以下の素数を全て得られるところです。しかしサイズ x の列をあらかじめ用意しなくてはなりません。100万以下の素数を求めるからといって、サイズ100万の列を用意するのはスペースの無駄です。そこで改良版を考えます。

アルゴリズム2

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

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

プログラム

以下のコードはJavaでそのまま実行できます。数字にLがついているのは long 指定で64ビット整数を使うためです。

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 < 1000000L; c = c + 2L) {
      boolean flag = true;
      for (int i = 0; i < V.size(); i++) {
        long p = V.get(i);
        if (c < p * p)
          break;
        if (c % p == 0) {
          flag = false;
          break;
        }
      }
      if (flag)
        V.addElement(c);
    }
  System.out.println(V.elementAt(V.size() - 1));
  }
}

このプログラムを走らせると、2秒で100万以下の最大の素数 999,983 が求まりました（ThinkPadX230 非力なノートPCです）。素数のリストが記載されている外部のウェブページ をみても正しいことがわかります。

もっと大きな素数の求め方

素数は数直線上にほぼ満遍なく分布しており、数が大きくなっても素数の割合はあまり変わりません。2013年、カナダ・モントリオール大のジェームズ・メイナードと、米カリフォルニア大のテレンス・タオが独立に「素数が2個含まれる幅 600 の区間が無限個存在する」ことを証明しています。大きな素数をエラトステネス手法で求めるのは、素数リストが大きくなるので不適切ということです。

では1742万5170桁の素数といった、「最大の素数」はどうやって求めるのでしょう？これはメルセンヌ数の形になる素数だけを相手にしているからです。