Thinkers'Studio
JavaとC言語の自習ツール
素数判定のプログラム例(Java版)

 MIN から MAX までの素数をプリントするプログラムです。
 素数判定のアルゴリズムにはいろいろなものがありますが、ここで紹介するのは一番単純な「試し割り」での方法です。

試し割りによる素数判定

 素数かどうか判定する自然数(正の整数)を x とします。
 素数は、 1 と自分自身でしか割り切れない数ですから、x を 2 から x-1 までの正の整数で試し割りします。
 「割り切れるものがなければ素数」です。

 割り算回数の節約 その(1)
 偶数はすべて 2で割り切れるので、2以外の偶数は素数ではありません。
 3以上の奇数についてだけ試し割りをすればよいことになります。

 割り算回数の節約 その(2)
 もう少し効率化を考えると、x-1 まで調べなくても √x まで調べれば割り切れるかどうかが分かります。
 (※ 理由と例は下で示します)

素数判定のプログラム例 】
 素数判定するメソッドを isPrimeNum として作成すると、次のようなプログラムとなります。
public class PrimeNum {
    final static int MIN = 100, MAX = 500;

    //xが素数か判定する
    static boolean isPrimeNum( int x ) {
        if( x == 2 ) return true;
        if( x < 2 || x % 2 == 0 ) return false;
        for( int n = 3; n <= Math.sqrt((double)x); n += 2 )
            if( x % n == 0 ) return false;
        return true;
    }
    public static void main( String[] args ) {
        int cnt = 0;

        System.out.println( MIN+"から"+MAX+"までの素数" );
        for( int n = MIN; n <= MAX; n++  ) {
            if( isPrimeNum( n ) ) {
                System.out.print( n + " " );
                if( ++cnt%5==0 ) System.out.println();
            } 
        }
    }
}
実行結果
100から500までの素数
101 103 107 109 113
127 131 137 139 149
(途中略)
467 479 487 491 499

※ √x まで調べればよい理由
 √x より大きい値で割り切れるなら、その商 q は √x より小さい値です(√x より大きな値の積は x より大きくなってしまいます)。 ですから、q を調べたときにすでに判定できているはずです。
   (例)x が 42 だとすると √42 は 6.4807 ...
      √42 超の割り切れる値は 7, 14, 21、その商はそれぞれ 6, 3, 2 ( 7*6=42, 14*3=42, 21*2=42 )。

(今週のクイズです)
 上の isPrimeNum メソッドを使って、100万を超えない最大の素数を表示するプログラムを書きなさい。
 効率の工夫をした main を考えてみましょう。
  (答えは、次回の Java の Tips で ・・・ )

 前回 クイズはありませんでした。