C++で配列内のすべての合成数の積を求める方法

n 個の整数で構成される配列 arr[n] が与えられたとき、配列内に含まれるすべての「合成数」の積を求めるのが本稿のテーマです。

合成数とは、1 と自分自身以外にも約数を持つ正の整数、すなわち 2 つの整数を掛け合わせて作ることができる数のことです。たとえば 6 は 2 × 3 で表せるため合成数であり、素数ではありません。逆に言えば、合成数とは「素数ではない数」とも定義できます。

入力例と出力例

入力

arr[] = {1, 2, 4, 5, 6, 7}

出力

24

説明： 配列内の合成数は 4 と 6 のみで、その積は 4 × 6 = 24 となります。

入力

arr[] = {10, 2, 4, 5, 6, 11}

出力

240

説明： 配列内の合成数は 10、4、6 で、その積は 10 × 4 × 6 = 240 となります。

解決のためのアプローチ

• 配列の全要素を先頭から順に走査します。

• 各要素について素数判定を行い、素数でない数（＝1 以外の数で割り切れる合成数）を見つけます。

• 見つかったすべての合成数を掛け合わせます。

• 最終的な積を結果として返します。

アルゴリズム

ここでは、エラトステネスの篩を利用してあらかじめ素数表を作成しておくことで、各要素が合成数かどうかを効率よく判定します。

Start
Step 1 → 配列内の合成数の積を求める関数を宣言する
    int product_arr(int arr[], int size)
        int max = *max_element(arr, arr + size) を宣言
        vector<bool> prime(max + 1, true) を設定
        prime[0] = true を設定
        prime[1] = true を設定
        Loop For int i = 2 ～ i * i <= max、i++
            IF (prime[i] == true)
                Loop For int j = i * 2 ～ j <= max、j += i
                    prime[j] = false を設定
                End
            End
        End
        int product = 1 を設定
        Loop For int i = 0 ～ i < size、i++
            IF (!prime[arr[i]])
                product *= arr[i]
            End
        End
        return product
Stop

C++ 実装例

#include <bits/stdc++.h>
using namespace std;
// 配列内の合成数の積を求める関数
int product_arr(int arr[], int size){
    int max = *max_element(arr, arr + size);
    vector<bool> prime(max + 1, true);
    prime[0] = true;
    prime[1] = true;
    for (int i = 2; i * i <= max; i++){
        if (prime[i] == true){
            for (int j = i * 2; j <= max; j += i)
                prime[j] = false;
        }
    }
    int product = 1;
    for (int i = 0; i < size; i++){
        if (!prime[arr[i]]){
            product *= arr[i];
        }
    }
    return product;
}
int main(){
    int arr[] = { 2, 4, 6, 8, 10};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout<<"配列内の合成数の積: "<<product_arr(arr, size);
    return 0;
}

出力

上記のコードを実行すると、次のような結果が出力されます。

配列内の合成数の積: 1920

コードのポイント

この実装では、まず配列内の最大値を求め、その大きさに合わせた素数判定テーブルを構築します。prime[0] と prime[1] を true に設定しているのは、0 と 1 が合成数ではないため、積の計算に含まれないようにするためです。その後、配列をもう一度走査し、素数でない要素だけを積算します。全体の計算量は、篩の構築に O(max log log max)、配列の走査に O(n) となり、非常に効率的です。なお、この実装は配列の要素が非負の整数であることを前提としています。