b513 - 判斷質數-商競103

🔗 前往 ZeroJudge 原題

題目描述

題目要求讀取多組數字，對於每個數字判斷其是否為質數，如果是則輸出 "Y"，否則輸出 "N"。輸入的第一行表示有幾組測試資料，接下來的每一行包含一個介於 2 到 65535 之間的數字。

解題思路

此題的解題思路是對於每個輸入的數字，從 2 開始迭代到該數字的平方根。如果在迭代過程中發現該數字可以被任何一個數字整除，則該數字不是質數，輸出 "N"。如果迭代完成後沒有發現任何可以整除該數字的數字，則該數字是質數，輸出 "Y"。使用平方根作為迭代上限是因為如果一個數有大於其平方根的因數，那麼它必然有一個小於其平方根的因數。

複雜度分析

• 時間複雜度: O(n * sqrt(m))，其中 n 是輸入數字的個數，m 是每個數字的大小。對於每個數字，我們需要迭代到其平方根，因此單個數字的判斷時間複雜度為 O(sqrt(m))。
• 空間複雜度: O(1)，因為我們只使用了常數級別的額外空間。

程式碼

#include <iostream>
#include <math.h>

using namespace std;

int main(){
	int a=0;
	long long int b=0;
	bool ans=true;
	while(cin >> a){
		for(int i=1;i<=a;i++){
			cin >> b;
			for(int j=2;j<=sqrt(b);j++){
				if(b%j==0){
					cout << "N" << endl;
					ans=false;
					break;
				}
			}
			if(ans==true){
				cout << "Y" << endl;
			}
			ans=true;
		}
	}
}