C++で配列内の素数の個数を数える方法

本記事では、整数の配列が与えられたときに、その配列に含まれる素数の個数をC++で求める方法を解説します。

素数とは、1とその数自身でのみ割り切れる数のことです。つまり、約数がちょうど2つしかない数を指します。配列の先頭要素から末尾要素まで順番に素数かどうかを判定し、素数が見つかるたびにカウントを増やしていきます。

ある数Nが素数かどうかを判定するには、2からN/2までの範囲にある数でNが割り切れるかどうかを確認します。1つでも割り切れる数が存在すればNは素数ではなく、どこでも割り切れなければNは素数です。

具体例で理解しましょう。

入力 − arr[]= { 1,2,3,4,5,6,7,8,9 }

出力 − 素数の個数 − 4

説明 − このうち2、3、5、7が素数で、1、4、6、8、9は素数ではありません。

入力 − arr[]= { 11,12,4,61,23 }

出力 − 素数の個数 − 3

説明 − このうち11、61、23が素数で、12、4は素数ではありません。

プログラムのアプローチ

• ランダムな整数を格納した配列arr[]を用意します。

• 関数checkPrime(int num)は、引数として渡された数numが素数かどうかを判定します。素数であれば1を、そうでなければ0を返します。

• numが1以下の場合は素数ではないため、0を返します。

• 2からnum/2までの範囲で、numを割り切れる数(num % i == 0)が1つでもあれば、numは素数ではないので0を返します。

• それ以外の場合は1を返します。

• 変数isprimeは、その数が素数かどうかを表します(1なら素数)。

• 変数countは、配列arr[]内の素数の個数を保持します。

• main関数内では配列全体を走査し、各要素arr[i]をcheckPrime(arr[i])に渡します。戻り値が1(isprime == 1)であればcountをインクリメントします。

• 最終的にcountには、配列arr[]内の素数の個数が格納されます。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
// 数が素数かどうかを判定する関数
int checkPrime(int num){
    // 1以下の数は素数ではない
    if (num <= 1)
        { return 0; }
    // 2からnum/2まで順に割り切れるか確認する
    for (int j = 2; j <= num/2; j++){
        if (num % j == 0){
            return 0;
        }
    }
    // 割り切れる数がなければ素数
    return 1;
}
int main(){
    int arr[] = { 1,3,5,4,8,13,11 };
    int n = 7;
    int count=0;
    int isprime=0;
    for(int i=0;i<n;i++){
        isprime=checkPrime(arr[i]);
        if(isprime==1)
            count++;
    }
    cout<<"Count of number of primes in array : "<<count;
    return 0;
}

補足： 元のコードでは「return 1;」がforループの内部に配置されていたため、最初の除算チェックだけで関数が終了してしまい、正しく判定できないケースがありました。上記のコードでは「return 1;」をループの外に移動し、すべての候補を確認した後に素数と判定するよう修正しています。

出力

上記のコードを実行すると、次の出力が生成されます −

Count of number of primes in array : 4