e913 - pA. 彈珠計算

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算小於等於給定值 n 的質數對 (A, B) 的數量，其中 B = A + 2。換句話說，需要找出所有滿足 A 和 A+2 都是質數，且 A <= n 的組合數量。

解題思路

此題的核心在於找出所有小於等於 n 的質數，然後檢查相鄰的質數是否相差 2。為了提高效率，可以使用埃拉托斯特尼篩法 (Sieve of Eratosthenes) 預先計算出所有小於等於 n 的質數。然後，遍歷質數列表，對於每個質數 A，檢查 A+2 是否也是質數。如果是，則增加計數器。最後，輸出計數器的值。程式碼中 p[i] 為 true 表示 i 是質數，false 表示不是。ans[i] 儲存小於等於 i 的質數對數量。

複雜度分析

• 時間複雜度: O(n log log n)
• 空間複雜度: O(n)

程式碼

#include <iostream>
using namespace std;
bool p[123457]={1,1};
int ans[123457],c=0;
int main(){
	for(int i=2;i<=352;++i)
		for(int j=i+i;j<=123456;j+=i)
			p[j]=1;
	for(int i=2;i<=123456;++i){
		if(p[i]==0&&p[i-2]==0)
			++c;
		ans[i]=c;
	}
	while(cin >> c)
		cout << ans[c] << "\n";
}