C++で数値が素数かどうかを判定するプログラムの作成方法

素数とは？

素数（そすう）とは、1より大きい整数のうち、約数が「1」と「その数自身」のみである数のことです。最初の方の素数には以下のようなものがあります。

2, 3, 5, 7, 11, 13, 17

ここでは、入力された数値が素数かどうかを判定するC++プログラムを紹介します。

サンプルプログラム

#include <iostream>
using namespace std;
int main() {
    int n=17, i, flag = 0;
    for(i=2; i<=n/2; ++i) {
        if(n%i==0) {
            flag=1;
            break;
        }
    }
    if (flag==0)
    cout<<n<<" is a prime number";
    else
    cout<<n<<" is not a prime number";
    return 0;
}

実行結果

17 is a prime number

プログラムの解説

上記のプログラムでは、2からnの半分（n/2）まで繰り返し処理を行うforループを使用しています。nは素数かどうかを判定したい数値です。

ループの中では、各値でnを割り算し、余りを確認します。もし余りが0になった場合、その数値は「1」と「自分自身」以外の数でも割り切れることになるため、素数ではありません。このとき、フラグ変数flagに1を設定し、break文でループを即座に抜けます。

for(i=2; i<=n/2; ++i) {
    if(n%i==0) {
        flag=1;
        break;
    }
}

ループ終了後、flagの値によって判定結果を表示します。

• flagが0のままの場合： どの数値でも割り切れなかったため、nは素数です。
• flagが1に変わった場合： 割り切れる数値が存在したため、nは素数ではありません。

if (flag==0)
cout<<n<<" is a prime number";
else
cout<<n<<" is not a prime number";

補足：より効率的な判定方法

n/2まで調べる方法はシンプルで分かりやすい一方、大きな数値に対しては無駄な計算が発生します。数学的には、ある数の約数は必ず√n以下の範囲に存在するため、ループ条件を i*i <= n や i <= sqrt(n) に変更すると、計算量を大幅に減らせます。大規模な数値を扱う場合は、この最適化を検討するとよいでしょう。