题意:输入一个数n (2 <= n <= 10000) 有多少种方案可以把n写成若干个连续素数之和
打出10000之内的素数表,然后再打出每个可能得到的和的方案数的表
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 #include <cstdio> 5 using namespace std; 6 const int Max = 10000; 7 int prime[Max + 5],total,flag[Max + 5]; 8 int dp[6000000]; //可以求出10000所有素数和为5000000多 9 void get_prime() 10 { 11 memset(flag, 0, sizeof(flag)); 12 total = 0; 13 for(int i = 2; i <= Max; i++) 14 { 15 if(flag[i] == 0) 16 { 17 prime[ ++total ] = i; 18 for(int j = i; j <= Max / i; j++) 19 flag[i * j] = 1; 20 } 21 } 22 } 23 void init() 24 { 25 memset(dp, 0, sizeof(dp)); 26 int ans; 27 for(int i = 1; i <= total; i++) 28 { 29 ans = 0; 30 for(int j = i; j <= total; j++) //第i个为起点,第j个为终点的素数段 31 { 32 ans += prime[j]; 33 dp[ans]++; 34 } 35 } 36 } 37 int main() 38 { 39 get_prime(); 40 init(); 41 int n; 42 while(scanf("%d", &n) != EOF && n) 43 { 44 printf("%d ", dp[n]); 45 } 46 return 0; 47 }