《C程序设计》例2-22详解
- 格式：doc
- 大小：245.50 KB
- 文档页数：4
例2-22 将1到1000之间的素数打印出来
我们已在本章中讨论过判别素数的方法，现在采用“筛法”来求素数表。
所谓“筛法”指的是“埃拉托色尼(Eratosthenes)筛法”。
他是古希腊的著名数学家。
他采取的方法是，在一张纸上写上1到1000全部整数，然后逐个判断它们是否素数，找出一个非素数，就把它挖掉，最后剩下的就是素数，见图2.37。
具体做法如下：
(1) 先将1挖掉(因为1不是素数)。
(2) 用2去除它后面的各个数，把能被2整除的数挖掉，即把2的倍数挖掉。
(3) 用3去除它后面各数，把3的倍数挖掉。
(4) 分别用4、5…各数作为除数去除这些数以后的各数。
这个过程一直进行到在除数后面的数已全被挖掉为止。
例如在图2.37中找1～50的素数，要一直进行到除数为47为止。
(事实上，可以简化，如果需要找1～n范围内素数表，只需进行到除数为n开方(取其整数) 即可。
例如对1～50，只需进行到将7(50开方)作为除数即可。
)
上面的算法可表示为：
(1) 挖去1；
(2) 用下一个未被挖去的数p去除p后面各数，把p的倍数挖掉；
(3) 检查p是否小于n的整数部分(如果n=1000，则检查p＜31?) ，如果是，则返回(2) 继续执行，否则就结束；
(4) 纸上剩下的数就是素数。
解题的基本思路有了，但要变成计算机的操作，还要做进一步的分析，如怎样判断一个数是否已被“挖掉”，怎样找出某一个数p的倍数，怎样打印出未被挖掉的数。
用自顶向下逐步细化的方法来处理这个问题，先进行“顶层设计”，见图2.38。
也可以用流程图进行逐步细化。
流程图2.39表示流程的粗略情况，把要做的三部分工作分别用A、B、C表示。
这三部分还不够具体，要进一步细化。
A部分可以细化为图2.40。
先输入n，然后将1输入给x1，2输入给x2，1000输入给x1000。
B部分可以细化为图2.41。
图2.41中的B1与B2不能再分了。
B1处理的方法是：使x1=0，即哪个数不是素数，就使它等于0，以后把不等于零的数打印出来就是所求的素数表。
B3中的循环体内以D标志的部分还要进一步细化，对D细化为图2.42。
图2.42中的E部分还不够具体，再进一步细化为图2.43。
图2.43中的F部分又细化为图2.44。
因为首先要判断某一个xj是否已被挖掉，如已被挖掉则不必考虑被xi除。
至此，已不能也不需要再分解了。
再对图2.39中的C部分进行细化，见图2.45。
对图2.45中的G部分进行细化，得图2.46。
至此，已将图2.39分解成为能用三种基本结构表示的基本操作了。
将以上这些图合起来得到总的流程图，见图2.47。
根据这个细化了的流程图已经可以用任何高级语言编写出源程序了。
以上是用流程图表示逐步细化的过程，如果题目复杂，则画许多分流程图也是比较费事的。
本例为了说明问题把细化过程分解得比较细，如果技巧熟悉些，可以精简一些步骤。
例如从图2.39的C部分可以直接画出图2.47的C部分，而不必经过图2.45和图2.46。
图2.47
也可以用伪代码来描述逐步细化过程，由于不需要画流程图，因此便于修改。
例如，想对“ 打印全部素数”这一句话细化，只需将这句擦掉，在原处填入细化了的伪代码语句即可，或者将它向右展开，逐级细化。
例如：
输入1～n各数……
把所有非素数去掉……
打印全部素数
i=1
while i≤n
{把未挖的xi打印出来（if xi不等于0 then print xi ）
i=i+1}
对熟悉伪代码的人来说，可能这样更方便些。
在程序设计中常采用模块设计的方法，尤其是当程序比较复杂时，更有必要。
在拿到一个程序模块(实际上是程序模块的任务书) 以后，根据程序模块的功能将它划分为若干个子模块，如果嫌这些子模块的规模大，还可以划分为更小的模块。
这个过程采用自顶向下的方法来实现。
程序中的子模块在C语言中通常用函数来实现。
例如在上例中，可以将图2.39的A、B、C三部分分别作为三个子模块，用三个函数来实现。
程序中的子模块一般不超过50行，即打印时不超过一页，这样的规模便于组织，也便于阅读。
划分子模块时应注意模块的独立性，即使一个模块完成一项功能，耦合性愈少愈好。
