【解題】Prime Words

ACM Volume CIX 10924 - Prime Words


The Problem

A prime number is a number that has only two divisors: itself and the number one. Examples of prime numbers are: 1, 2, 3, 5, 17, 101 and 10007.

In this problem you should read a set of words, each word is composed only by letters in the range a-z and A-Z. Each letter has a specific value, the letter a is worth 1, letter b is worth 2 and so on until letter z that is worth 26. In the same way, letter A is worth 27, letter B is worth 28 and letter Z is worth 52.

You should write a program to determine if a word is a prime word or not. A word is a prime word if the sum of its letters is a prime number.


Input

The input consists of a set of words. Each word is in a line by itself and has L letters, where 1 ≤ L ≤ 20. The input is terminated by enf of file (EOF).


Output

For each word you should print: It is a prime word., if the sum of the letters of the word is a prime number, otherwise you should print: It is not a prime word..


Sample Input

UFRN
contest
AcM


Sample Output

It is a prime word.
It is not a prime word.
It is not a prime word.


解題思考

　　對於這一題，可以分成兩個步驟來求解。

　　首先，根據題目定義，我們需要先將輸入字串中的字母轉成數字並相加，並存在變數 sum 中。

　　完成之後，再利用迴圈從 2 到 √sum 中尋找是否有 sum 的因數(判別是否可以整除，即餘數是否為 0)。若有，則代表 sum 不是一個質數。反之，則代表 sum 是一個質數。

　　最後按照題目的要求輸出，就可以了。


參考解答(C++)

#include <iostream>
#include <string>

using namespace std;

int main(void)
{
    string s;
    while (cin >> s)
    {
        // 將字母轉換為數字
        int sum = 0;
        for (int i = 0; i < s.length(); i++)
        {
            if (s[i] >= 'a' && s[i] <= 'z')
            {
                sum += s[i] - 'a' + 1;
            }
            else if (s[i] >= 'A' && s[i] <= 'Z')
            {
                sum += s[i] - 'A' + 27;
            }
        }

        // 判斷是否為質數
        bool prime = true;
        for (int i = 2; i * i <= sum; i++)
        {
            if (sum % i == 0)
            {
                prime = false;
                break;
            }
        }

        cout << "It is " << (prime ? "" : "not ") << "a prime word." << endl;
    }

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

    return 0;
}