d709 - 判断质数（一）
題目描述
題目要求讀取一系列整數，對於每個整數判斷其是否為質數。如果該數為質數，則輸出 0，否則輸出 1。輸入以 0 結尾，讀取到 0 時程式結束。
解題思路
此題的核心在於判斷一個數是否為質數。一個數 n 如果不是質數，則必然存在一個小於等於 sqrt(n) 的因數。因此，我們可以從 2 開始，迭代到 sqrt(n)，檢查 n 是否能被這些數整除。為了進一步優化，我們只需要檢查奇數即可，因為如果 n 是偶數且大於 2，則它一定不是質數。程式首先處理了特殊情況：0, 1, 和偶數。對於其他數，程式迴圈檢查從 3 開始的奇數是否為其因數。
複雜度分析
- 時間複雜度: O(sqrt(n))，其中 n 是輸入的數字。因為迴圈迭代到 sqrt(n)。
- 空間複雜度: O(1)，因為程式只使用了常數級別的額外空間。
程式碼
#include <iostream>
#include <cmath>
using namespace std;
int main(){
int a=0;
bool ans=true;
while(scanf("%d",&a)){
if(a==0){
return 0;
}
else if(a==1){
printf("1\n");
ans=false;
}
else if(a%2==0&&a!=2){
printf("1\n");
ans=false;
}
else{
for(int i=3;i<=sqrt(a);i+=2){
if(a%i==0){
printf("1\n");
ans=false;
break;
}
}
}
if(ans==true){
printf("0\n");
}
ans=true;
}
}