Aritalab:Lecture/Algorithm/Eratosthenes
From Metabolomics.JP
エラトステネスのふるい
ここでは素数をみつける最も簡単なアルゴリズム、「エラトステネスのふるい」を考えましょう。 まず動作のアニメーションとして日本語版ウィキペディアの記事「エラトステネスの篩」をみてください。
アルゴリズム1
なぜ x の平方根までで十分なのか |
---|
x の平方根を超える数 y が素数でない場合、y = ab という形に書けるはず。しかし a か b どちらかは x 以下になるので、既に除かれています。 |
- 探索リストに 2 から x までの整数を並べる。
- 探索リストの先頭の数を素数リストに移動し、その倍数を探索リストから除く。
- 上記の操作を探索リストの先頭値が x の平方根に達するまで行う。
- 探索リストに残った数を素数リストに移動して終了。
このアルゴリズムの利点は x の平方根まで計算するだけで x 以下の素数を全て得られるところです。しかしサイズ x の列をあらかじめ用意しなくてはなりません。1億以下の素数を求めるのにサイズ1億の列を用意はできません。
アルゴリズム2
- 素数リストに2を入れる。
- 2から x までの数 a について昇順に以下を繰り返す。
- a が素数リストにある数で割り切れるかチェック。
- 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 が求まります。