埃拉托色尼筛选法巧解质数问题

质数问题很有趣,也是常见的程序员面试问题,例如,找出N以内的所有质数。

这个问题本身不难,直觉可以使用排除法。例如,从2到N,每个数判断是否有1和它本身以外的其他因数。当然,聪明一点,会发现我们根本不需要遍历N以内的所有数来判断N是否为质数,最多实验N的平方根以内数就足够。因为,N有因数的话,那么至少有一半的因数不会超过N的开平方。要判断100是不是质数,100 = 2*50 = 4*25 = 5*20 = 10*10,只要判断10以内有无100的因数即可。使用这种方法的时间复杂度为 $O(n*sqrt(n))$。

有没有更快速的算法呢?当然是有的——埃拉托色尼筛选法。

埃拉托色尼筛选法

埃拉托色尼筛选法(Sieve of Eratosthenes)简称埃氏筛法,由古希腊数学家埃拉托色尼提出,核心思想非常简单,先看动图感受一下:
Sieve of Eratosthenes

首先将1排除,找到n以内所有质数方法:

  1. 创建从2到n的连续整数列表,(2,3,4,…,n);
  2. 初始化p=2,这是最小的质数;
  3. 枚举所有p的倍数,除p外都标记为非质数,(2p,3p,4p,…);
  4. 找到下一个没有标记大于p的数。如果没有,结束运算;如果有,将该值赋予p,重复步骤3;
  5. 运算结束后,剩下所有未标记的数都是找到的质数。

这个算法的核心思想是:任何一个p值都是质数,如果存在一个合数,那么就应该存在一个质数都够标记它。算法的时间复杂度为O(n loglog n)。

进一步简化的优化算法:

  1. 对于步骤3,可以不用从2p开始排除,而是直接从p^2开始。理由已经在开始讲过,所有的小于p^2的合数都因为有更小的因数而被排除。
  2. 对于步骤4,当p^2大于n的时候停止计算。

另一个优化思路:只初始化奇数列表,这种方法可以被概括为轮分解(Wheel factorization),是一种效率更高的寻找质数的办法。

算法实现

这里推荐python匿名函数的写法,和埃氏筛法一样简洁明了:

1
2
3
import math
def getPrime(n):
return filter(lambda x: not [x%i for i in range(2, int(math.sqrt(x))+1) if x%i == 0], range(2,n+1))