UVALive3399 UVA1210 POJ2739 Sum of Consecutive Prime Numbers【素数筛选+尺取法】

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 25286		Accepted: 13793

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

Sample Output

Source

Japan 2005

Regionals 2005 >> Asia - Tokyo

问题链接：UVALive3399 UVA1210 POJ2739 Sum of Consecutive Prime Numbers。

题意简述：给定一个10000以内的n，判定n是否可以由几个连续的素数（例如：2,3,5,7...）相加得到，输出解的组数。

问题分析：

先用筛选法，筛选出素数备用，然后用尺取法解决。素数是单调递增的，满足用尺取法解决问题的条件。

先求出最前面的子序列，使之素数和大于或等于n；

重复后面一步，直到p素数大于n；

若素数子序列和等于n，则解数计数；去掉子序列的第1个元素，子序列的后面再加上后续素数（只有素数值小于n时才累加），直到子序列和为0（后续素数已经大于n，无法加上，而不断减去第1个元素）。

程序说明：小于10000的最大素数为9973，如果只用小于等于9973的素数，结果会出问题。需要多算几个素数，筛选出的素数有大于10000的素数就没有问题了。程序中，素数筛选范围是2到10000+10。

AC的C++语言程序如下：

/* UVALive3399 UVA1210 POJ2739 Sum of Consecutive Prime Numbers */

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

using namespace std;

const int N = 10000;
int primes[N+1+10];

// Eratosthenes筛选法
void esieve(int n)
{
    memset(primes, 0, sizeof(primes));

    primes[0] = primes[1] = 1;
    for(int i=2; i<=sqrt(n); i++) {
        if(!primes[i]) {
            for(int j=i*i; j<=n; j+=i)  //筛选
                primes[j] = 1;
        }
    }

    for(int i=2, j=0; i<=n; i++)
        if(!primes[i])
            primes[j++] = i;
}

int main()
{
    esieve(N+10);

    int n;
    while(cin >> n && n) {
        int start, end, sum, ans;
        start = end = sum = ans = 0;
        for(;;) {
            while(primes[end] <= n && sum < n)
                sum += primes[end++];

            if (sum == n)
                ans++;

            sum -= primes[start++];

            if (sum <= 0)
                break;
        }
        printf("%d
", ans);
    }

    return 0;
}