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;
}