求素数

 鉴于以前写程序那种不经过仔细思考及分析的不良习惯,觉得画流程翻还是很必要的,而且养成习惯后,对自己的思维锻炼以及高效正确编程有很大的好处。翻开大一时发的《C程序设计》第二章复习了一下,把上面一个很好的例子自己整理了一下,而且发现一个不错的画流程图的工具(Diagram Designer)。以下为全文:

      

问题:将11000之间的素数打印出来。 算法描述:“筛选”法,所谓“筛选法”指的是“Eratosthenes筛法”。他采取的方法是,在一张纸上写上11000全部整数,然后逐个判断它们是否是素数,找出一个非素数,就把它挖掉,最后剩下的就是素数。 2 3 5 7 ……

具体做法如下: 先将1挖掉(因为1不是素数)。 2去除它后面的各个数,把能被2整除的数挖掉,即把2的倍数挖掉。 3去除它后面的各数,把3的倍数挖掉 分别用45…各数作为除数去除这些数以后的各数。这个过程一直进行到在除数后面的数已经全被挖掉为止。事实上,只需进行到 上面的算法可以表示为: 挖去1 用下一个未被挖去的数p去除p后面的各数,把p的倍数挖掉。 检查p是否小于的整数部分(如果n=1000,则检查p<31?),如果是,则返回继续执行,否则就结束。 纸上剩下的就是素数。 解题的基本思路有了,但要变成计算机的操作,还要做进一步的分析,如怎样判断一个数是否已被挖掉,怎样找出一个数p的倍数,怎样打印出来未被挖掉的数。 用自顶向下逐步细化的方法来处理这个问题,先进行“顶层设计”,见下图。也可以用流程图进行逐步细化。流程图1表示流程的粗略情况,把要做的三部分工作分别用ABC表示。

这三部分还不够具体,要进一步细化。A部分可以细化为图A。先输入n,然后将1输入给X12输入X21000输入给X1000 B部分可以细化为图B B中的B1B2不能再分了。B1处理的方法是:使X1=0,即哪个数不是素数,就使它等于0,以后把不等于0的数打印处理就是所求的素鼠表。B3中的循环体内以D标志的部分还要进一步细化,对D细化为图D

D中的E部分还不够具体,再进一步细化为图E

E中的F部分又细化为图F,因为首先要判断某一个Xj是否已经被挖掉,如已被挖掉则不必考虑被Xi除。至此,已不能也不需要再分解了。 图1中的C部分进行细化,得图C1

再对图C1中的G部分进行细化,得图G

至此,已将图1分解为能用三种基本结构表示的基本操作了。将以上这些图组合起来就可以得到最终的总流程图了,根据这个细化了的流程图已经可以用任何高级语言编写程序了。

有时间再把整个流程图组合在一起,然后把对应的程序也写一下,慢慢来吧,要走的路还长呢!