找质数算法之埃拉托斯特尼筛法(Sieve of Eratosthenes)

以前我在Project Euler上做题时很多都是跟质数有关的,而托斯特尼筛法(Sieve of Eratosthenes)是我感觉最简洁强大的,它的算法复杂度要小于O(n),典型的空间换时间算法。

 

埃拉托斯特尼筛法
 

按我的理解不同于其他用循环试除查找质数的方法,埃拉托斯特尼筛法不用除法而是用乘法。原理很简单:

  1. 假设有张表里面放了数字2到10
  2. 因为2的倍数:4、6,8,10都是合数,所以用笔划掉,剩下3、5、7、9,而第一个没有被划掉的是质数,所以3是质数(因为3不是小于3的数的倍数,也就是说不能被整除)。
  3. 划去3的倍数:9,剩下5、7,所以5是质数
  4. 划去5的倍数:无,剩下7,所以7是质数
  5. 划去7的倍数:无,没有剩下数字
  6. 查找完毕,质数是(2、3、5、7)

这个操作很像筛沙子,所以筛法因此得名吧,这里有一个在线JavaScript演示版。如果这张表长为N,一般只要划去小于等于N平方根的数的倍数就可以了,因为小于N的数如果为合数一定有一个小于等于N平方根的质数,而既然我们已经划到了N的平方根了,所以剩下的都是质数啦。

具体查找质数的编程步骤:

  1. 建立从2到N的表
  2. 找到第一个没有划掉的数p,这是个质数。如果p大于N的平方根,跳到步骤5
  3. 划掉所有没有划掉的p的倍乘
  4. 跳到步骤2
  5. 没有被划掉的都是小于等于N的质数

上个Python代码,查找小于等于65536的质数:

# -*- coding:UTF-8 -*-
import math

def main():
    # 质数筛子,小于等于65536的质数
    size = 65536
    limit = int(math.sqrt(size))
    # 多加一个,方便索引从0开始
    sieve = [True] * (size + 1)

    prime = []
    for index in range(2, limit + 1):
        if sieve[index] == True:
            # 第一个没被划掉的是质数
            prime.append(index)

            # 划掉index的倍乘
            for factor in range(index*2, size+1, index):
                sieve[factor] = False

    # 剩下的都是质数
    for index in range(limit + 1, size+1):
        if sieve[index] == True:
            prime.append(index)

    # 显示所以质数
    print prime

if __name__ == "__main__":
    main()

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注