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

POJ 2739 Sum of Consecutive Prime Numbers

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

3.2常用技巧精选（一）

尺取法

简单，一次就AC了。先艾氏筛法做一份素数表，然后在素数表上爬行一遍就行了。最近好多事，通宵吧，第二天吃不消，不通宵吧，事情多得睡不着……

#include <iostream>
#include <vector>
using namespace std;
#define MAX_N 10000 + 16

// 先生成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;
}
///////////////////////////End Sub//////////////////////////////////

又看到了神奇的0毫秒：

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 2739 Sum of Consecutive Prime Numbers 题解 《挑战程序设计竞赛》