d387 - 10235 - Simply Emirp
題目描述
題目要求判斷給定的整數是質數、非質數還是 Emirp。Emirp 定義為一個質數，其反轉後也是質數，且反轉後的數與原數不同。
解題思路
首先，使用埃拉托斯特尼篩法預先計算出 1 到 1000000 之間的質數。然後，對於每個輸入的數字，檢查它是否為質數。如果它是質數，則計算它的反轉數，並檢查反轉數是否也是質數，且與原數不同。根據這些條件，輸出相應的結果。
複雜度分析
- 時間複雜度: O(N log log N + M)，其中 N 是篩法計算質數的上限 (1000000)，M 是輸入數字的個數。埃拉托斯特尼篩法的時間複雜度為 O(N log log N)，反轉數字和檢查質數的時間複雜度為 O(M)。
- 空間複雜度: O(N)，用於儲存篩法計算出的質數陣列。
程式碼
#include <iostream>
using namespace std;
int c[1000000]={0};
int main(){
cin.tie(0); ios::sync_with_stdio(false);
for(int i=2;i<=1000;i++)
for(int j=i*2;j<1000000;j+=i)
c[j]=1;
int a;
while(cin >> a){
if(c[a]==1)
cout << a << " is not prime.\n";
else{
int b=0,d=a;
while(d>0){
b*=10;
b+=d%10;
d/=10;
}
if(b!=a&&c[b]==0)
cout << a << " is emirp.\n";
else
cout << a << " is prime.\n";
}
}
}