d613 - Prime Gap

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算給定正整數 k 所在的質數間隙的長度。如果 k 不是合數，或者沒有質數間隙包含 k，則長度為 0。質數間隙定義為兩個相鄰質數 p 和 p + n 之間有 n - 1 個連續的合數。

解題思路

此題的核心思想是預先計算出所有質數，並記錄每個數字是質數還是合數。然後，對於每個輸入的數字 k，找到其左側最近的質數和右側最近的質數，計算它們之間的間隙長度。

程式碼首先使用埃拉托斯特尼篩法 (Sieve of Eratosthenes) 找出 1299710 以內的質數。p[i] 為 true 表示 i 是合數，false 表示 i 是質數。

接著，程式碼遍歷所有數字，如果 i 是質數，則將 ans[i] 初始化為 0。如果 i 是合數，則計算其左側最近的質數 it，並將 ans[it] 到 ans[i] 的值設定為 tmp，其中 tmp 表示目前遇到的連續合數的數量。

最後，程式碼讀取輸入的數字 k，如果 ans[k] 大於 0，則輸出 ans[k] + 1，表示 k 所在的質數間隙的長度。如果 ans[k] 為 0，則輸出 0，表示 k 不是合數，或者沒有質數間隙包含 k。

複雜度分析

• 時間複雜度: O(N log log N + Q)，其中 N 是 1299710，Q 是輸入的數字數量。O(N log log N) 是埃拉托斯特尼篩法的時間複雜度，O(Q) 是處理每個輸入數字的時間複雜度。
• 空間複雜度: O(N)，用於儲存質數資訊和答案陣列。

程式碼

#include <iostream>
using namespace std;
int ans[1299710],tmp;
bool p[1299710]={1,1};
int main() {
	cin.tie(0);cin.sync_with_stdio(0);
	for(int i=2;i<=1140;++i)
		for(int j=i+i;j<1299710;j+=i)
			p[j]=1;
	for(int i=2;i<1299710;++i){
		if(p[i]==0){
			ans[i]=0;
			int it=i-1;
			while(p[it]&&it)
				ans[it--]=tmp;
			tmp=0;
		}
		else
			++tmp;
	}
	while(cin >> tmp){
		if(tmp==0)break;
		if(ans[tmp])cout << ans[tmp]+1 << "\n";
		else cout << "0\n";
	}
	return 0;
}