e655 - 10852 - Less Prime

🔗 前往 ZeroJudge 原題

題目描述

題目要求對於給定的整數 n (100 ≤ n ≤ 10000)，找到一個質數 x，使得 x ≤ n，並且 (n - px) 的值最大，其中 p 是整數，且 px ≤ n < (p + 1)x。 換句話說，我們要找到一個質數 x，使得 n 除以 x 的餘數最小，從而最大化 n - px 的值。

解題思路

首先，我們需要預先計算出 1 到 10000 之間的質數。可以使用埃拉托斯特尼篩法 (Sieve of Eratosthenes) 來有效地完成這個任務。 預計算完質數後，對於每個輸入的 n，我們從 n/2 開始向上尋找第一個質數。 為什麼從 n/2 開始？ 因為 p*x ≤ n，所以 x 必然小於等於 n/2 (當 p=1 時)。 找到第一個滿足條件的質數 x 後，我們直接輸出 x。 由於題目要求找到 一個 滿足條件的質數，因此一旦找到，就可以立即輸出，不需要進一步的優化。

複雜度分析

• 時間複雜度: O(N log log N + M * (N/2))，其中 N 是 10000，M 是測資數量。 O(N log log N) 是埃拉托斯特尼篩法的時間複雜度，O(M * (N/2)) 是對於每個測資尋找質數的時間複雜度。
• 空間複雜度: O(N)，用於儲存質數篩選的結果。

程式碼

#include <iostream>
using namespace std;
int n,m;
bool p[10001]={1,1};
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	for(int i=2;i<=100;++i)
		for(int j=i+i;j<=10000;j+=i)
			p[j]=1;
	cin >> m;
	while(m--){
		cin >> n;
		n=n/2;
		++n;
		while(p[n])
			++n;
		cout << n << "\n";
	}
}