■ 素数(Initial number)とは
* 1より大きい整数の内、1と自分自身以外の整数では割り切れないような整数をいう(1は含まない)
■ サンプル
例１：普通に求める
SampleInitialNumber1.java
public class SampleInitialNumber1 {
public static void main(String[] args) {
long start = System.currentTimeMillis();
// 0 - 100000までの素数を出力する
int num = 100000;
// 除算の回数
int counter = 0;
// 素数の数をカウント
int initialCount = 0;
for (int i = 2; i <= num; i++) {
int j;
for (j = 2; j < i; j++) {
counter++;
if (i % j == 0) {
// 割り切れると素数ではなく、それ以上の繰返しは不要
break;
}
}
if (i == j) {
// 最後まで割り切れなかった
initialCount++;
System.out.println(i);
}
}
System.out.println("素数の数：" + initialCount);
System.out.println("除算を行った回数：" + counter);
long stop = System.currentTimeMillis();
System.out.println("実行時間 : " + (stop - start) + "[ミリ秒]");
}
}
出力結果
...
99991
素数の数：9592
除算を行った回数：455189150
実行時間 : 2063[ミリ秒]
例２：エラトステネスの篩(ふるい)
エラトステネスの篩(Sieve of Eratosthenes）とは
=> ある数までの素数を探す場合、その数の平方根より小さい素数の倍数を消せば、残った数が素数である
例：100までの素数を探す
=> 100の平方根(√100)は、10である
=> 10までの素数は、「2、3、5、7」である
=> 2の倍数(2,4,...,100)、3の倍数(3,6,...,99)、5の倍数(5,10,...,100)、7の倍数(7,14,...,98)を消していく
=> その残りが、100までの素数（2、3、5、7、11、13、・・・）である
消していく様子を、ふるいに掛けている感じ。
手順
[1] ある数までの全整数データを用意する(例：10以下の整数データを用意する)
[2] 平方根以下の素数の倍数を取り除く(例：10の平方根(√10≒3.16)までの倍数を取り除く)
[3] 最後まで残った数を素数として出力する(例：残った数を出力する)
SampleInitialNumber2.java
public class SampleInitialNumber2 {
public static void main(String[] args) {
long start = System.currentTimeMillis();
// 0 - 100000までの素数を出力する
int num = 100000;
// 素数の数をカウント
int initialCount = 0;
boolean[] areInitialNumbers = new boolean[num];
// 初期化(初めは素数であるとする)
for (int i = 2; i < num; i++) {
areInitialNumbers[i] = true;
}
// ふるいにかける
for (int i = 2; i < num; i++) {
if (!areInitialNumbers[i]) {
continue;
}
for (int j = 2 * i; j < num; j += i) {
// 素数じゃない
areInitialNumbers[j] = false;
}
}
// 出力
for (int i = 2; i < num; i++) {
if (areInitialNumbers[i]) {
initialCount++;
System.out.println(i);
}
}
long stop = System.currentTimeMillis();
System.out.println("素数の数：" + initialCount);
System.out.println("実行時間 : " + (stop - start) + "[ミリ秒]");
}
}
出力結果
...
99991
素数の数：9592
実行時間 : 256[ミリ秒]
