POJ 2739 Sum of Consecutive Prime Numbers 题解 《挑战程序设计竞赛》 � 码农场

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.

连续素数和：将一个整数分解为连续的素数之和，有多少种分法？

3.2常用技巧精选（一）

尺取法

先艾氏筛法做一份素数表，然后在素数表上爬行一遍就行了

// 先生成MAX_PRIME内的素数表

#define MAX_PRIME MAX_N

vector<int> primes;

vector<bool> is_prime;

void init_primes()

{

    is_prime = vector<bool>(MAX_PRIME + 1, true);

    is_prime[0] = is_prime[1] = false;

    for (int i = 2; i <= MAX_PRIME; ++i)

    {

        if (is_prime[i])

        {

            primes.push_back(i);

            for (int j = i * 2; j <= MAX_PRIME; j += i)

            {

                is_prime[j] = false;

            }

        }

    }

}

 

///////////////////////////SubMain//////////////////////////////////

int main(int argc, char *argv[])

{

#ifndef ONLINE_JUDGE

    freopen("in.txt", "r", stdin);

    freopen("out.txt", "w", stdout);

#endif

    init_primes();

    const int size = primes.size();

    int n;

    while (cin >> n && n)

    {

        int l = 0, r = 0, sum = 0, result = 0;

        for (;;)

        {

            while (sum < n && r < size)

            {

                sum += primes[r++];

            }

            if (sum < n)

            {

                break;

            }

            else if (sum == n)

            {

                ++result;

            }

            sum -= primes[l++];

        }

        cout << result << endl;

    }

#ifndef ONLINE_JUDGE

    fclose(stdin);

    fclose(stdout);

    system("out.txt");

#endif

    return 0;

}

Also check http://blog.csdn.net/fps538/article/details/9397787
Read full article from POJ 2739 Sum of Consecutive Prime Numbers 题解 《挑战程序设计竞赛》 � 码农场