関数を使って素数を判定するC++プログラムの作成方法

素数とは、1より大きい整数であり、約数が「1」と「その数自身」のみである数のことを指します。言い換えれば、素数はそれ以外のどの整数でも割り切ることができません。

最初のいくつかの素数は以下の通りです。

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

本記事では、関数を使用してある数値が素数かどうかを判定するC++プログラムについて解説します。

サンプルコード

#include <iostream>
using namespace std;
void isPrime(int n) {
    int 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"<<endl;
    else
    cout<<n<<" is not a prime number"<<endl;
}
int main() {
    isPrime(17);
    isPrime(20);
    return 0;
}

実行結果

17 is a prime number
20 is not a prime number

プログラムの仕組み

このプログラムでは、isPrime() 関数を使って、引数として渡された数値 n が素数かどうかを判定します。判定の流れは以下の通りです。

1. 割り算による判定

2から n/2(n の半分)までの範囲でループを実行し、それぞれの値で n を順番に割っていきます。もし割り算の剰余が0になった場合、それは n が1でも自身でもない別の数で割り切れることを意味します。つまり、その数は素数ではないため、フラグ変数に1を設定し、break 文でループを抜け出します。該当するコード部分は以下の通りです。

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

2. フラグ変数による結果の出力

ループ終了後、フラグ変数の値を確認します。flag の値が0のまま(一度も割り切れなかった)であれば、その数は素数であることが分かり、その旨を出力します。逆に flag の値が1に変更されていれば、その数は素数ではないため、そう表示します。

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

main() 関数からの呼び出し

main() 関数内では、isPrime() 関数に対して17と20という2つの異なる値を渡して呼び出しています。これにより、それぞれの数値が素数かどうかの判定結果が出力されます。

isPrime(17);
isPrime(20);

実行結果を見ると、17は素数として、20は素数ではない(2や4などで割り切れるため)として正しく判定されていることが確認できます。