【C++】配列内のすべての素数の積を求める方法

整数型配列 arr[] が与えられたとき、その配列に含まれるすべての素数を見つけ出し、それらの積を計算するのが本記事のテーマです。

素数とは、1とその数自身でしか割り切れない正の整数のことです。たとえば、2、3、5、7、11などが素数に該当します。

それでは、次の配列を例に解を求めてみましょう。

入力: arr[] = { 11, 20, 31, 4, 5, 6, 70 }

出力: 1705

説明: 配列内の素数は 11、31、5 の3つであり、その積は 11 × 31 × 5 = 1705 となります。

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

出力: 210

説明: 配列内の素数は 2、3、5、7 の4つであり、その積は 2 × 3 × 5 × 7 = 210 となります。なお、1は素数ではないため計算対象には含まれません。

解決のためのアプローチ

• 入力配列 arr[] を受け取る。
• 各要素を順番に調べ、素数かどうかを判定する。
• 配列内に存在するすべての素数を掛け合わせる。
• 最終的な積を返す。

アルゴリズム

Start
In function int prodprimearr(int arr[], int n)
    Step 1→ 配列の最大値を取得し、max_val として宣言・初期化（*max_element(arr, arr + n)）
    Step 2→ vector<bool> isprime(max_val + 1, true) を宣言
    Step 3→ isprime[0] と isprime[1] を false に設定
    Step 4→ p = 2 から p * p <= max_val の間、p を増加させながらループ
        もし isprime[p] == true ならば、
            i = p * 2 から i <= max_val の間、i += p ずつ増加させながらループ
                isprime[i] を false に設定
    Step 5→ prod を 1 で初期化
    Step 6→ i = 0 から i < n の間、i を増加させながらループ
        もし isprime[arr[i]] が true なら
            prod = prod * arr[i] とする
    Step 7→ prod を返す
In function int main(int argc, char const *argv[])
    Step 1→ arr[] = { 11, 20, 31, 4, 5, 6, 70 } を宣言・初期化
    Step 2→ n = sizeof(arr) / sizeof(arr[0]) を宣言・初期化
    Step 3→ prodprimearr(arr, n) の結果を出力
Stop

C++での実装例

#include <bits/stdc++.h>
using namespace std;
int prodprimearr(int arr[], int n){
   // 配列の最大値を求める
   int max_val = *max_element(arr, arr + n);
   // エラトステネスの篩を用いて、max_val 以下の
   // すべての素数を求める
   vector<bool> isprime(max_val + 1, true);
   isprime[0] = false;
   isprime[1] = false;
   for (int p = 2; p * p <= max_val; p++) {
      // isprime[p] が変更されていなければ p は素数
      if (isprime[p] == true) {
         // p の倍数をすべて合成数としてマーク
         for (int i = p * 2; i <= max_val; i += p)
            isprime[i] = false;
      }
   }
   // 配列内のすべての素数の積を求める
   int prod = 1;
   for (int i = 0; i < n; i++) {
      if (isprime[arr[i]])
         prod *= arr[i];
   }
   return prod;
}
int main(int argc, char const *argv[]){
   int arr[] = { 11, 20, 31, 4, 5, 6, 70 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << prodprimearr(arr, n);
   return 0;
}

出力

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

1705

まとめ

この記事では、エラトステネスの篩を活用して配列内の素数を効率的に判定し、その積を求めるC++プログラムを紹介しました。素数判定を事前に一括処理することで、各要素ごとに個別に素因数分解を行う方法よりも高速に動作し、要素数の多い配列でも実用的なパフォーマンスを実現できます。