a007 - 判斷質數
題目描述
題目要求判斷給定的整數是否為質數。輸入為多組測試資料，每組資料包含一個整數，輸出 "質數" 或 "非質數"。
解題思路
此題採用預先計算質數的方式來加速判斷。首先，程式預先計算了從 2 到 46341 之間的質數，並將其儲存在 a 陣列中。然後，對於每個輸入的數字 q，程式會檢查 q 是否能被小於等於 sqrt(q) 的任何預先計算的質數整除。如果都不能整除，則 q 為質數，否則 q 為非質數。
複雜度分析
- 時間複雜度: O(N + M * sqrt(Q))，其中 N 是預計算質數的數量 (約為 46341 / 2 = 23170)，M 是預計算質數的數量，Q 是輸入的數字。預計算質數的時間複雜度為 O(N * sqrt(N))，但由於只執行一次，因此可以忽略。對於每個輸入數字，判斷是否為質數的時間複雜度為 O(M * sqrt(Q))。
- 空間複雜度: O(N)，其中 N 是預計算質數的數量。
程式碼
#include <iostream>
#include <cmath>
using namespace std;
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int a[4792],k=1;
bool c=true;
a[0]=2;
for(int i=3;i<=46341;i+=2){
for(int j=3;j<=sqrt(i);j+=2){
if(i%j==0){
c=false;
break;
}
}
if(c==true){
a[k]=i;
k++;
}
c=true;
}
int q=0;
while(cin >> q){
if(q==1){
c=true;
}
else{
for(int i=0;a[i]<=sqrt(q);i++){
if(q%a[i]==0){
c=false;
break;
}
}
}
if(c==true){
cout << "質數";
}
else{
cout << "非質數";
c=true;
}
cout << endl;
}
}