演習(エラトステネスの篩)の回答例

出典: CourseWiki

/*
 * エラトステネスの篩 
 */
public class Eratosthenes {
    public static void main(String[] args) {
        // 素数だけ true にした配列を得る 
        boolean[] sieve = sieve(1000);
        
        // 素数の表示
        int n = 0;
        for (int i = 2; i < sieve.length; i++) {
            if (sieve[i]) {
                System.out.print(i);
                n++;
                if (n % 10 == 0) {
                    System.out.println();
                } else {
                    System.out.print(" ");
                }
            }
        }
        System.out.println();
    }
    
    /*
     * エラトステネスの篩のアルゴリズムを用いてnまでの素数表を求める.
     * 返り値は n 個の要素を持つ boolean 型の配列.
     * (i (0 <= i < n) が素数ならば配列のi番目の要素が true になっている)
     */
    private static boolean[] sieve(int n) {
        // i が素数なら isprime[i] == true になる配列
        boolean[] isprime = new boolean[n];
 
        // とりあえず,一旦全部素数としてマークする
        for (int i = 0; i < isprime.length; i++) {
            isprime[i] = true;
        }
 
        // 0 と 1 は素数ではない
        isprime[0] = false;
        isprime[1] = false;
        
        // 次の for 文で,p をどこまで動かすか.
        // for (int p = 2; p < n; p++) でも良いが,実際は n の平方根までで構わないので,
        // max に平方根を代入している.Math.sqrt は平方根を求めるメソッド.
        int max = (int)Math.sqrt(isprime.length);
        // 最小の素数2から始めて,配列上で,素数の倍数を false にマークする
        for (int p = 2; p <= max; p++) {
            // System.out.println(java.util.Arrays.toString(isprime));
            // p が素数ならば
            if (isprime[p]) {
                // System.out.println("Found Prime Number: " + p);
                // pの倍数を「素数でない」(false) とする
                for (int i = p * 2; i < isprime.length; i += p) {
                    // System.out.println("  Marking: " + i);
                    isprime[i] = false;
                }
            }
        }
        return isprime;
    }
}

途中にあるコメントアウトされた System.out.println(..) は,動作を理解するためのものです. うまく書けなかった人はコメントを外して実行してみると良いでしょう.

また,デバッグの際にもこのような文を付け加えると,問題解決のヒントになることが多いです.

for文の中にあるif文のチェックはなくても動きますが,あったほうが効率が良いです. (pが素数でないときは,既にpの全ての倍数はfalseになっているはずなので,内側のfor文を実行する意味はありません.)

p は,2 から prime.length (=n) の平方根まで動かしています.なぜ平方根までで良いのかは考えてください.

平方根まで動かすとき,

for (int p = 2; p < max; p++) 

では駄目で

for (int p = 2; p <= max; p++) 

にする必要があります.

例えば n = 1000 の場合,\sqrt{1000} = 31.622.. なので max = 31 になります.p < max だと p が 30 までしか動かないため, 31 * 31 = 961 が素数になってしまいます.

ナビゲーション