首页 > 代码库 > poj2739

poj2739

2024-07-05 19:58:37   220人阅读

                                                                                       Sum of Consecutive Prime Numbers
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 18427   Accepted: 10122

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

Japan 2005
过的第一段代码，可是后来发现自己事实上是蠢了，因为根本没必要用筛选法挑选素数，以至于我wrong了几次，因为筛选法挑出来的素数在数组中不是连续存在的，如果不再把素数统一赋值到一个连续的数组中的话，我们在后面进行累加的时候就会出现一些困难，因为我们还需要给vis一个循环，让其过滤掉非素数。我wrong了一次后发现了这个问题，于是赋值到一个连续的数组中，当时我选择的是在筛选素数的同时进行赋值，可是wrong了几次，后来发现，在筛选的过程中赋值，isprimer数组中的素数是不完整的，因为筛选法本身就不是全部遍历筛选的！
//memory：744K time：0MS
#include <iostream>
#include<cmath>
#include<cstring>
using namespace std;
const int MAXN = 10001;
int main()
{
    bool vis[MAXN];
    int isprime[MAXN],k=0;
    memset(vis,0,sizeof(vis));
    for(int i=2;i<(int)sqrt((double)MAXN);i++)   //筛选法挑选素数
    {
        if(!vis[i])
        {
            for(int j=i*i;j<MAXN;j+=i)
                vis[j]=1;
        }
    }
    for(int i=2;i<MAXN;i++)
    {
        if(!vis[i])
            isprime[k++]=i;
    }
    int n;
    while(cin>>n)
    {
        if(n==0)
            break;
        //因为不一定是从头开始，所以需要两层循环，
        //每一个i都需要从i开始往后累加
        int num=0;
        for(int i=0;isprime[i]<=n;i++)   //isprime循环
        {
            int ans = 0;    //累加器
            for(int j=i ; j<k&& ans<n ; j++)  //从每一个i开始往后循环
            {
                ans += isprime[j];
            }
            if(ans==n)
                num++;
        }
        cout<<num<<endl;
    }
    return 0;
}

以下给出一个较好的代码，挑选素数的想法很好，素数只能被素数整除，不会被偶数整除。但是这种方法很明显慢一些

//memory :736K time :32MS
#include<iostream>
using namespace std;
const int MAXN = 10001;
int prime[MAXN],prime_num = 0;

bool isprime(int n)
{
    for(int i=0;i<prime_num;i++)
    {
        if(n%prime[i]==0)
            return false;
    }
    return true;
}

int main()
{
    int n;

    for(int i=2;i<MAXN;i++)
    {
        if(isprime(i))
        {
            prime[prime_num++]=i;
        }
    }
    while(cin>>n)
    {
        if(n==0)
            break;
        int num=0;
        for(int i=0;prime[i]<=n;i++)
        {
            int ans = 0;
            for(int j=i;j<prime_num&&ans<n;j++)
            {
                ans += prime[j];
            }
            if(ans == n)
                num++;
        }
        cout<<num<<endl;
    }
    return 0;
}

 

 


联系
我们