寻找素数对

偏执的太偏执、 2022-05-15 03:59 157阅读 0赞

## 寻找素数对 ##

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

Input
    输入中是一些偶整数M(5<M<=10000). 
    Output
    对于每个偶数,输出两个彼此最接近的素数,其和等于该偶数. 
    Sample Input
    20 30 40
    Sample Output
    7 13
    13 17
    17 23

分析：

其中一个亮点就是 寻找最近的素数对 **可以从这个数的中间找！！**至于判断素数的算法 可以用筛选法 比较快

【代码总览1】：

//筛选法求素数
    #include <stdio.h>
    #include <math.h>
    #define N 10010
    int a[110000];
    int main()
    {
        int n,i,j,min,max;
        while(scanf("%d",&n)!=EOF)
        {
          for(i=2;i<=N;i++)
              a[i]=i;
              a[1]=0;
            for(i=2;i<=sqrt(N*1.0);i++)
              {
                if(a[i]!=0)
                  {
                    for(j=2;i*j<=N;j++)
                      {
                        a[i*j]=0;
                          }
                    }
              }
              int t=n/2;
              while(t!=n)
                {
                    if(a[t]!=0)
                      {
                        if(a[n-t]!=0)
                           {
                            printf("%d %d\n",n-t,t);break;
                             }
                      }
                      t++;
                }
        }
           return 0;
    }

【代码总览2】：

#include <stdio.h>
    #include <string.h>
    int sushu(int m)
    {
        int i;
        if(m==1) return 0;
        else{
        for(i=2;i<m;i++)
         if(m%i==0)
         break;
        }
        if(i>=m) return 1;
        else return 0;
    }
    int main()
    {
        int n,i;
        while(scanf("%d",&n)!=EOF){
        int t=n/2;
        for(i=t;i>0;i--)
        {
         if(sushu(i)&&sushu(n-i))
         {
       printf("%d %d\n",i,n-i);
          break;
         }
    
        }   
    }
        return 0;
    }