d117 - 10924 - Prime Words

🔗 前往 ZeroJudge 原題

題目描述

題目要求判斷一個字串是否為 "prime word"。一個字串的數值定義為其所有字母的 ASCII 碼值總和。如果這個總和是一個質數，則該字串是 "prime word"，否則不是。輸入包含多組測試案例，每組一個字串，字串長度介於 1 到 20 之間，由小寫和大寫字母組成。

解題思路

解題思路是先預先計算出一定範圍內的質數，然後對於每個輸入字串，計算其字母的 ASCII 碼值總和，最後檢查這個總和是否為質數。

1. 預計算質數: 使用埃拉托斯特尼篩法 (Sieve of Eratosthenes) 預先計算出小於 1041 的所有質數。
2. 計算字串總和: 對於每個輸入字串，遍歷其所有字符，計算每個字符的 ASCII 碼值，並將它們加總。小寫字母 'a' 到 'z' 的值為 1 到 26，大寫字母 'A' 到 'Z' 的值為 27 到 52。
3. 判斷質數: 檢查計算得到的總和是否在預先計算出的質數列表中。如果在列表中，則輸出 "It is a prime word."，否則輸出 "It is not a prime word."。

複雜度分析

• 時間複雜度: O(N + M)，其中 N 是預計算質數的上限 (1041)，M 是輸入字串的總長度。預計算質數的時間複雜度為 O(N log log N)，但由於 N 的大小固定，可以視為常數時間。遍歷輸入字串計算總和的時間複雜度為 O(M)。
• 空間複雜度: O(N)，用於儲存預先計算出的質數列表。

程式碼

#include <iostream>
#include <string>
using namespace std;
int a[1041]={0};
int main(){
	for(int i=2;i<=33;i++)
		for(int j=i*2;j<1041;j+=i)
			a[j]=1;
	string b;
	while(cin >> b){
		int sum=0;
		for(int i=0;i<b.length();i++)
			(b[i]<'a')?sum+=b[i]-38:sum+=b[i]-96;	
		(a[sum]==0)?cout << "It is a prime word.\n":cout << "It is not a prime word.\n";
	}
}