将1到1000之间的素数打印出来

将1到1000之间的素数打印出来 例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行，即打印时不超过一页，这样的规模便于组织，也便于阅读。划分子模块时应注意模块的独立性，即使一个模块完成一项功能， 耦合性愈少愈好。