Phần tử mảng có tần suất là số nguyên tố trong C++

Mảng (Array) là bộ chứa các phần tử cùng kiểu dữ liệu.

Tần suất nguyên tố (Prime Frequencies) nghĩa là số lần xuất hiện của một phần tử trong mảng là một số nguyên tố.

Bài toán: Cho một chuỗi (hoặc mảng), tìm số lượng phần tử mà tần suất xuất hiện của chúng là số nguyên tố.

Ví dụ

Input: str = "helloworld" Output: 2

Giải thích

Tần suất các ký tự:

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

Ký tự 'l' xuất hiện 3 lần (số nguyên tố), 'o' xuất hiện 2 lần (số nguyên tố). Vậy có 2 ký tự thỏa mãn.

Thuật toán

• Duyệt chuỗi/mảng, dùng unordered_map để đếm tần suất mỗi phần tử.
• Với mỗi tần suất, kiểm tra xem có phải số nguyên tố không.
• Đếm số phần tử có tần suất nguyên tố.

Chương trình C++ mẫu

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

bool isPrime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i * i <= n; i += 6)
        if (n % i == 0 || n % (i + 2) == 0) return false;
    return true;
}

int countPrimeFrequent(string s) {
    int count = 0;
    unordered_map<char, int> mp;
    for (char c : s) mp[c]++;
    for (auto &p : mp)
        if (isPrime(p.second)) count++;
    return count;
}

int main() {
    string s = "helloworld";
    cout << "Số phần tử có tần suất nguyên tố: " << countPrimeFrequent(s);
    return 0;
}

Kết quả

Số phần tử có tần suất nguyên tố: 2