文章目錄

试编写一个程序,找出前 N(如200)个质数。如果没有进一步要求,这不是难题。但再次希望从所知的、使用除法的方法中,用最快的办法来编写程序.

说明: 可能最先想到的办法,就是让某个变量 i 从 2 变到 N,然后检查它是不是质数,如果是就显示出来,如果不是,就检查下一个。这是正确的做法,但却没有注意到一个小细节,因而使程序运行速度变慢。当然,2是质数,但所有 2 的倍数都不是质数,如果令 i 从 2 变到 N, 不就很冤枉的测试了 4,6,8,10,…这些数? 所以第一点提示是测试 2,3,5,7,…,N, 即 2 与所有奇数就足够了。同理,3 是质数,但 6,9,12,…这些3的倍数却不是,因此,如果能把 2 与 3的倍数都跳过去而不测试,任意连续的 6个数中,就只会测试两个而已。以6n,6n + 1,6n + 2, 6n + 3, 6n + 4, 6n + 5为例,6n, 6n + 2, 6n + 4是偶数, 6n + 3是3的倍数, 所以如果把 2 与 3 的倍数都不理会,要测试的数就只留下6n + 1与6n + 5而已,因而工作量之时前述想法的2 / 6 = 1/3, 应该用这个办法去编写程序。

假如i 是如上述的一个数(不是2 与 3 的倍数), 如何测试 i 是个质数呢? 按照定义 i 如果是质数, 也就只有 1 与 i 可以除尽自己,所以可以用2, 3, 4, 5, 6, …, i - 1去除 i, 如果都除不尽(余数不是0), i 就是质数。观点也对,但却与上一点一样地笨拙。当 i > 2 时,有哪一个数 i 可以被 i - 1除尽的? 没有, 为什么? 如果 i 不是质数, 那么 i = a b, 此地 a 与 b 既不是 i 又不是 1; 正因为 a > 1, a 至少是2, 因此 b 最多是 i / 2而已,去除 i 的数用不着是 2,3,4,…,i - 1, 而用 2,3,4,…, i / 2就可以了。 不但如此,因为 i = a b, a 与 b 不能大于sqrt(i)(即i的平凡根), 为什么呢? 如果a > i 的平方根, b > i 的平方根, 于是a * b > i, 因此就都不能整除i了。如果 i 不是质数, 它的最大因子就是sqrt(i); 换言之,用2,3,4,5,…,sqrt(i)去除 i 就行了。

但是, 用2,3,4,5,…,sqrt(i)去除i也是个浪费。就像前一段所说的,2除不尽,2的倍数也除不尽;同理 3 除不尽,3 的倍数也除不尽……最理想的方法就是用质数去除 i, 因为在前一段的提示, i 不是 2 与 3的倍数,所以就用5, 7, 11, 13, 17, 19,…这些比sqrt(i)小的质数去除 i 即可。

但问题是这些质数从何而来? 这比较简单,可以准备一个数组prime[], 用于存放找出来的质数, 一开始它应该有2 、3与5。于是当 i = 5,7,11,13,17,19,23,25,29,…这些不是 2 与 3 的倍数时,就用prime[]中小于 sqrt(i)的数去除 i 即可,如果都除不尽,i 就是质数,把它放入prime[]中,因此prime[]中的质数就会越来越多,直到满足所要的个数为止。

不妨用这段说明来编写程序,不过应注意下面几点:

  1. 不要处理2 与 3 的倍数(见第一段)
  2. 用质数去除(见第二、三段).
  3. 用i的平方根可能会有问题,为什么?有什么办法可以解决?

解答见prime_one.py

文章目錄