c033 - 00406 - Prime Cuts
題目描述
題目要求找出 1 到 N 之間的所有質數，並根據給定的 C 值，輸出質數列表的中間部分。如果質數的數量 K 是偶數，則輸出 2C 個質數；如果 K 是奇數，則輸出 2C-1 個質數。如果 2C 或 2C-1 大於等於 K，則輸出所有質數。
解題思路
首先，使用埃拉托斯特尼篩法 (Sieve of Eratosthenes) 預先計算出 1 到 1000 之間的質數，並記錄每個數字是否為質數。然後，對於每組輸入 N 和 C，計算出 1 到 N 之間質數的數量 K。根據 K 的奇偶性以及 C 的值，計算出需要輸出的質數的起始位置和結束位置。最後，按照順序輸出指定範圍內的質數。
複雜度分析
- 時間複雜度: O(N log log N + Q * K)，其中 N 是篩選質數的上限 (1000)，Q 是查詢次數，K 是 1 到 N 之間質數的數量。埃拉托斯特尼篩法的時間複雜度是 O(N log log N)，對於每組查詢，需要遍歷最多 K 個質數，因此查詢部分的時間複雜度是 O(Q * K)。
- 空間複雜度: O(N)，主要用於儲存質數篩選的結果。
程式碼
#include <stdio.h>
int p[1001]={1},num[1001]={0};
int main(){
int k=0;
for(int i=2;i<=32;i++)
for(int j=i*2;j<1001;j+=i)
p[j]=1;
for(int i=0;i<=1000;i++){
if(p[i]==0)k++;
num[i]=k;
}
int n,c;
while(scanf("%d%d",&n,&c)>0){
printf("%d %d: ",n,c);
if(num[n]%2){
c=(c<<1)-1;
if(c>=k){
for(int i=1;i<=n;i++)
if(p[i]==0)
printf("%d ",i);
}
else{
int t=0,max=(num[n]+c)/2,min=(num[n]-c)/2;
for(int i=1;i<=n&&t<max;i++){
if(p[i]==0){
t++;
if(t>min)
printf("%d ",i);
}
}
}
}
else{
c<<=1;
if(c>=k){
for(int i=1;i<=n;i++)
if(p[i]==0)
printf("%d ",i);
}
else{
int t=0,max=(num[n]+c)/2,min=(num[n]-c)/2;
for(int i=1;i<=n&&t<max;i++){
if(p[i]==0){
t++;
if(t>min)
printf("%d ",i);
}
}
}
}
printf("\n\n");
}
}