【第五章第6节】动手试一试 题解

rosynirvana

测试编译器 clang 3.1
编译参数 -ansi -pedantic -Werror

如果你需要让程序最后暂停，那么自己加system("pause")之类的语句吧，所有题解都相同，以下不再重复说明。

首先是最平庸的解法

1. #include <stdio.h>
   
2. 
   
3. int is_prime(int);
   
4. 
   
5. int main(void)
   
6. {
   
7.   int i, j;
   
8.   for(i=4; i!=100+2; i+=2){
   
9.   /* 只用检验偶数，所以i每次自增2 */
   
10.     int upper = i / 2;
    
11.   /* c = a + b = b + a，只用检查一半的就可以了 */
    
12.     printf("%d", i);
    
13.     for(j=2; j <= upper; ++j)
    
14.       if(is_prime(j) && is_prime(i-j))
    
15.         printf("=%d+%d", j, i-j);
    
16.   /* 换行的另一种写法，少打几个字 */
    
17.     puts("");
    
18.   }
    
19.   return 0;
    
20. }
    
21. 
    
22. /* 判断一个数字是不是质数，基本上和书上的做法一样 */
    
23. int is_prime(int n)
    
24. {
    
25.   int i;
    
26.   int upper = n / 2;
    
27.   for(i=2; i<=upper; ++i)
    
28.     if(n % i == 0)
    
29.       return 0;
    
30.   return 1;
    
31. }

复制代码

snowlele

参考LZ的第一个解，自己修改了例题，得到的习题的解答，不考虑效率等因素，纯粹的小白答案。
#include <stdio.h>
#include <stdlib.h>
int main()
{
    int k,a,b,i,fa,fb;
    for(k=4;k<=100;k=k+2)
    {
        printf("%d",k);
        for(a=2;a<=k/2;a++)
        {
             //判断a是否为质数
            fa =0;
            for(i=2;i<=a-1;i++)
            {
                if(a % i == 0)
                {
                    fa=1;
                    break;
                }            
            }
            
            if(fa==0)//如果a为质数
            {
                 b=k-a;
                fb=0;
                for(i=2;i<=b-1;i++)
                {
                    if(b%i == 0)
                    {
                          fb=1;
                          break;
                    }
                }
               
                if(fb==0) //如果b也是质数
                {
                       printf("=%d+%d",a,b);
                }   
            }
        }
        printf("\n");
    }
system("pause");
return 0;
}

rosynirvana

上面的做法不是很好，存在大量的重复计算
例如分解10，程序会验证 2+8 3+7 4+6 5+5
于是就要试除计算2是不是质数，8是不是质数，3是不是质数，7是不是质数……
而这些计算中有些已经在之前的计算中做过了，例如分解8的时候，已经验证过2是不是质数，6是不是质数

所以可以把所有质数缓存起来，代码如下

1. #include <stdio.h>
   
2. 
   
3. void init(void);
   
4. int is_prime(int);
   
5. 
   
6. int prime_table[50];
   
7. /* 用来存放质数，1-100之间的质数有多少个？你可能记得是25个，不记得也不要紧，肯定不会超过50个 */
   
8. int prime_num = 0;
   
9. /* 如果不记得，那么就可以在计算的时候统计一下 */
   
10. 
    
11. int main(void)
    
12. {
    
13.   int i, j;
    
14.   init();
    
15.   for(i=4; i!=100+2; i+=2){
    
16.     int upper = i / 2;
    
17.     printf("%d", i);
    
18.     for(j=2; j <= upper; ++j)
    
19.       if(is_prime(j) && is_prime(i-j))
    
20.         printf("=%d+%d", j, i-j);
    
21.     puts("");
    
22.   }
    
23.   return 0;
    
24. }
    
25. 
    
26. void init()
    
27. {
    
28.   int i, j;
    
29.   int pos = 0;
    
30.   /* 下一个算出来的质数，存放在质数表的哪个位置？ */
    
31.   for(i=2; i!=100; ++i){
    
32.     int upper = i/2;
    
33.     int is_prime = 1;
    
34.     for(j=2; j<=upper; ++j)
    
35.       if(i % j == 0){
    
36.         is_prime = 0;
    
37.         break;
    
38.       }
    
39.     if(is_prime){
    
40.     /* 如果是质数，那么记录到质数表中，更新下一个写入的位置，然后质数的总数加一 */
    
41.       prime_table[pos] = i;
    
42.       ++pos;
    
43.       ++prime_num;
    
44.     }
    
45.   }
    
46. }
    
47. 
    
48. int is_prime(int n)
    
49. {
    
50.   int pos;
    
51.   for(pos=0; pos!=prime_num; ++pos)
    
52.     if(n == prime_table[pos])
    
53.       return 1;
    
54.   /* 扫描质数表，如果这个数字存储在质数表中，那么它就是质数，否则就不是 */
    
55.   return 0;
    
56. }

复制代码

rosynirvana

上面的做法仍然有改进空间，例如把质数表的搜索改成2分搜索；线性搜索最坏要25次，而二分搜索只要5次就可以了。
另外试除到n/2是比较慢的做法，筛质数可以参考 http://bbs.ahalei.com/thread-2961-1-2.html
但是100以内的数字实在太少，改进也难以察觉效果
不过最后还是写一个我自己比较满意的版本

1. #include <stdio.h>
   
2. 
   
3. void init(void);
   
4. int is_prime(int);
   
5. 
   
6. int prime_table[50];
   
7. int prime_num = 0;
   
8. 
   
9. int main(void)
   
10. {
    
11.   int i, j;
    
12.   init();
    
13.   for(i=4; i!=100+2; i+=2){
    
14.     int upper = i / 2;
    
15.     printf("%d", i);
    
16.     for(j=2; j <= upper; ++j)
    
17.       if(is_prime(j) && is_prime(i-j))
    
18.         printf("=%d+%d", j, i-j);
    
19.     puts("");
    
20.   }
    
21.   return 0;
    
22. }
    
23. 
    
24. void init()
    
25. {
    
26.   int i, j;
    
27.   int pos = 0;
    
28.   int div[] = {2, 3, 5, 7};
    
29.   /* 筛法，将100以内的整数用2,3,5,7筛一遍，剩下的就是质数 */
    
30.   int buf[101] = {1, 1, 0};
    
31.   for(i=0; i!=4; ++i){
    
32.     int d = div[i];
    
33.     buf[d] = 1;
    
34.     for(j=d*d; j<101; j+=d)
    
35.       buf[j] = 1;
    
36.   }
    
37.   for(i=0; i!=4; ++i)
    
38.     prime_table[pos++] = div[i];
    
39.   for(i=3; i<101; i+=2)
    
40.     if(buf[i] == 0){
    
41.       prime_table[pos++] = i;
    
42.       prime_num += 1;
    
43.     }
    
44.   prime_num += 4;
    
45. }
    
46. 
    
47. int is_prime(int n)
    
48. {
    
49.   /* 二分搜索 */
    
50.   int upper = prime_num-1;
    
51.   int lower = 0;
    
52.   while(upper >= lower){
    
53.     int mid = (upper + lower) / 2;
    
54.     if(prime_table[mid] > n)
    
55.       upper = mid - 1;
    
56.     else if(prime_table[mid] < n)
    
57.       lower = mid + 1;
    
58.     else
    
59.       return 1;
    
60.   }
    
61.   return 0;
    
62. }

复制代码

kuaile1210

楼主是写出来了.但是用了很多书上跟本没有提到的知识.我想只是看了<<啊哈C>>这本书的人看不懂.我现在也看不懂.所以这个答案没什么意义.可不可以用书上提到的知识来实现啊?让我们看看过程.学到些东西.

rosynirvana

kuaile1210 发表于 2014-5-2 18:43
楼主是写出来了.但是用了很多书上跟本没有提到的知识.我想只是看了这本书的人看不懂.我现在也看不懂.所以这 ...

请至少说下哪些部分看不懂，哪些部分用了书上没有提到的知识，这样才可能解决问题

xu1123

rosynirvana 发表于 2014-5-2 21:22
请至少说下哪些部分看不懂，哪些部分用了书上没有提到的知识，这样才可能解决问题

LZ大大写的程序都要比较后面才能学到了吧?,
应该根据我们的进程写一段代码,
我们不可能看完整本书才来做这些题目的对吧?

rosynirvana

xu1123 发表于 2014-7-6 22:51
LZ大大写的程序都要比较后面才能学到了吧?,
应该根据我们的进程写一段代码,
我们不可能看完整本书才来 ...

所以您哪里看不懂了请直接说

caihei

LS的是最接近书本进度的写法

ouch

snowlele 发表于 2014-11-21 17:36
参考LZ的第一个解，自己修改了例题，得到的习题的解答，不考虑效率等因素，纯粹的小白答案。
#include
# ...

这个方法很棒呀，非常简洁，对我们小白来说可读性高。而且是用学过的方法实现的。LZ大大的代码中的二分搜索和缓存，prime-，buf[j]等等。真是令我们一头雾水，一脸懵逼