d362 - 10394 - Twin Primes
題目描述
題目要求找出第 S 對 twin prime，並以 (p1, p2) 的格式輸出。Twin prime 指的是兩個差為 2 的質數。
解題思路
此題的核心在於找出第 S 對 twin prime。由於 S 的範圍最大到 100000，直接計算到第 100000 對 twin prime 會比較耗時。因此，程式碼採用了預先計算的方法。首先，使用埃拉托斯特尼篩法 (Sieve of Eratosthenes) 找出小於 4500 的所有質數，並將其儲存在 p 陣列中。接著，遍歷奇數，判斷該數及其加 2 的數是否都是質數。如果是，則將該 twin prime 儲存在 ans 陣列中。最後，根據輸入的 S 值，從 ans 陣列中取出第 S 對 twin prime 並輸出。
複雜度分析
- 時間複雜度: O(N log log N + M)，其中 N 是篩選質數的上限 (4500)，M 是需要計算的 twin prime 數量 (約 100000)。埃拉托斯特尼篩法的時間複雜度為 O(N log log N)，計算 twin prime 的時間複雜度為 O(M)。
- 空間複雜度: O(N + M)，其中 N 是篩選質數的上限 (4500)，M 是儲存 twin prime 的數量 (約 100000)。
程式碼
#include <iostream>
using namespace std;
int p[700],n,it,ans[100005],it2,k;
bool isp[5005];
bool jp(int x){
for(int i=0;i<it&&p[i]<x;++i){
if(x%p[i]==0)return 0;
}
return 1;
}
int main(){
cin.tie(0); cout.tie(0);
ios::sync_with_stdio(false);
for(int i=2;i<=67;++i){
for(int j=i+i;j<=4500;j+=i){
isp[j]=1;
}
}
for(int i=2;i<=4500;++i){
if(isp[i]==0){
p[it]=i;
++it;
}
}
for(int i=3;it2<100000;i+=2){
if(jp(i+2)==0){
i+=2;
}
else{
if(jp(i)){
ans[it2]=i;
++it2;
}
}
}
while(cin >> n){
cout << "(" << ans[n-1] << ", " << ans[n-1]+2 << ")\n";
}
}