素数判定アルゴリズムの実行速度比較(Java) - 三十路エンジニアの備忘録+α

BohYoh.com【著書】明解Javaによるアルゴリズムとデータ構造の2章の素数列挙プログラムを少しだけ書き換え、実行速度を計ってみた。
全部で3通り。ソースコードは以下の通り。

//PrimeNumber1.java
// 100,000以下の素数を列挙(1)

class PrimeNumber1 {

    public static void main(String[] args) {
        long start = System.currentTimeMillis();

        int counter = 0;        // 除算の回数

        for (int n = 2; n <= 100000; n++) {
            int i;
            for (i = 2; i < n; i++) {
                counter++;
                if (n % i == 0) // 割り切れると素数ではない
                    break;          // それ以上の繰返しは不要
            }
            if (n == i)             // 最後まで割り切れなかった
                System.out.println(n);
        }

        System.out.println("除算を行った回数：" + counter);

        long stop = System.currentTimeMillis();
        System.out.println("実行にかかった時間は " + (stop - start) + " ミリ秒です。");
    }
}

//PrimeNumber2.java
// 100,000以下の素数を列挙(2)

class PrimeNumber2 {

    public static void main(String[] args) {
        long start = System.currentTimeMillis();

        int counter = 0;                    // 除算の回数
        int ptr = 0;                        // 得られた素数の個数
        int[] prime = new int[500000];  // 素数を格納する配列

        prime[ptr++] = 2;           // ２は素数である
        prime[ptr++] = 3;           // ３は素数である

        for (int n = 5; n <= 100000; n += 2) {      // 対象は奇数のみ
            int i;
            for (i = 1; i < ptr; i++) { // 既に得られた素数で割ってみる
                counter++;
                if (n % prime[i] == 0)      // 割り切れると素数ではない
                    break;                      // それ以上の繰返しは不要
            }
            if (ptr == i)                       // 最後まで割り切れなかったら
                prime[ptr++] = n;               // 素数として配列に登録
        }

        for (int i = 0; i < ptr; i++)       // 求めたptr個の素数を表示
            System.out.println(prime[i]);

        System.out.println("除算を行った回数：" + counter);

        long stop = System.currentTimeMillis();
        System.out.println("実行にかかった時間は " + (stop - start) + " ミリ秒です。");
    }
}

//PrimeNumber3.java
// 100,000以下の素数を列挙(3)

class PrimeNumber3 {
    public static void main(String[] args) {
        long start = System.currentTimeMillis();

        int counter = 0; //乗除算の回数
        int ptr = 0; //得られた素数の数
        int[] prime = new int[500000]; //素数を格納する配列

        prime[ptr++] = 2; //素数2を登録
        prime[ptr++] = 3; //素数3を登録

        for (int n = 5; n <= 100000; n += 2) { //対象は奇数のみ
            boolean wflag = false; //割り切れたかどうか
            for (int i = 1; prime[i] * prime[i] <= n; i++) {
                // 対象の数の平方根以下の全ての素数で除算する
                counter +=2;
                if (0 == n % prime[i]) { //割り切れたら素数ではない
                    wflag = true;
                    break;
                }
            }
            if (!wflag) { //最後まで割り切れなかったら
                prime[ptr++] = n; //素数として新たに登録
                counter++; //最後にループに入らなかった分
            }
        }

        for (int i = 0; i < ptr; i++)  //求めたptr個の素数を表示
            System.out.println(prime[i]);

        System.out.println("除算を行った回数: " + counter);

        long stop = System.currentTimeMillis();
        System.out.println("実行にかかった時間は " + (stop - start) + " ミリ秒です。");
    }
}