以前我在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()