MIN から MAX までの素数をプリントするプログラムです。
素数判定のアルゴリズムにはいろいろなものがありますが、ここで紹介するのは一番単純な「試し割り」での方法です。
割り算回数の節約 その(1)
偶数はすべて 2で割り切れるので、2以外の偶数は素数ではありません。
3以上の奇数についてだけ試し割りをすればよいことになります。
割り算回数の節約 その(2)
もう少し効率化を考えると、x-1 まで調べなくても √x まで調べれば割り切れるかどうかが分かります。
(※ 理由と例は下で示します)
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 で ・・・ )