e530 - 01644 - Prime Gap

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算給定數字 k 所在的 Prime Gap 的長度。Prime Gap 定義為兩個連續質數 p 和 p+n 之間 n-1 個連續合數的序列。如果 k 不在任何 Prime Gap 內，則輸出 0。

解題思路

此題的解法是先預先計算出一定範圍內的質數，然後對於輸入的 k，尋找其前後的質數，並計算它們之間的差值。

1. 質數篩選: 使用埃拉托斯特尼篩法 (Sieve of Eratosthenes) 預先計算出小於等於 1299709 的所有質數，並將其儲存在 pr 陣列中。
2. 輸入處理: 讀取輸入的 k 值。如果 k 為 0，則結束程式。
3. 特殊情況處理: 如果 k 本身是質數，則 Prime Gap 長度為 0。
4. 尋找 Prime Gap: 如果 k 不是質數，則遍歷預先計算的質數陣列 pr，找到大於 k 的第一個質數 pr[i]。然後，Prime Gap 的長度為 pr[i] - pr[i-1]。

複雜度分析

• 時間複雜度: O(N + M)，其中 N 是篩選質數的範圍 (1299709)，M 是輸入的數量。 篩選質數的時間複雜度為 O(N log log N)，尋找 Prime Gap 的時間複雜度為 O(M * K)，K 是質數陣列的長度。
• 空間複雜度: O(N)，主要用於儲存質數陣列 pr 和布林陣列 p。

程式碼

#include <iostream>
using namespace std;
int pr[100001],it=0,n;
bool p[1299710]={1,1};
int main(){
	for(int i=2;i<=1141;++i)
		for(int j=i+i;j<=1299709;j+=i)
			p[j]=1;
	for(int i=2;i<=1299709;++i)
		if(!p[i]){
			pr[it]=i;
			++it;
		}
	while(cin >> n){
		if(!n)break;
		else if(!p[n])
			cout << "0\n";
		else
			for(int i=0;i<=100000;++i)
				if(pr[i]>n){
					cout << pr[i]-pr[i-1] << "\n";
					break;
				}
	}
}