PTA 7-236 验证哥德巴赫猜想

哥德巴赫猜想之一是指一个偶数（2除外）可以拆分为两个素数之和。请验证这个猜想。
因为同一个偶数可能可以拆分为不同的素数对之和，这里要求结果素数对彼此最接近。

输入格式:

首先输入一个正整数T，表示测试数据的组数，然后是T组测试数据。每组测试输入1个偶数n（6≤n≤10000）。

输出格式:

对于每组测试，输出两个彼此最接近的素数a、b（a≤b），两个素数之间留1个空格。

输入样例:

2
30
40

输出样例:

13 17
17 23

思路：

1. 定义一个全局数组 prime，用于存储从6到10000之间所有的素数，空间要足够大，否则会段错误

2. 调用 is_prime 函数检查6到10000之间的每个整数是否为素数，并将素数存入 prime 数组

3. 查找能够相加得到该偶数的一对素数，并且这对素数的差距尽可能小

/*
一个偶数（2除外）可以拆分为两个素数之和
两个素数a、b彼此最接近
*/

#include <stdio.h>
#include <math.h>

int prime[5000];// 统计6~10000间的所有素数(数组给太小会段错误)
int is_prime(int x)
{
    int flag=1;
    if(x==1)
        flag=0;
    for(int i=2;i<=sqrt(x);i++)
    {
        if(x%i==0)
        {
            flag=0;
            break;
        }
    }
    return flag;
}

void two_prime(int sum,int cnt)
{
    int a,b;
    for(int i=0;i<cnt;i++)// a<=b
    {
        for(int j=i;j<cnt;j++)
        {
            if((prime[i]+prime[j] == sum))
            {
                a=prime[i];b=prime[j];
            }
        }
    }
    printf("%d %d\n",a,b);
    // for(int i=0;i<10;i++)
    //     printf("%d ",prime[i]);
    // printf("\n");
}
int main()
{
    int T,num;
    int cnt=0;
    for(int nums=6;nums<=10000;nums++)
    {
        if(is_prime(nums))
            prime[cnt++]=nums;
    }
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&num);
        two_prime(num,cnt);
    }
    return 0;
}