【C++】出現頻度が素数となる配列要素（文字）を見つける方法

配列と素数頻度とは

配列（Array）とは、同じデータ型の要素を格納するためのコンテナです。

素数頻度（Prime Frequency）とは、配列内の要素が出現する回数が素数になっていることを意味します。

これらの定義に基づき、本記事では「出現回数が素数となっている配列要素を見つける」という問題を扱います。具体的には、文字列が与えられたとき、各文字の出現頻度を求め、その頻度が素数であればカウントしていく流れになります。

入力例

Input: str = "helloworld"
Output: 2

解説

まず、文字列内の各文字の出現回数を数えてみましょう。

h → 1
e → 1
l → 3
o → 2
w → 1
r → 1
d → 1

このうち、l は3回（素数）、o は2回（素数）出現しているため、条件を満たす文字は2個となります。

アプローチとしては、文字列を先頭から順に走査しながら、C++ の map（連想配列）を使って各文字の出現回数を記録します。その後、各頻度が素数かどうかを判定し、素数であればカウントを1ずつ増やしていきます。

アルゴリズム

1. 文字列を走査し、unordered_map を使って各文字の出現回数をカウントします。
2. マップに格納された各文字の頻度に対して、素数判定関数でチェックを行います。
3. 頻度が素数であれば、結果用のカウンタをインクリメントします。
4. 最終的なカウントを返して出力します。

素数判定には「6k±1 法」と呼ばれる効率的な手法を採用しています。2 と 3 の倍数を事前に除外した後、5 から始めて 6 ずつ増加させながら約数の有無を確認することで、√n までの範囲で高速に素数判定を完了できます。

C++ 実装例

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int check_prime(int n) {
    if (n <= 1)
        return 0;
    if (n <= 3)
        return 1;
    if (n % 2 == 0 || n % 3 == 0)
        return 0;
    for (int i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return 0;
    return 1;
}
int countPrimeFrequent(string s) {
    int count = 0;
    unordered_map<char, int> mp;
    for (int i = 0; i < s.length(); i++)
        mp[s[i]]++;
    for (auto it = mp.begin(); it != mp.end(); it++) {
        if (check_prime(it->second))
            count++;
    }
    return count;
}
int main() {
    string s = "helloworld";
    cout << countPrimeFrequent(s);
    return 0;
}

出力

素数の頻度を持つ文字の数 : 2

計算量の目安

時間計算量： 文字列の長さを n、異なる文字の種類数を k、最大頻度を m とすると、文字列の走査に O(n)、各頻度の素数判定に O(√m) が必要なため、全体として O(n + k√m) となります。

空間計算量： マップに文字ごとの頻度を保存するため、O(k) の追加メモリを使用します。