哥德巴赫猜想认为“每一个大于2的偶数,都能表示成两个质数之和”。
给定一个大于2的偶数N,你能找到两个质数P和Q满足P<=Q并且P+Q=N吗?
Input
一个偶数N(4 <= N <= 1000000)
Output
输出P和Q。如果有多组解,输出P最小的一组。
Sample Input
10
Sample Output
3 7
#include <cstdio>
using namespace std;
int prime[1000000+5] = { 1,1 };
int main()
{
int i, j;
for( i=2; i<=500000; i++ ){ /*打表标记素数*/
if( prime[i] )
continue;
else /*这里我写成i<=1000000 然后一输入就奔溃*/
for( j=i+i; j<= 1000000; j += i )
prime[j] = 1;
}
int num;
scanf("%d", &num );
//num = num /2; 不能这想着这样简化循环,不然会影响下面的num-i,最后加个break就行*/
for( i=2; i<= num; i++ ){
if( !prime[i] && !prime[num-i] ){
printf("%d %d\n", i, num-i ); /*输出最小的一组*/
break;
}
}
return 0;
}