首页 > 代码库 > 杭电 1262 寻找素数对 【素数】
杭电 1262 寻找素数对 【素数】
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1262
解题思路：先将题目中给出的偶数范围内的素数打表，设输入的那个偶数为n，这样找到n/2在素数表的位置k,从pn[k]到pn[2]；以及从pn[k]到pn[10000]依次判断相加是否等于n即可。
反思：注意像 10和26这样的偶数，应该输出的是 5 5；13 13；所以应该单独处理这种n/2等于一个素数的偶数
ps:这是在杭电的100题，这三个多月来，加油！！！！！fighting!!!!!!
#include <stdio.h>#include <math.h>#define N 10000 int p[N]; //判断p[i]中的i是否为素数int pn[N]; //存储素数void prim_num(){ int i,j,n; for(i=1; i<=N; i++) p[i]=1; n=(int)sqrt(N); for(i=2; i<=n; i++) { for(j=i+i; j<=N; j+=i) //素数的合肯定不是素数，这就是判断哪些数不是素数 { p[j]=0; } } j=1; for(i=1; i<=N; i++) //把素数存储入pn[N],下表从1开始 { if(p[i]) { pn[j++]=i; } }}int main(){ int i,j,k; int n; prim_num(); while(scanf("%d",&n)!=EOF) { int flag=1; for(i=2;i<N;i++) { if(n/2==pn[i]) { k=i; break; } if(n/2>pn[i]&&n/2<pn[i+1]) { k=i; break; } } for(i=k;i>=0&&flag;i--) { for(j=i;j<N;j++) { if(pn[i]+pn[j]==n) { printf("%d %d\n",pn[i],pn[j]); flag=0; } } } } return 0;}
杭电 1262 寻找素数对 【素数】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。