【C言語入門】数値が素数かどうかを判定するプログラムの書き方

素数とは何か？

素数とは、「1とその数自身」の2つの数でしか割り切れない数のことです。ここでいう「約数」とは、その数を余りなく割り切ることができる数を指します。

最初の10個の素数は「2、3、5、7、11、13、17、19、23、29」です。

素数ではない数は合成数と呼ばれます。合成数とは、2つ以上の約数を持つ数のことです。

さらに、1は素数でも合成数でもありません。1の約数は1自身のみであり、約数が2つ存在しないためです。

素数であるための2つの条件

ある数が素数かどうかを判定するには、以下の2つの条件を確認します。

1. 1より大きい整数であること
2. 約数が「1」と「その数自身」のちょうど2つだけであること

この2つの条件を両方とも満たしていれば、その数は素数であると言えます。

判定の基本的なロジック

プログラムでは、対象の数より小さい数で順番に割り算を行います。もし1つでも割り切れる数が見つかれば、その数は素数ではありません。逆に、どこまで試しても割り切れなければ、それは素数です。

実際に2つの数を例にとって、この手順で素数かどうかを確認してみましょう。

例1：42の場合

入力 − Number1 − 42
出力 − 42 は素数ではない

ロジック：42を、1より大きく42未満のすべての数で割っていきます。

42 ÷ 2 = 21 となり、42は2で割り切れます。つまり、42は自分自身と1以外の数でも割り切れるため、素数ではありません。

例2：7の場合

入力 − Number2 − 7
出力 − 7 は素数である

ロジック：7を、1より大きく7未満のすべての数で割っていきます。

• 7は2で割り切れない → 次の数3をチェック
• 7は3で割り切れない → 次の数4をチェック
• 7は4で割り切れない → 次の数5をチェック
• 7は5で割り切れない → 次の数6をチェック
• 7は6で割り切れない → チェック終了

この結果、7は1と7でしか割り切れないことがわかります。したがって、7は素数です。

計算時間の問題と最適化の考え方

上記のロジックのままでは、数が1000や100000といった大きな値になった場合、forループがその分だけ繰り返され、非常に多くの計算時間が必要になってしまいます。そこで、反復回数を減らすためのより効率的な方法が求められます。

最適化された解決策のひとつが、「ループを半分までしか実行しない」という方法です。たとえば数が77なら、ループは38までしか回りません。これにより必要な反復回数が大幅に削減されます。以降はこのアルゴリズムを使ってプログラムを作成します。

なお、数学的には「√num（numの平方根）まで調べれば十分」とさらに最適化できますが、ここでは理解しやすい「半分まで調べる」方法を採用します。

C言語による実装例

#include <stdio.h>
int main() {
    int num = 33, flag = 0;
    for(int i=2 ; i < num/2 ; i++) {
        if(num%i == 0) {
            printf("%d is not a prime number", num);
            flag = 1;
            break;
        }
    }
    if(flag == 0) {
        printf("%d is a prime number", num);
    }
}

このプログラムでは、変数flagを「素数かどうかの目印」として使っています。途中で割り切れる数が見つかった時点でflagを1にし、break文でループを抜けます。ループ終了後もflagが0のままであれば、一度も割り切れなかったということなので、その数は素数だと判断できます。

出力結果

33 is not a prime number

この例ではnumに33を代入しています。33は3で割り切れる（33 ÷ 3 = 11）ため、素数ではなく合成数です。プログラムを実行すると、i=3の時点で33が割り切れることが検出され、「33 is not a prime number（33は素数ではない）」と表示されます。