Javaで素数を求めるプログラムを実装
エラトステネスの篩を利用した、1からNまでの素数を求めるプログラムをJavaで実装しました。
100万までの素数を求めたときの実行速度を計測してみたので、少しメモしておきます。
実行環境
OS:Windows 7 ProfessionalCPU:Intel Core i7-3770 3.40GHz
Java:1.8.0_40
最初に、そのまま実装したコードです。
実装コード
import java.util.Iterator; import java.util.LinkedList; /** * エラトステネスの篩を利用して、素数を調べる */ public class PrimeChecker1 { /** * 1からnまでの素数をリストで返す * @param n * @return */ private void check(int n) { Timer timer = new Timer(); timer.start(); LinkedList<Integer> searchNumberList = new LinkedList<>(); LinkedList<Integer> primeList = new LinkedList<>(); // 探索リスト生成 for(int i=2; i<=n; i++){ searchNumberList.add(i); } do{ // 探索リストの先頭を素数として取り出す int prime = searchNumberList.poll(); primeList.add(prime); // 取り出した素数の倍数を探索リストから削除 Iterator<Integer> ite = searchNumberList.iterator(); while(ite.hasNext()){ if(ite.next() % prime == 0){ ite.remove(); } } }while(primeList.getLast() < Math.sqrt(n)); // 残った探索リストの数字を素数としてリストに追加 primeList.addAll(searchNumberList); for(int prime : primeList){ System.out.println(prime); } timer.stop(); } public static void main(String[] args){ new PrimeChecker1().check(1000000); } } /** * 時間の計測クラス */ class Timer{ private long startTime; public void start(){ startTime = System.currentTimeMillis(); } public void stop(){ long time = System.currentTimeMillis() - startTime; System.out.println("実行時間 : "+time+"ms"); } }
実行結果(結果の表示有り)
(省略) 999961 999979 999983 実行時間 : 1343ms
実行結果(結果の表示無し)
実行時間 : 766ms
結果を表示して、1.3秒ほど掛かっています…
友達に「booleanの配列使えば、速くできるよ」と教えてもらったので、コードを改善してみました。
booleanの配列を利用して改善した実装コード
import java.util.Arrays; /** * エラトステネスの篩を利用して、素数を調べる * @author tomohiro * */ public class PrimeChecker2 { /** * 1からnまでの素数をリストで返す * @param n * @return */ private void check(int n) { Timer timer = new Timer(); timer.start(); // 探索リスト生成 boolean[] search = new boolean[n+1]; Arrays.fill(search, true); // 素数でないものはfalseにする for(int i=2; i<Math.sqrt(n); i++){ // 素数の倍数なら何もしない if(!search[i]){ continue; } // 素数の倍数をふるい落とし for(int j=2; i*j <= n; j++){ search[i*j] = false; } } for(int i=2; i<search.length; i++){ if(search[i]){ System.out.println(i); } } timer.stop(); } public static void main(String[] args){ new PrimeChecker2().check(1000000); } } /** * 時間の計測クラス */ class Timer{ private long startTime; public void start(){ startTime = System.currentTimeMillis(); } public void stop(){ long time = System.currentTimeMillis() - startTime; System.out.println("実行時間 : "+time+"ms"); } }
実行結果(結果の表示有り)
(省略) 999961 999979 999983 実行時間 : 551ms
実行結果(結果の表示無し)
実行時間 : 16ms
大分速くなりました!
アルゴリズムはやっぱり難しいです。
速く動くアルゴリズム思い付ける人って素直に尊敬します。
頑張ろう!