POJ (2739 Sum of Consecutive Prime Numbers)

spoiler posted @ 2011年4月30日 21:32 in 未分类 , 1306 阅读

题目分析:直接枚举就可以了 二重循环!

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int pri[10000],k;
bool flag[10001];
int get_pri(){
	int i;
	memset(flag,true,sizeof(flag));
	pri[1]=2;
	k=1;
	for(i=4;i<=10000;i+=2)
		flag[i]=false;
	for(i=3;i<=10000;i+=2)
		if(flag[i]){
			pri[++k]=i;
			for(int j=i*2;j<=10000;j+=i)
				flag[j]=false;
		}
	return 0;
}
int main(){
	int i,j;
	int n,ans,sum;
	get_pri();
	while(scanf("%d",&n),n){
		ans=0;
		int x=n/2;
		for(i=1;pri[i]<=x;i++){
			sum=0;
			for(j=i;j<=x;j++){
				sum+=pri[j];
				if(sum==n){
					ans++;
					break;
				}
				if(sum>n)
					break;
			}
		}
		if(flag[n])
			ans++;
		printf("%d\n",ans);
	}
	return 0;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter