配列内で素数回出現する要素を数えるアルゴリズムとC++実装

ある配列が与えられたとき、その中に素数回出現している要素がいくつあるかを数える問題を考えてみましょう。

例として、次の配列を見てください。

{1, 2, 2, 0, 1, 5, 2, 5, 0, 0, 1, 1}

この場合、各要素の出現回数は以下のようになります。

• 1 → 4回（素数ではない）
• 2 → 3回（素数）
• 0 → 3回（素数）
• 5 → 2回（素数）

したがって、素数回出現している要素は {2, 0, 5} の3つとなり、答えは 3 です。

アルゴリズム

countPrimeOccurrence(arr, n)

Begin
    count := 0
    キーと値がint型のマップを定義する
    arr内の各要素eについて、以下を実行する
        map.key(arr) の値を増やす
    done
    各キーについて、対応する値が素数かどうかを判定し、
    素数であれば count を増やす
    count を返す
End

C++による実装例

まず頻度を記録するためのマップを作成し、各要素の出現回数をカウントします。その後、各出現回数が素数かどうかを isPrime() 関数で判定し、素数であればカウントを増やしていきます。

#include <iostream>
#include <map>
using namespace std;

bool isPrime(int n){
    for(int i = 2; i<=n/2; i++){
        if(n % i == 0){
            return false;
        }
    }
    return true;
}

int countPrimeOcurrence(int arr[], int n){
    int count = 0;
    map<int, int> freq_map;
    for(int i = 0; i<n; i++){
        freq_map[arr[i]]++; // 出現頻度をカウント
    }
    for (auto it = freq_map.begin(); it != freq_map.end(); it++) {
        if (isPrime(it->second))
            count++;
    }
    return count;
}

int main() {
    int arr[] = {1, 2, 2, 0, 1, 5, 2, 5, 0, 0, 1, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Prime frequency count: " << countPrimeOcurrence(arr, n);
}

実行結果

Prime frequency count: 3

処理のポイント

• 時間計算量： マップへの挿入と走査に O(n log n)、素数判定に O(√m)（mは最大出現回数）程度かかります。
• isPrime関数： 2から n/2 まで順に割り切れるかを確認するシンプルな試し割り法を使用しています。より効率化するなら √n まで調べる方法もあります。
• map の利用： C++の std::map を使うことで、要素ごとの出現回数を自動的に整理できます。