Question

这次再请思考求解“判定91是否是素数”这一问题的算法。在用于判定素数的典型算法中，有一个被称为“埃拉托斯特尼筛选法”的算法，在学习这个算法前，先请思考如果是在数学考试中遇到这道题，如何解答呢？

也许有人会这样想：用91分别除以比较它小的所有正整数，如果没有找到能够整除的数，那么91就是素数。但，如此繁琐的步骤可行吗？实际上这就是正确答案。埃拉托斯特尼筛选法是一种用于把某个范围内的所有素数筛选出来的算法，比如筛选100以内的所有素数，其基本思路就是用待判定的数除以比较它小的所有正整数。例如要判定91是否是素数，只要分别除以2-90之间的每个数就可以了（因为1肯定能够整除任何数，所以从2开始检测）。这个步骤用程序表示的话，就变成了如代码清单5.2所示的代码。Mod是用于求除法运算中余数的运算符。如果余数为0则表示可以整除，因此也就知道待判定的数不是素数了，程序执行结果如图5.4所示

代码清单5.2 判定是否是素数的程序

a=91

s=”素数”

For i=2 to (a-1)

If a Mod i =0 Then

s=”不是素数”

Exit For

End If

Next

MsgBox CStr(a)&s

图5.4 代码清单5.2的执行结果

无论是多么冗长的繁琐的步骤，只要明确并且机械就能构成优秀的算法。把算法用程序表示出来让计算机去执行，而计算机会用令人吃惊的速度进行运算。为了判定91是否是素数，用91除以2-90这89个数据的操作一瞬间就可以完成。在思考算法时不妨时刻记着，解决问题时是利用计算机的处理速度的

作为利用计算机的处理速度解决问题的另外一个例子，请试着求解以下联立方程组。题目是鸡兔同笼问题：鸡和兔子共计10只，把它们的脚加起来共计32只，问鸡和兔子分别有多少只？设有x只鸡，y只兔子，那么就可以列出如下的联立方程组

x+y=10

2x+4y=32

因为鸡和兔子的只数应该都在0-10范围内，所以就试着把0-10中每个数依次代入x和y，只要能够找到使这两个方程同时成立的数值也就求出了答案。利用计算机的处理速度，答案一瞬间就出来了（如代码清单5.3和图5.5所示）

代码清单5.3 求解鸡兔同笼问题的程序

For x=0 To 10

For y=0 To 10

a=x+y

b=2*x+4*y

If(a=10) And (b=32) Then

MsgBox”鸡=”&CStr(x)&”兔子=,”&CStr(y)

End If

Next

Next

图5.5 代码清单5.2的执行结果