歌德巴赫猜想 (速筛)

哥德巴赫猜想认为“每一个大于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;
}