POJ 2739 Sum of Consecutive Prime Numbers【素数筛】_综合

题目

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.

题目大意：给定一个数字，寻找有几种连续的素数之和可以等于给定数字。
例如：17有两种，一种是2+3+5+7。另一种是17。
而例如20：无论是7+13还是3+5+5+7都是不符合条件的。

输入

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.

输出

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.

样例输入

样例输出

题目分析

本题可将所有的素数全部筛选出来，用一个数组进行存放，然后对素数数组进行遍历，查找有几种方法可得出最终数字。
在筛选素数上，采用了欧拉筛的方法，即通过之前存在的素数，来排除掉之后范围内的非素数。每个数遍历一遍，即该方法的复杂度为 $O (n)$ .

欧拉筛：

int isprime[10005];//筛选范围
int prime[10005];//保存已经筛出的素数
int cnt = 0;//统计已经筛选出的个数
void getprime(){
    memset(isprime,1,sizeof(isprime));//对每一个数进行标记均为素数，未筛选isprime[1] = 0;//1不是素数for(int i = 2;i<=10000;++i){
    if(isprime[i]) prime[++cnt]=i;//如果i是一个素数，那么存入素数表中for(int j = 1;j<=cnt&&(i*prime[j])<=10000;++j){
    //通过已经筛选出来的素数去作为因数，从而筛去之后的合数。//且prime[j]是该被筛去合数的最小因数（保证每个数只被筛一遍）isprime[i*prime[j]] = 0;//筛去if(i%prime[j]==0) break;//保证了prime[j]是被筛数最小的质因数。//e.g. 63可被3*21筛去，也可是7*9.如果不保证prime[j]是最小质因数，那么63会被筛两次，//这样增加了运行时间，降低了效率。由此，想只筛一遍，必须保证prime[j]是最小质因数。}}
}

附上对欧拉筛的更详细解说：
欧拉筛代码实现

代码

#include<iostream>
#include<cstring>
using namespace std;int isprime[10005];
int prime[10005];
int cnt = 0;
void getprime(){
    memset(isprime,1,sizeof(isprime));isprime[1] = 0;for(int i = 2;i<=10000;++i){
    if(isprime[i]) prime[++cnt]=i;for(int j = 1;j<=cnt&&(i*prime[j])<=10000;++j){
    isprime[i*prime[j]] = 0;if(i%prime[j]==0) break;}}
}int getsum(int m){
    int k,sum,time = 0;for(int i = 1;i<=cnt;++i){
    sum = 0;k = 0;while(sum<m){
     //判定是否超出当前数字sum+=prime[i+k];//依次求和++k;}if(sum == m) ++time;}return time;
}int main()
{
    getprime();int a;while(scanf("%d",&a)&&a!=0)cout << getsum(a)<<endl;return 0;
}

运行结果

在这里插入图片描述