C++で配列内の合成数の個数と合計を求める方法

正の整数からなる配列が与えられたとき、その配列に含まれる合成数の個数と合計を求めるのが本記事の課題です。

合成数とは

与えられた整数の集合のうち、素数ではない数を「合成数」と呼びます。ただし、1は合成数でも素数でもなく、「単位数（ユニット）」という特別な数に分類されます。したがって、1を除くすべての整数は、必ず素数か合成数のどちらかに分類されることになります。

100までの合成数は以下の通りです。

4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 
26, 27, 28, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 
45, 46, 48, 49, 50, 51, 52, 54, 55, 56, 57, 58, 60, 62, 
63, 64, 65, 66, 68, 69, 70, 72, 74, 75, 76, 77, 78, 80, 
81, 82, 84, 85, 86, 87, 88, 90, 91, 92, 93, 94, 95, 96, 
98, 99, 100

具体例

入力 − array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
出力 − 合成数の個数：5
　　　 合成数の合計：37

解説 − 配列に含まれる合成数は4, 6, 8, 9, 10の5つです。したがって、個数は5、合計は4+6+8+9+10 = 37となります。

入力 − array[] = {1, 2, 3, 4, 5}
出力 − 合成数の個数：1
　　　 合成数の合計：4

解説 − 配列に含まれる合成数は4のみです。したがって、個数は1、合計は4となります。

プログラムのアプローチ

• 正の整数の配列を入力として受け取る

• 配列のサイズを計算する

• 合成数の合計を格納する変数sumを初期化する

• 配列内の最大値を変数に格納する

• エラトステネスの篩を使って、最大値までの素数をすべて求める

• 配列全体を走査し、各要素が素数かどうかを判定する。素数でなければ合成数なので、合成数のカウントを1増やし、その値を合計に加算する

サンプルコード

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 合成数の個数を求めて返す関数
int compcount(int ar[], int num, int* sum){
   // 配列の最大要素を格納
   int max_val = *max_element(ar, ar + num);
   // エラトステネスの篩を使ってmax_val以下の
   // すべての素数を求める
   // boolean型の配列「prime[0..n]」を作成。
   // prime[i]の値は最終的にfalseになる
   vector<bool> pr(max_val + 1, true);
   // 0と1の値をtrueに設定
   pr[0] = true;
   pr[1] = true;
   for (int p = 2; p * p <= max_val; p++){
      // prime[p]が変更されていなければ、それは素数
      if (pr[p] == true){
         // pの倍数をすべて更新
         for (int i = p * 2; i <= max_val; i += p){
            pr[i] = false;
         }
      }
   }
   // arr[]内のすべての合成数をカウント
   int ans = 0;
   for (int i = 0; i < num; i++){
      if (!pr[ar[i]]){
         ans++;
         *sum = *sum + ar[i];
      }
   }
   return ans;
}
// ドライバーコード
int main(){
   int ar[] = { 1, 2, 3, 4, 5 };
   int num = sizeof(ar) / sizeof(ar[0]);
   int sum = 0;
   cout << "Count of Composite Numbers = "<< compcount(ar, num, &sum);
   cout << "\nSum of Composite Numbers = " << sum;
   return 0;
}

出力

上記のコードを実行すると、以下の出力が得られます。

Count of Composite Numbers = 1
Sum of Composite Numbers = 4