任何个偶数总能表示为两个素数之和
输入格式 输入一个偶数 A。
输出若干行，每行有两个素数 a b，用空格分开。 且 a+b=A， a ≤ b。
数据范围 A: [4, 1000]
样例输入：
4
样例输出：
2 2
样例输入：
10
样例输出：
3 7
5 5
思路：
为了节省时间复杂度 先创建一个素数数组 用于存放2到n的所有素数 如果在evendiv()中设置了判别素数 那么时间复杂度 将会达到O(n^3)
#include<stdio.h>
#include<math.h>
#define M 1000
void evendiv(int n);
void InPrime(int n,int p[]);
int main() {
// 输入一个偶数
int n;
scanf("%d",&n);
// 这是为了正确的输入偶数 如果不是偶数就一直输入
// n&1 相与 使用运算更快的位运算
while(n & 1 == 1) {
printf("input:\n");
scanf("%d",&n);
}
// 调用素数分解
evendiv(n);
return 0;
}
void evendiv(int n) {
// 输出若干行，每行有两个素数 a b，用空格分开。 且 a+b=A， a ≤ b
// a <= b
int p[n] = {0};
// 先把数组存起来 为了节省时间复杂度
InPrime(n,p);
for(int i = 0; i < n; i++ ) {
for(int j = i; j < n; j++) {
if(p[i]+p[j] == n) {
printf("%d %d\n",p[i],p[j]);
}
}
}
}
// 把所有的素数全部存起来
void InPrime(int n,int p[]) {
int k = 0;
for(int j = 2; j < n; j++) {
int flag = 1;
for(int i = 2; i<=(int)sqrt(j)+1; i++) {
if(j%i==0) {
flag = 0;
break;
}
}
if(flag == 1) {
p[k] = j;
k++;
}
}
}
