a702 - Cousin Primes

🔗 前往 ZeroJudge 原題

題目描述

題目要求找出第 S 對 Cousin prime，Cousin prime 定義為 (p, p+4)，其中 p 和 p+4 都是質數。

解題思路

此題的核心在於高效地找出 Cousin primes。由於題目限制了第 100000 對 Cousin prime 中的質數小於 20000000，因此可以預先計算出所有小於 20000000 的質數，然後找出所有符合 Cousin prime 定義的配對，並將這些配對儲存起來。最後，根據輸入的 S 值，直接從儲存的配對中取出第 S 對 Cousin prime。

程式碼使用 Sieve of Eratosthenes 演算法來篩選質數。首先，建立一個布林陣列 p，用於標記每個數字是否為質數。然後，從 3 開始，將所有質數的倍數標記為非質數。篩選完畢後，遍歷 p 陣列，找出所有相鄰的質數，且相差為 4，即 Cousin primes。將這些 Cousin primes 儲存在 ans 陣列中。最後，根據輸入的 S 值，輸出 ans 陣列中對應的 Cousin prime。

複雜度分析

• 時間複雜度: O(N log log N + M)，其中 N 是質數篩選的上限 (20000000)，M 是 Cousin primes 的數量 (小於 100000)。Sieve of Eratosthenes 的時間複雜度為 O(N log log N)，找出 Cousin primes 的時間複雜度為 O(N)，儲存和查詢的時間複雜度為 O(1)。
• 空間複雜度: O(N + M)，其中 N 是質數篩選的上限 (20000000)，M 是 Cousin primes 的數量 (小於 100000)。p 陣列佔用 O(N) 的空間，ans 陣列佔用 O(M) 的空間。

程式碼

#include <iostream>
using namespace std;
//<20000000
bool p[18466750]={1,1};
int ans[100001],it,n;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	for(int i=3;i<=4300;i+=2)
		for(int j=i+i;j<=18466750;j+=i)
			p[j]=1;
	for(int i=3;i<=18466750&&it<100000;i+=2)
		if(p[i]==0&&p[i+4]==0)
			ans[it++]=i;
	while(cin >> n)
		cout << "(" << ans[n-1] << ", " << ans[n-1]+4 << ")\n";
}