f426 - 高雄市109年資訊競賽國中組第四題
題目描述
題目要求計算指定範圍內（包含範圍邊界）的質數個數以及質數總和。輸入兩個整數 n 和 m，輸出 n 到 m 之間（包含 n 和 m）的質數個數和這些質數的和。
解題思路
本題的核心是找出指定範圍內的質數。使用埃拉托斯特尼篩法 (Sieve of Eratosthenes) 是一種高效的演算法，用於找出一定範圍內的質數。首先，建立一個布林陣列 prime，初始化所有元素為 1 (表示假設為質數)。然後，從 2 開始，將所有 2 的倍數標記為非質數 (設為 1)。接著，找到下一個未被標記的數字 (即質數)，重複上述過程，直到篩選完畢。最後，遍歷指定範圍，統計未被標記為非質數的數字的個數和總和。
複雜度分析
- 時間複雜度: O(N log log N)，其中 N 是範圍的大小 (10001)。埃拉托斯特尼篩法的時間複雜度為 O(N log log N)。遍歷範圍計算質數和的步驟為 O(N)。因此，整體時間複雜度為 O(N log log N)。
- 空間複雜度: O(N)，需要一個大小為 10001 的布林陣列
prime來儲存質數標記。
程式碼
#include <stdio.h>
using namespace std;
char prime[10001]={1,1};
inline int read(){
int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
inline void write(int x) {
if(x==0)
putchar_unlocked('0');
else{
int stk[9],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
}
int main(){
int n=read(),m=read(),ans=0,ans2=0;
for(int i=2;i<=100;++i)
for(int j=i+i;j<10001;j+=i)
prime[j]=1;
for(int i=n;i<=m;++i){
if(!prime[i]){
ans+=i;
++ans2;
}
}
write(ans2);
putchar_unlocked('\n');
write(ans);
}