エラトステネスの篩

素数判定アルゴリズムのエラトステネスの篩というアルゴリズムを紹介します。
エラトステネスの篩は指定された値以下の素数を求めるアルゴリズムです。

まず、2から指定された数値までの整数の数列を作成します。

次に小さい方から数値を取り出し、印がついていなければそれを素数とします。

そして素数の倍数の数値すべてに素数でないことを示す印をつけます。

これを繰り返して最後に印がついていない数値が素数ということになります。

以下にサンプルのプログラムを示します。

sample/number/prime/PrimeSample.java

package sample.number.prime;

public class PrimeSample {

	public static void main(String[] arg) {

		boolean[] marks = new boolean[1024];
	
		// 素数でない数値に印をつける

		for (int i = 2; i < marks.length; i++)

			if (!marks[i])

				for (int j = i + i; j < marks.length; j += i)

					marks[j] = true;
		
		// 素数を表示する

		for (int i = 2; i < marks.length; i++)

			if (!marks[i])

				System.out.println(i);
	}
}

2010年6月22日 | カテゴリー：アルゴリズム