hdu hdoj 1262 寻找素数对.doc

问题描述 寻找素数对 Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 3456????Accepted Submission(s): 1701 Problem Description 哥德巴赫猜想大家都知道一点吧.我们现在不是想证明这个结论,而是想在程序语言内部能够表示的数集中,任意取出一个偶数,来寻找两个素数,使得其和等于该偶数.做好了这件实事,就能说明这个猜想是成立的.由于可以有不同的素数对来表示同一个偶数,所以专门要求所寻找的素数对是两个值最相近的. ? Input 输入中是一些偶整数M(5M=10000). ? Output 对于每个偶数,输出两个彼此最接近的素数,其和等于该偶数. ? Sample Input 20 30 40 ? Sample Output 7 13 13 17 17 23 ? Source 浙江工业大学第四届大学生程序设计竞赛 ? Recommend JGShining #include iostream using namespace std; const int max_num=10001; int flag_prime[max_num]; int prime[max_num/3]; int len=0; void get_prime() { int i,j; for(i=2;imax_num;i++) { if(flag_prime[i] == 0) prime[len++]=i; for(j=0;jlen i*prime[j]max_num;j++) { flag_prime[i*prime[j]]=1; if(i%prime[j] == 0) break; } } } int main() { int pre,last; int n; int num; get_prime(); while(cinn) { num=n/2; last=0; while(prime[last]num) { last++; } while(true) { pre=last; while(prime[last]+prime[pre]n) { pre--; } if(prime[last]+prime[pre]==n) break; last++; } coutprime[pre] prime[last]endl; } return 0; } 蔡尚真 代码；阮凯云 2011-10-25整理