入力された自然数が素数か判定する

２以上の自然数において、その自然数が１とその自然数自身の他に約数が存在しない場合、その自然数は素数とも呼ばれます。素数か判定するには、数が大きくなるほど手計算では大変ですが、コンピューターにまかせれば、あっという間に判定できます。ただし、膨大な桁数の素数となると、コンピューターでも、その判定にかなり時間がかかってしまいます。

素数かどうか判定するには、まず、入力された自然数を、実際に２から、自然数より１小さい値まで割ってみて、割り切れるのかどうか調べます。 （２の場合は、割らずに素数と判定します。）もし、割り切れる事が起きれば（余りが０となる）、その自然数は素数ではありません。

以下は、入力された自然数が素数かどうか判定するプログラムソースコード例です。

#include <stdio.h>
 
int main(void)
{
    int i;        /* ループ処理用変数 */
    int flg;    /* 素数判定に使用（0なら素数） */
    int num;    /* 入力された自然数を格納 */
 
    flg = 0;    /* 0と初期化しておく */
 
    /* キーボードからの入力処理 */
    printf("素数判定をしたい自然数(2以上)を入力して下さい。\n");
    scanf("%d", &num);
 
    /* numを2からnum-1の整数で割り、約数が存在しないか調べるループ処理 */
    for(i = 2 ; i < num ; i++)
    {
        /* 1とnum自身の他に約数が存在したら素数と判定する処理 */
        if(num % i == 0)
        {
            flg = 1;    /* 素数ではないと判定されたので1を代入 */
        }
    }
 
    /* flg値が0なら素数である旨を表示 */
    if(flg == 0)
    {
        printf("入力された自然数 %d は、素数です。\n", num);
    }
    else
    {
        printf("入力された自然数 %d は、素数ではありません。\n", num);
    }
 
    return 0;
}

上記のプログラムをコンパイルし実行すると、 自然数の入力が求められます。入力すると、その数が素数かどうか判定され、結果が表示されます。

素数判定をしたい自然数(2以上)を入力して下さい。
7
入力された自然数 7 は、素数です。