|
Sum of Consecutive Prime Numbers
Description
Some positive integers can be represented by a sum of one or more consecutive prime numbers. How many such representations does a given positive integer have? For example, the integer 53 has two representations 5 + 7 + 11 + 13 + 17 and 53. The integer 41 has
three representations 2+3+5+7+11+13, 11+13+17, and 41. The integer 3 has only one representation, which is 3. The integer 20 has no such representations. Note that summands must be consecutive prime numbers, so neither 7 + 13 nor 3 + 5 + 5 + 7 is a valid representation for the integer 20. Your mission is to write a program that reports the number of representations for the given positive integer. Input
The input is a sequence of positive integers each in a separate line. The integers are between 2 and 10 000, inclusive. The end of the input is indicated by a zero.
Output
The output should be composed of lines each corresponding to an input line except the last zero. An output line includes the number of representations for the input integer as the sum of one or more consecutive prime numbers. No other characters should be inserted
in the output. Sample Input 2 3 17 41 20 666 12 53 0 Sample Output 1 1 2 3 0 0 1 2 Source |
解题思路：
可能是因为好久没有刷题的缘故了，，这道水题卡了我快１个小时，，最后脑补了队列终于Ａ了，卡的原因很简单，在枚举循环节的时候总是出问题，所以说呢，该好好补补最为基础和常用的东西了，不过这题如果用了队列也还是蛮好的．
题一读，就是说，给你一个数字，然后让你在素数列中找到连续的一串素数使得他们的和和这个数字相等，问有多少种这样的组合？
其实，这题就是一个 素数筛＋队列．．．
先经过打一个素数表，然后复制到ｂ数组中，利用队列ＦＩＦＯ的原则，首先让２进入队伍中，然后将进入的元素加进sum中，如果相等了，那么直接退出，，然后以此可以手动模拟下，，，，
代码：
# include<cstdio>
# include<iostream>
# include<queue>
using namespace std;
# define MAX 10001
int a[MAX];
int b[MAX/2];
void dabiao()
{
for ( int i = 2;i <=MAX;i++ )
a[i] = 1;
for ( int i = 2;i<=MAX;i++ )
{
if ( a[i] == 1 )
{
for ( int j = 2*i;j <= MAX;j+=i )
{
a[j] = 0;
}
}
}
}
int main(void)
{
int n;
int n2;
dabiao();
while ( cin>>n )
{
if ( n==0 )
break;
for ( int j = 0, i = 2;i < MAX;i++ )
{
if ( a[i] == 1 )
{
b[j++] = i;
n2 = j;
}
}
int sum = 0;
int cnt = 0;
queue<int>Q;
for ( int i = 0;i < n2;i++ )
{
Q.push(b[i]);
sum += b[i];
if ( sum == n )
{
cnt++;
sum -= Q.front();
Q.pop();
}
while ( sum > n )
{
sum -= Q.front();
Q.pop();
if ( sum == n )
{
cnt++;
sum -= Q.front();
Q.pop();
break;
}
}
if ( Q.empty() )
break;
}
cout<<cnt<<endl;
}
return 0;
}