ZeroJudge 解題筆記：a537. 10789 - Prime Frequency

作者：王一哲
日期：2026年1月9日


ZeroJudge 題目連結：a537. 10789 - Prime Frequency

解題想法

先用埃拉托斯特尼篩法建立 0 到 2000 之間的質數篩選器，再對每一行字串用字典或表格計數，計算字母數量，如果數量是質數就加到答案之中。最後再依照答案中儲存的內容按照字典序輸出，如果答案是空的則印出 empty。

Python 程式碼

Python 有現成的計數工具 Counter，使用時間約為 11 ms，記憶體約為 3.2 MB，通過測試。

from collections import Counter
""" 建立 0 ~ 2000 的質數篩選器 """
maxn = 2000
sieve = [True]*(maxn + 1)
sieve[0] = sieve[1] = False
for i in range(2, int(maxn**0.5) + 1):
    if sieve[i]:
        for j in range(i*i, maxn+1, i):
            sieve[j] = False
""" 主要的解題過程 """
T = int(input())
for t in range(1, T+1):
    cnt = Counter(input())  # 計數器
    ans = []  # 答案
    for k, v in cnt.items():  # 依序取出字母 k 及數量 v
        if sieve[v]: ans.append(k)  # 如果 v 是質數，k 加入 ans
    ans.sort()  # 排序
    print(f"Case {t:d}: ", end="")  # 輸出答案
    if not ans: print("empty")
    else: print("".join(ans))

C++ 程式碼

使用時間約為 2 ms，記憶體約為 336 kB，通過測試。

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    /* 建立 0 ~ 2000 的質數篩選器 */
    const int maxn = 2000;
    vector<bool> sieve (maxn+1, true);
    sieve[0] = false; sieve[1] = false;
    for(int i=2; i <= (int)sqrt(maxn); i++) {
        if (sieve[i]) {
            for(int j=i*i; j<=maxn; j+=i) {
                sieve[j] = false;
            }
        }
    }
    /* 主要的解題過程 */
    int T; cin >> T; cin.ignore();
    for(int t=1; t<=T; t++) {
        string s, ans = ""; getline(cin, s);  // 暫存用的 s，答案 ans
        map<char, int> cnt;  // 計數器
        for(char c : s) cnt[c]++;
        for(auto it : cnt) {  // 依序取出字母 k 及數量 v
            char k = it.first;
            int v = it.second;
            if (sieve[v]) ans += k;  // 如果 v 是質數，k 加入 ans
        }
        cout << "Case " << t << ": ";  // 輸出答案
        if (ans.empty()) cout << "empty\n";
        else cout << ans << "\n";
    }
    return 0;
}