配列内の素数と非素数の積の絶対差を求めるアルゴリズム

本記事では、配列に含まれるすべての素数の積と、すべての非素数（合成数）の積との間の絶対差を求める方法を解説します。

この問題を解くには、まず各要素が素数かどうかを判定する必要があります。素数判定の代表的な手法の一つとして、「2 からその数の平方根までのどの整数でも割り切れないこと」を確認する方法があります。ある数 n が合成数であれば、必ず √n 以下の約数を持つため、√n まで調べれば十分であり、判定にかかる計算量は O(√n) で抑えられます。

すべての要素について素数かどうかを判定したら、それぞれのグループごとに積を計算し、最後に両者の差の絶対値を求めます。

アルゴリズム

diffPrimeNonPrimeProd(arr)

begin
    prod_p := 配列 arr 内のすべての素数の積
    prod_np := 配列 arr 内のすべての非素数の積
    return |prod_p − prod_np|
end

C++ による実装例

#include <iostream>
#include <cmath>
using namespace std;
bool isPrime(int n){
    for(int i = 2; i<=sqrt(n); i++){
       if(n % i == 0){
          return false; // 素数ではない
       }
    }
    return true; // 素数
}
int diffPrimeNonPrimeProd(int arr[], int n) {
    int prod_p = 1, prod_np = 1;
    for(int i = 0; i<n; i++){
       if(isPrime(arr[i])){
          prod_p *= arr[i];
       } else {
          prod_np *= arr[i];
       }
    }
    return abs(prod_p - prod_np);
}
main() {
    int arr[] = { 4, 5, 3, 8, 13, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Difference: " << diffPrimeNonPrimeProd(arr, n);
}

出力

Difference: 125

処理の流れと解説

上記の実装例では、配列 {4, 5, 3, 8, 13, 10} を入力としています。このうち素数は 5、3、13 であり、それらの積は 5 × 3 × 13 = 195 です。一方、非素数は 4、8、10 であり、それらの積は 4 × 8 × 10 = 320 です。

したがって、求める絶対差は |195 − 320| = 125 となり、出力結果と一致します。

補足：実装上の注意点

• isPrime 関数では、1 以下の数に対する明示的なチェックを行っていないため、1 が素数として扱われる可能性があります。実際の運用では n < 2 の場合に false を返すよう修正することを推奨します。
• 全体の計算量は、配列の長さを n、要素の最大値を m とすると O(n·√m) になります。