Javaで素数をカウントしてみる

Javaで素数をカウントしてみる。
なんにも考えないで、ただ素数をカウント・列挙するプログラムを書いてみた。

// bubbleprimeと呼ぶことにする

import java.util.ArrayList;
    public static void main(String[] args){
        bubblePrime(1000);
    }
    private static void bubblePrime(int num) {
        System.out.println("bubblePrime実行します");
        long start = System.currentTimeMillis();
        ArrayList<Integer> primeList = new ArrayList<Integer>();
        int limitNum = num;
        for(int i = 0 ; i <= limitNum ; i++ ){
            int j ;
            for( j = 3  ; j < i ; j++ ){
                if(i % j == 0){
                    break;
                }
            }
            if(i == j)
                primeList.add(i);

        }
        long stop = System.currentTimeMillis();
        System.out.println(primeList.size()+"個でした");
        System.out.println(stop - start + "ミリ秒かかった");
        System.out.println("bubblePrime実行完了です。");
   }

このbubbleprimeはわかりやすいのだが、バブルソートと同じく実行が遅い。10万件程度なら、1,2秒で済むのでいいのだが、100万件とかにした途端に遅くなる。

wikipediaに素数を求める方法としてエラトステネスの篩というものがあるらしい。これによれば、4ステップの手順でてきるようだ。

ステップ 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 に戻る。

この順番でコードおを起こせば実行速度が速くなるみたいだ。そこで起こしてみる。

import java.util.LinkedList;
    public static void main(String[] args){
        bubblePrime(1000);
    }
    private static void eratosPrime(int num) {
        System.out.println("eratosPrime実行します");
        long start = System.currentTimeMillis();
        LinkedList<Integer> primeList = new LinkedList<Integer>();
        LinkedList<Integer> numberList = new LinkedList<Integer>();
        for (int i = 2; i < num; i++) {
            numberList.add(i);
        }
        int primeNum = numberList.getFirst();
        primeList.add(primeNum);
        for (int tmpNum : numberList) {
            for (int prime : primeList) {
                if (tmpNum % prime == 0) {
                    break;
                } else if (tmpNum < prime * prime) {
                    primeList.add(tmpNum);
                    break;
                }
            }
            
        }
        long stop = System.currentTimeMillis();
        System.out.println(primeList.size() + "個でした");
        System.out.println(stop - start + "ミリ秒かかった");
        System.out.println("eratosPrime実行完了です。");
    }

非効率な部分もあるが、速度は十分にでた。あと少々リファクタリングすればもう少し速度改善は期待できると思う。

- 1-100
bubblePrime:1ミリ秒
eratosPrime:1ミリ秒

- 1-1000
bubblePrime:3ミリ秒
eratosPrime:2ミリ秒

- 1-10000
bubblePrime:33ミリ秒
eratosPrime:19ミリ秒

- 1-100000
bubblePrime:1877ミリ秒
eratosPrime:47ミリ秒

- 1-1000000
bubblePrime:153443ミリ秒
eratosPrime:582ミリ秒

見ての通り数字が大きくなるほど差がでてくる。ソートとかもそうだけど、アルゴリズムってすごい。