4月 23, 2009

【解題】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;
}

2 回覆:

kgame 智涵 提到...

你是不是Copy錯sample阿
怎麼一堆0011的

小參 提到...

已更正, 感謝告知

張貼留言