歌德巴赫猜想
Time Limit:4000MS Memory Limit:65536KB
Description
歌德巴赫猜想，是指對于每一個(gè)大于4的偶數(shù)ｎ，都能表示成兩個(gè)質(zhì)數(shù)之和。
現(xiàn)在，你需要寫程序驗(yàn)證這一猜想。對于n，找出質(zhì)數(shù)a和b, 滿足a+b=n, a≤b，且a*b最大。例如n=8，滿足條件的a和b分別為3和5；
又如n=10，質(zhì)數(shù)3、7以及5、5滿足a+b=n, a≤b，而乘積大的那組是5、5。
Input
每行一個(gè)偶數(shù)n（4 < n <= 20000）
Output
對應(yīng)于每個(gè)輸入的偶數(shù)，輸出a、一個(gè)空格、b、一個(gè)換行符
Sample Input
8
10
1000
Sample Output
3 5
5 5
491 509
Source
09級10級編程能力測試1
素?cái)?shù)篩法，重要不等式
1 #include <stdio.h>
2 #include <string.h>
3
4 #define L 20009
5
6 int prime[ L ];
7
8 void initPrime() {
9 int i, j;
10 memset( prime, 0xff, sizeof(prime) );
11 prime[ 0 ] = prime[ 1 ] = 0;
12 for ( i = 2; i < L; ++i ) {
13 if ( prime[ i ] ) {
14 for ( j = i+i; j < L; j += i ) {
15 prime[ j ] = 0;
16 }
17 }
18 }
19 }
20
21 int main() {
22 int n, a, b;
23 initPrime();
24 while ( scanf( "%d", &n ) == 1 ) {
25 a = b = n / 2;
26 while ( (prime[a]==0) || (prime[b]==0) ) {
27 --a;
28 ++b;
29 }
30 printf( "%d %d\n", a, b );
31 }
32 return 0;
33 }
34