问题:将1到1000之间的素数打印出来。
算法描述:“筛选”法,所谓“筛选法”指的是“Eratosthenes筛法”。他采取的方法是,在一张纸上写上1到1000全部整数,然后逐个判断它们是否是素数,找出一个非素数,就把它挖掉,最后剩下的就是素数。
① 2 3 ④ 5 ⑥ 7 ⑧ ⑨ ⑩……
具体做法如下:
⑴先将1挖掉(因为1不是素数)。
⑵用2去除它后面的各个数,把能被2整除的数挖掉,即把2的倍数挖掉。
⑶用3去除它后面的各数,把3的倍数挖掉
⑷分别用4,5…各数作为除数去除这些数以后的各数。这个过程一直进行到在除数后面的数已经全被挖掉为止。事实上,只需进行到
上面的算法可以表示为:
⑴挖去1
⑵用下一个未被挖去的数p去除p后面的各数,把p的倍数挖掉。
⑶检查p是否小于的整数部分(如果n=1000,则检查p<31?),如果是,则返回⑵继续执行,否则就结束。
⑷纸上剩下的就是素数。
解题的基本思路有了,但要变成计算机的操作,还要做进一步的分析,如怎样判断一个数是否已被挖掉,怎样找出一个数p的倍数,怎样打印出来未被挖掉的数。
用自顶向下逐步细化的方法来处理这个问题,先进行“顶层设计”,见下图。也可以用流程图进行逐步细化。流程图1表示流程的粗略情况,把要做的三部分工作分别用A、B、C表示。
这三部分还不够具体,要进一步细化。A部分可以细化为图A。先输入n,然后将1输入给X1,2输入X2,1000输入给X1000。
B部分可以细化为图B。
B中的B1和B2不能再分了。B1处理的方法是:使X1=0,即哪个数不是素数,就使它等于0,以后把不等于0的数打印处理就是所求的素鼠表。B3中的循环体内以D标志的部分还要进一步细化,对D细化为图D。
图D中的E部分还不够具体,再进一步细化为图E。
图E中的F部分又细化为图F,因为首先要判断某一个Xj是否已经被挖掉,如已被挖掉则不必考虑被Xi除。至此,已不能也不需要再分解了。
图1中的C部分进行细化,得图C1。
再对图C1中的G部分进行细化,得图G。
至此,已将图1分解为能用三种基本结构表示的基本操作了。将以上这些图组合起来就可以得到最终的总流程图了,根据这个细化了的流程图已经可以用任何高级语言编写程序了。
有时间再把整个流程图组合在一起,然后把对应的程序也写一下,慢慢来吧,要走的路还长呢!