现在的位置: 首页 > 综合 > 正文

sdut2404 Super Prime

2013年09月07日 ⁄ 综合 ⁄ 共 953字 ⁄ 字号 评论关闭

输出有时候是YES NO,有时候是Yes No,有时候是yes no。

因为这个WA实在可惜,Be careful !

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
#define M 100000
bool mark[M+5],issuper[M+5];
int su[M+5];
int k;
void prime(){   //筛选法找素数
	int i,j;
	memset(mark,1,sizeof(mark));
	mark[0]=mark[1]=0;
	for(i=2;i<=(int)sqrt(M*1.0);i++)
		if(mark[i])
			for(j=i*i;j<M;j+=i)
				mark[j]=0;
}
void rar(){   //把找到的素数存进一个数组
	k=0;
	int i;
	for(i=2;i<=M;i++)
		if(mark[i])
			su[++k]=i;
}
void findsuper(){
	int i,j;
	long long sum;
	memset(issuper,0,sizeof(issuper));
	for(i=1;i<k;i++){
		sum=su[i];
		for(j=i+1;j<=k;j++){
			sum+=su[j];
			if(sum<=M&&mark[sum])   //注意前后两个条件不能颠倒,不然各种蛋疼
				issuper[sum]=1;
		}
	}
}
int main(){
	int t,icase=1;
	int n;
	scanf("%d",&t);
	prime();
	rar();
	findsuper();
	while(t--){
		scanf("%d",&n);
		if(issuper[n])
			printf("Case %d: yes\n",icase++);
		else
			printf("Case %d: no\n",icase++);
	}
	return 0;
} 



/**************************************
	Problem id	: SDUT OJ 2404 
	Result		: Accepted 
	Take Memory	: 704K 
	Take Time	: 30MS 
	Submit Time	: 2013-06-07 21:39:11  
**************************************/


抱歉!评论已关闭.