a699 - 1、国王的烦恼(King)

🔗 前往 ZeroJudge 原題

題目描述

題目要求判斷給定的數字是否為質數，輸入數字範圍在 0 到 671064 之間。有多組測試數據，直到輸入結束 (EOF)。

解題思路

此題使用埃拉托斯特尼篩法 (Sieve of Eratosthenes) 預先計算出 671064 範圍內的質數。首先，建立一個布林陣列 p，初始化所有元素為 true (假設所有數字都是質數)。然後，從 2 開始，將所有 2 的倍數標記為非質數，接著是 3 的倍數，依此類推。最後，對於每個輸入數字 n，直接檢查 p[n] 的值，如果是 true，則輸出 "It's a prime!!!"，否則輸出 "It's not a prime!!!"。

複雜度分析

• 時間複雜度: O(N log log N) (預計算質數) + O(1) (查詢每個數字是否為質數)，其中 N = 671065。
• 空間複雜度: O(N)，用於儲存布林陣列 p。

程式碼

#include <iostream>
using namespace std;
bool p[671065]={1,1};
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	for(int i=2;i<820;++i)
		for(int j=i+i;j<671065;j+=i)
			p[j]=1;
	int n;
	while(cin >> n)
		(p[n])?cout << "It's not a prime!!!\n":cout << "It's a prime!!!\n";
}