配列内の素数と非素数の合計の絶対差を求める方法

はじめに

本記事では、配列内のすべての素数の合計と、すべての非素数（合成数）の合計の差を求め、その絶対値を計算する方法を解説します。

この問題を解くためには、まず各数値が素数かどうかを判定する必要があります。素数判定の基本的なアプローチとしては、「対象の数が 2 からその平方根までのいずれの整数でも割り切れないこと」を確認する方法があります。この方法では、1つの数値の判定に O(√n) の時間計算量が必要です。

アルゴリズム

diffPrimeNonPrimeSum(arr)

begin
    sum_p := arr 内のすべての素数の合計
    sum_np := arr 内のすべての非素数の合計
    return |sum_p − sum_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 diffPrimeNonPrimeSum(int arr[], int n) {
    int sum_p = 0, sum_np = 0;
    for (int i = 0; i < n; i++) {
        if (isPrime(arr[i])) {
            sum_p += arr[i];   // 素数の合計に加算
        } else {
            sum_np += arr[i];  // 非素数の合計に加算
        }
    }
    return abs(sum_p - sum_np);
}

int main() {
    int arr[] = { 5, 8, 9, 6, 21, 27, 3, 13 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Difference: " << diffPrimeNonPrimeSum(arr, n);
}

出力

Difference: 50

計算過程の確認

サンプル配列 {5, 8, 9, 6, 21, 27, 3, 13} の場合、処理は以下のように進みます。

• 素数：5, 3, 13 → 合計 = 21
• 非素数：8, 9, 6, 21, 27 → 合計 = 71
• 絶対差：|21 − 71| = 50

なお、isPrime() 関数は 2 から √n までの範囲のみをチェックするため、全要素に対して効率的に素数判定を行うことができます。配列全体の計算量は O(n√m)（m は配列内の最大値）となります。