POJ2739_Sum of Consecutive Prime Numbers【筛法求素数】【枚举】

Japan 2005

题目大意：

一个数可以由若干种连续的素数序列求和得到，比如说41 = 2+3+5+7+11+13 = 11+13+17 = 41

共有三种不同的素数序列求和得到。给你一个数N，求满足N = 连续的素数序列和的方案数

思路：

很简单的题目，但是用普通方法判断素数可能会超时，这里用了筛法求素数的方法直接用数组Prime

判断是否为素数，另开一个数组PrimeNum用来存所有的素数。

最后就是枚举，求得满足的方案数

#include<stdio.h>
#include<string.h>

int Prime[10010],PrimeNum[10010];

int IsPrime()//筛法求素数
{
    Prime[0] = Prime[1] = 0;

    for(int i = 2; i <= 10000; i++)
        Prime[i] = 1;
    for(int i = 2; i <= 10000; i++)
    {
        for(int j = i+i; j <= 10000; j+=i)
            Prime[j] = 0;
    }
    int num = 0;
    for(int i = 0; i <= 10000; i++)
        if(Prime[i])
            PrimeNum[num++] = i;

    return num;
}
int main()
{
    int num = IsPrime();
    int N;
    while(~scanf("%d",&N) && N!=0)
    {
        int count = 0;
        for(int i = 0; PrimeNum[i]<=N && i < num; i++)//枚举
        {
            int sum = 0;
            for(int j = i; PrimeNum[j]<=N && j < num; j++)
            {
                sum += PrimeNum[j];
                if(sum == N)
                {
                    count++;
                    break;
                }
                if(sum > N)
                    break;
            }
        }

        printf("%d\n",count);
    }

    return 0;
}

POJ2739_Sum of Consecutive Prime Numbers【筛法求素数】【枚举】

原文：http://blog.csdn.net/lianai911/article/details/39379587