哥德巴赫猜想进阶：就是指任何一个大于2的偶数，都可以写成两个素数的和。现在输入一个偶数，要求寻找两个素数，使其和等于该偶数。由于可能有多组素数对满足条件，所以本题要求输出两数差最小的那两个素数。

Question

1224 哥德巴赫猜想

题目描述

所谓哥德巴赫猜想，就是指任何一个大于2的偶数，都可以写成两个素数的和。现在输入一个偶数，要求寻找两个素数，使其和等于该偶数。由于可能有多组素数对满足条件，所以本题要求输出两数差最小的那两个素数。

输入要求
输入一个偶整数M，M大于2。

输出要求
对于每个偶数，输出两个彼此最接近的素数，并且其和等于该偶数。（输出时两个素数小的在前，大的在后）。

输入样例
20

输出样例
7 13

问题相关代码，请勿粘贴截图

int main()
{
    int m,d,f,i,j,k=0,key,min;
    int sushu(int n);
    scanf("%d",&m);
    for(i=2;i<=m-1;i++)
    {
        for(j=m;j>=2;j--)
        {
            d=sushu(i);
            f=sushu(j);
            if(d&&f&&(i+j==m)&&i<=j)
            {
               // __________________________________________
                //我的思路在这里就没办法进行了
                //到这里可以直接输出多组素数对，但是不知如何输出差最小
            }
        }
    }
    return 0;
}

int sushu(int n)
{
    int i,a=1;
    if(n==2)
        return 1;
    if(n==3)
        return 1;
    for(i=2;i<=sqrt(n);i++)
    {
        if(n%i==0)
        {
            a=0;
            break;
        }
    }
    return a;
}

运行结果及报错内容

我的代码能够输出所有满足多组素数对的结果，但是我不知道怎么去求两数差最小的那两个素数对。

还有一个问题是，尝试着存储多组数据，通过比较输出最小，但是造成运算超时了。

希望有更好的办法解决运算速度的问题！

Answer 1

修改如下，供参考：

#include <stdio.h>
int main()
{
    int m,d,f,i,j,k=0,key,min;
    int sushu(int n);
    scanf("%d",&m);
    for(i = m/2;i > 1 ;i--)
    {
        if(sushu(i) && sushu(m-i)){
           printf("%d %d",i,m-i);
           break;
        }
    }
    return 0;
}

int sushu(int n)
{
    int i;
    if(n<=3) return n>1;
    for(i=2;i*i<=n;i++)
       if(n%i == 0) return 0;
    return 1;
}