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

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

試し割りによる素数判定

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

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

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

素数判定のプログラム例 】
 素数判定する関数を isPrimeNum として作成すると、次のようなプログラムとなります。
#include <stdio.h>
#include <math.h>
#define MAX 500

// xが素数か判定する(素数なら1, 非素数は0)
int isPrimeNum( int x )
{
    int n;

    if( x == 2 ) return 1;
    if( x < 2 || x % 2 == 0 ) return 0;
    for( n = 3; n <= sqrt((double)x); n += 2 )
        if( x % n == 0 ) return 0;
    return 1;
}

main()
{
    int n, cnt = 0;

    printf( "%dまでの素数\n", MAX );
    for( n = 1; n <= MAX; n++  ) {
        if( isPrimeNum( n ) ) {
            printf( "%3d%c", n, (++cnt%5==0) ? '\n' : ' ' );
        }
    }
    printf( "\n" );
    printf( "%d個ありました\n", cnt );
}
実行結果
500までの素数
  2   3   5   7  11
 13  17  19  23  29
 31  37  41  43  47
 53  59  61  67  71
(途中略)
467 479 487 491 499

95個ありました

※ √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 を考えてみましょう。

 (答えは、次回のC言語の Tips で)
 前回 クイズはありませんでした。