Javaで素数を求めるプログラムを実装

エラトステネスの篩を利用した、1からNまでの素数を求めるプログラムをJavaで実装しました。

100万までの素数を求めたときの実行速度を計測してみたので、少しメモしておきます。

実行環境

OS：Windows 7 Professional
CPU：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

大分速くなりました！

アルゴリズムはやっぱり難しいです。
速く動くアルゴリズム思い付ける人って素直に尊敬します。

頑張ろう！