coreBugZJ

此 blog 已弃。

歌德巴赫猜想,EOJ 2877

歌德巴赫猜想

Time Limit:4000MS Memory Limit:65536KB


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

Source

09级10级编程能力测试1



素数筛法,重要不等式

 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, 0xffsizeof(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 


posted on 2011-03-30 20:45 coreBugZJ 阅读(233) 评论(0)  编辑 收藏 引用 所属分类: ACM


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理