以下是古希腊人发现的一种系统性的筛选较小质数的高效方式,目的就是找到一种能很快剔除非质数的有效方法。首先,依次写下1到100的所有数字。然后剔除掉数字1。(前文已经提到过,虽然古希腊人将1视为质数,但21世纪的我们不再这么认为了。)接下来看第二个数字2,它是第一个质数。然后将2之后每隔一个的数字全部剔除掉。这样便可以一下子将所有2的倍数都筛掉了,也就是剔除掉除2以外的所有偶数。数学家喜欢开玩笑说,因为2是唯一一个偶质数,因此2也是个奇质数(odd prime)。4不好笑吧?幽默大概并非数学家的强项。
4英语中的odd既表示奇数,也表示奇怪。——译者注
图 1-18 剔除2之后的每隔一个的数字
现在我们看到的最小的而且还未被剔除的那个数字就是3,然后再系统地剔除那些是3的倍数的数字。
图 1-19 剔除3之后的每隔二个的数字
因为4已经被剔除掉了,我们直接来看数字5,然后将所有数字5以后的每隔四个数字的数字都剔除。接下来就是不断重复这一过程,每次剔除完后,回到前面最小的一个还未被排除的数字n,然后将其后每隔(n-1)个数字的数字都剔除掉:
图 1-20 最后,我们便得出了100以内的所有质数(www.daowen.com)
上述方法的美妙之处就在于它是非常机械化的,不需要动太多脑力就能完成。比如,数字91是质数吗?如果你使用上述方法,那么你根本就勿需思考。当你在剔除所有7之后的每隔6个数字的数字时,因为91=7×13,它就已经被剔除了。但话说回来,91的确是个不容易确定的数字,通常在我们背乘法表的时候,不会涉及13倍这么大的倍数。
以上这种系统化的操作方法是一个很好的程序算法,即通过采用一套特定指令来解决问题,这便是计算机程序的基本运行原理。这一特定算法出现在两千年前一个活跃的数学发源地:亚历山大港。亚历山大港位于当今埃及境内,是当时古希腊帝国的前哨城市之一,据称拥有全世界最好的图书馆。大约在公元前三世纪,图书管理员埃拉托斯特尼发明了这个最早的用于寻找质数的计算机程序。
它被称为埃拉托斯特尼筛法,因为,在每次剔除非质数的过程中,就好像你在使用一个网格筛子,根据不断出现的新质数设定相应网格之间的间距。第一次使用筛子时,每两条网格相隔1个数字,然后相隔2个,然后相隔4个,以此类推。唯一的问题是当我们尝试筛选较大的质数时,这个方法就不那么高效了。
除了筛选质数以及照管图书馆中的成千上万的纸莎草纸和牛皮纸卷以外,埃拉托斯特尼还计算出地球的圆周长度,以及地球和太阳及月亮之间的距离。他计算出太阳与地球的距离是804 000 000个运动场的距离,不过他用的这种测量单位让人很难评估数据的准确性。我们应该以哪种运动场的长度作为一个斯塔德呢?是温布利大球场,还是小一点儿的比如洛夫特斯路的球场?
除了测量太阳系的大小以外,埃拉托斯特尼还绘制出了尼罗河的河道图,并首次给出了尼罗河频繁泛滥的准确原因:远在埃塞俄比亚的河流源头处的大雨。他还创作诗歌。尽管他有这么多成就,朋友们还是给他起了一个外号,叫做贝塔,因为他哪件事都不精通。据悉,暮年的他双目失明,绝食自尽。
你现在就可以在蛇梯棋棋盘上实践埃拉托斯特尼筛法,每剔除一个数,就把一截意面放在那个数所在的格子里。剩下的就都是质数了。
免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。