题目

Description

歌德巴赫猜想,是指对于每一个大于4的偶数n,都能表示成两个质数之和。 现在,你需要写程序验证这一猜想。对于n,找出质数a和b, 满足a+b=n, a≤b,且a*b最大。例如n=8,满足条件的a和b分别为3和5; 又如n=10,质数3、7以及5、5满足a+b=n, a≤b,而乘积大的那组是5、5。 Input

每行一个偶数n(4 < n <= 20000)

Output

对应于每个输入的偶数,输出a、一个空格、b、一个换行符

Sample Input

8 10 1000 Sample Output

3 5 5 5 491 509

代码

#include<stdio.h>
#include<math.h>
 
bool isPrime(int x); 
int main()
{
    int n,i,j;
    while (scanf("%d",&n) != EOF)
    {
        for (i = n/2;i > 0;i -= 2)
        {
            if(i%2 == 0)
                i --;
            j = n - i;
        if(isPrime(i)&&isPrime(j))
        {
                printf("%d %d\n",i,j);
                break;
        }
        }
    }
    return 0;
}
bool isPrime(int x)
{
    int len = sqrt((float)x);
    for (int i = 2;i <= len;i ++)
    {
        if(x % i == 0)
            return false;
    }
    return true;
}