d386 - 10200 - Prime Time
題目描述
題目要求計算在給定範圍 [a, b] 中，n^2 + n + 41 產生質數的百分比。
解題思路
由於 n 的範圍較小 (0 <= n <= 10000)，可以先預先計算出 n^2 + n + 41 在這個範圍內每個值是否為質數，並統計質數的數量。然後，對於每個查詢 (a, b)，計算 [a, b] 範圍內質數的數量，並計算百分比。使用預計算和累加和可以有效地計算區間內的質數數量。
複雜度分析
- 時間複雜度: O(Nsqrt(N)) + O(Q)，其中 N 是
n的最大值 (10000)，Q 是查詢的數量。預計算質數的時間複雜度是 O(Nsqrt(N))，查詢的時間複雜度是 O(1)。 - 空間複雜度: O(N)，用於儲存預計算的質數數量。
程式碼
#include <bits/stdc++.h>
using namespace std;
int n,ca,p[10005],x,y;
bool isp(int x){
for(int i=2;i<=sqrt(x);++i){
if(x%i==0)return 0;
}
return 1;
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
for(int i=0;i<=10000;++i){
if(isp(i*i+i+41)){
++p[i];
}
if(i)p[i]+=p[i-1];
}
while(cin >> x >> y){
cout << fixed << setprecision(2) << (double)(p[y]-(x==0?0:p[x-1]))/(y-x+1)*100.0+0.000001 << "\n";
}
}