首页 > ACM题库 > HDU-杭电 > HDU 1262 寻找素数对-模拟-[解题报告] C++
2013
12-04

HDU 1262 寻找素数对-模拟-[解题报告] C++

寻找素数对

问题描述 :

哥德巴赫猜想大家都知道一点吧.我们现在不是想证明这个结论,而是想在程序语言内部能够表示的数集中,任意取出一个偶数,来寻找两个素数,使得其和等于该偶数.
做好了这件实事,就能说明这个猜想是成立的.
由于可以有不同的素数对来表示同一个偶数,所以专门要求所寻找的素数对是两个值最相近的.

输入:

输入中是一些偶整数M(5<M<=10000).

输出:

对于每个偶数,输出两个彼此最接近的素数,其和等于该偶数.

样例输入:

20 30 40

样例输出:

7 13
13 17
17 23

题目描述:输入一个偶数,判断这个偶数可以由哪两个差值最小的素数相加,输出这两个素数。

题目分析:模拟题,注意的是为了提高效率,在逐个进行判断时,只要从2判断到n/2就可以了,并且最好用打表法判断素数。代码附上。。。

#include<cstdio>
 #include<cstring>
 #include<cmath>
 const int MAX = 10005;
 bool prim[MAX];
 void dabiao() {           //先打素数表 
     memset(prim,0,sizeof(prim));
     for(int i = 4;i<=MAX;i+=2)
     prim[i] = 1;
     int d = sqrt(MAX);
     for(int i = 2;i<d;++i) {
         if(prim[i])
         continue;
         for(int j = i*i;j<MAX;j+=i)
         prim[j] = 1;
     }
 }
 int main( ) {
     int n;
     dabiao();
     while(scanf("%d",&n)!=EOF) {
         int loc,MIN = MAX;
         for(int i = 2;i<=n/2;++i)
         if(!prim[i]&&!prim[n-i]&&(n-2*i)<MIN)
         loc = i;
         printf("%d %d\n",loc,n-loc);
     }
     return 0;
 }

 

 


  1. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。