e552 - 01210 - Sum of Consecutive Prime Numbers
題目描述
題目要求計算一個給定的正整數 n 可以用多少種連續質數的和表示。連續質數的和是指從某個質數開始，連續加若干個後面的質數，使得和等於 n。
解題思路
首先，使用埃拉托斯特尼篩法生成 10000 以內的質數。然後，對於每個質數，計算從該質數開始的所有連續質數的和，並記錄這些和出現的次數。最後，對於輸入的 n，輸出其對應的和的出現次數。
具體來說，程式碼首先生成質數表 pr，然後使用 ans 陣列記錄每個數字可以被多少種連續質數的和表示。對於每個質數 pr[i]，從 i 開始，不斷累加後面的質數，直到和超過 10000。每次累加後，將累加的和 c 對應的 ans[c] 加 1。最後，讀取輸入的 n，輸出 ans[n] 的值。
複雜度分析
- 時間複雜度: O(N^2)，其中 N 是 10000。生成質數表需要 O(N log log N) 的時間，計算連續質數的和需要 O(N^2) 的時間。
- 空間複雜度: O(N)，主要用於儲存質數表
pr和計數陣列ans。
程式碼
#include <iostream>
using namespace std;
int pr[1230],it,ans[10001],n;
bool p[10005]={1,1};
int main(){
for(int i=2;i<=100;++i)
for(int j=i+i;j<=10000;j+=i)
p[j]=1;
for(int i=2;i<=10000;++i){
if(p[i]==0){
pr[it]=i;
++it;
}
}
for(int i=0;i<it;++i){
int c=pr[i];
++ans[c];
for(int j=i+1;j<it;++j){
c+=pr[j];
if(c>10000)break;
++ans[c];
}
}
while(cin >> n){
if(n==0)break;
cout << ans[n] << "\n";
}
}