エラトステネスの篩（エラトステネスのふるい）は素数判定法の一種で、指定された整数以下の全ての素数を発見するための単純なアルゴリズムである。古代ギリシアの科学者、エラトステネスが考案したとされるため、この名がある。 ※Wikipediaより
Wikipediaさんを参考にエラトステネスの篩で素数を求めるプログラムを作ってみようと思います
まず手順 Wikipediaさんのそのままですが・・・ｗ
1
整数を最初の素数である 2 から昇順で探索リストに羅列する。
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
2
リストの先頭の数を素数リストに記録する。
素数リスト：2
探索リスト：2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
3
前のステップで素数リストに加えられた数の全ての倍数を、探索リストから削除する。
素数リスト：2
探索リスト：3 5 7 9 11 13 15 17 19
4
探索リストの最大値が素数リストの最大値の平方よりも小さい場合、素数リストおよび探索リストに残っている数が素数となる。探索リストの最大値が素数リストの最大値の平方よりも大きい場合、ステップ 2 に戻る。
19 は 2 の平方よりも大きいので、ステップ 2 に戻る。
2
素数リスト：2 3
探索リスト：3 5 7 9 11 13 15 17 19
3
素数リスト：2 3
探索リスト：5 7 11 13 17 19
4
19 は 3 の平方よりも大きいので、ステップ 2 に戻る。
2
素数リスト：2 3 5
探索リスト：5 7 11 13 17 19
3
素数リスト：2 3 5
探索リスト：7 11 13 17 19
4
19 は 5 の平方よりも小さいので、リストに残っている数が素数である。
結果：2 から 20 までの数に含まれる素数は、
2 3 5 7 11 13 17 19
この手順の通りにJavaで書いてみた
import java.util.Iterator;
import java.util.LinkedList;
public class Eratosthenes {
static LinkedList primes = new LinkedList(); //素数リスト
static LinkedList numbers = new LinkedList(); //探索リスト
static int N = 100000; //Nまでの素数を求める
public static void main(String[] args) {
//1.整数を最初の素数である 2 から昇順で探索リストに羅列する。
for(int i = 2; i <= N; i++){
numbers.add(i);
}
int prime;
Iterator it;
do{
//2.リストの先頭の数を素数リストに記録する
prime = numbers.getFirst();
primes.add(prime);
//3.前のステップで素数リストに加えられた数の全ての倍数を、探索リストから削除する
it = numbers.iterator();
while(it.hasNext()){
if(it.next() % prime == 0) it.remove();
}
//4.探索リストの最大値が素数リストの最大値の平方よりも大きい場合、ステップ 2 に戻る
}while(numbers.getLast() > prime*prime);
//4.探索リストの最大値が素数リストの最大値の平方よりも小さい場合、素数リストおよび探索リストに残っている数が素数となる
it = numbers.iterator();
while(it.hasNext()){
primes.add(it.next());
}
}
}
本当に手順そのまま書けたｗ
もうちょっと改善の余地がありそうだけど、手順通りのほうが理解しやすいしよほど効率が求められない限りこれで十分かな
覚えとこー
