【解題】Prime Frequency

ACM Volume CVII 10789 - Prime Frequency


The Problem

Given a string containing only alpha-numerals (0-9, A-Z and a-z) you have to count the frequency (the number of times the character is present) of all the characters and report only those characters whose frequency is a prime number. A prime number is a number, which is divisible by exactly two different integers. Some examples of prime numbers are 2, 3, 5, 7, 11 etc.


Input

The first line of the input is an integer T (0 < T < 201) that indicates how many sets of inputs are there. Each of the next T lines contains a single set of input.

The input of each test set is a string consisting alpha-numerals only. The length of this string is positive and less than 2001.


Output

For each set of input produce one line of output. This line contains the serial of output followed by the characters whose frequency in the input string is a prime number. These characters are to be sorted in lexicographically ascending order. Here ``lexicographically ascending" means ascending in terms of the ASCII values. Look at the output for sample input for details. If none of the character frequency is a prime number, you should print `empty' (without the quotes) instead.


Sample Input

3
ABCC
AABBBBDDDDD
ABCDFFFF


Sample Output

Case 1: C
Case 2: AD
Case 3: empty


解題思考

　　看到質數，就知道要把埃氏篩法(Sieve of Eratosthenes)拿出來用啦。

　　也就是：要找到小於等於 n 的所有質數，需從最小質數 2 開始，將所有小於等於 n 的 2 的倍數標記為「非質數」。再從下一個質數 3 開始，進行相同的步驟，將所有小於等於 n 的 3 的倍數標記為「非質數」。接著再找下一個質數，不斷重複，直到找出所有小於等於 n 的質數為止。


　　通過以上方法，我先建立了所有小於 2000 的質數表。

　　接著在讀入每一筆資料、統計完不同字元的出現次數之後，再直接查表判斷出現次數是否為質數。

　　照著題目進行要求輸出，結果就出來了。


參考解答(C++)

#include <iostream>
#include <string>

#define MAX_SIZE 2000
#define WORD_NUM 62

using namespace std;

int main(void)
{
    // 預先建立質數表
    bool prime[MAX_SIZE];
    memset(prime, 1, MAX_SIZE);
    prime[0] = false;
    for (int i = 2; i * i < MAX_SIZE; i++)
    {
        if (prime[i - 1])
        {
            for (int j = 2; (i * j) < MAX_SIZE; j++)
            {
                prime[i * j - 1] = false;
            }
        }
    }

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        string s;
        cin >> s;

        // 計算每個字元的出現次數
        int frequency[WORD_NUM];
        memset(frequency, 0, sizeof(int) * WORD_NUM);
        for (int j = 0; j < s.length(); j++)
        {
            // '0' - '9' => 0 - 9
            if (s[j] >= '0' && s[j] <= '9')
            {
                frequency[s[j] - '0']++;
            }
            // 'A' - 'Z' => 10 - 35
            else if (s[j] >= 'A' && s[j] <= 'Z')
            {
                frequency[s[j] - 'A' + 10]++;
            }
            // 'a' - 'z' => 36 - 61
            else if (s[j] >= 'a' && s[j] <= 'z')
            {
                frequency[s[j] - 'a' + 36]++;
            }
        }

        // 輸出次數為質數的字元
        cout << "Case " << i << ": ";
        bool empty = true;
        for (int j = 0; j < WORD_NUM; j++)
        {
            if (frequency[j] && prime[frequency[j] - 1])
            {
                empty = false;

                // 轉換為字元輸出
                if (j < 10)
                {
                    cout << static_cast<char>(j + '0');
                }
                else if (j < 36)
                {
                    cout << static_cast<char>(j - 10 + 'A');
                }
                else
                {
                    cout << static_cast<char>(j - 36 + 'a');
                }
            }
        }

        if (empty) { cout << "empty"; }

        cout << endl;
    }

#ifndef ONLINE_JUDGE
    system("pause");
#endif

    return 0;
}