POJ (2262 Goldbach's Conjecture)

spoiler posted @ 2011年5月02日 15:25 in 数论 , 1117 阅读

题目大意:给你一个大于等于6的偶数,让你求出两个奇素数,a,b 满足 x=a+b; a,b也许有多对,但是只需要求出 b-a最大的那对!

题目分析: 这题直接暴力就可以了,先求出奇素数,第一队就是满足条件的了

代码://pku 2909 pku2262 hdu1397  AC代码都差不多

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int s[500020];
int flag[1000002]={0};
void init(){
	int k=1;
	for(int i=2;i<=1000000;i+=2)
		flag[k]=1;//“0”代表是奇素数,”1“代表不是!
	for(int i=3;i<=1000000;i+=2){
		if(!flag[i]){
			s[k++]=i;
			for(int j=2*i;j<=1000000;j+=i)
				flag[j]=1;
		}	
	}
}
int main(){
	init();
	 long n,i;
	while(scanf("%ld",&n),n){
		if(n%2==1)
			continue;
		long long p=n/2+1;
		for(i=1;s[i]<=p;i++){
			int k=n-s[i];
			if(!flag[k]){
				printf("%ld = %d + %d\n",n,s[i],k);
	                  	break;//注意第一对就是题目要的,这里要直接跳出了 不然TLE
			}
		}
		if(i>p)
			printf("Goldbach's conjecture is wrong.\n");//这里要不要无所谓 其实
	}
	return 0;
}

 


登录 *


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