求质数是一个很普遍的问题, 通常不外乎用数去除, 到除不尽时, 给定的数就是质数。但是早在2000年前人们就知道了一个不必用除法而找出2~N的质数的所有方法了。假设有一个很神奇的筛子, 可以给出一个数,例如 i,这个筛子有办法把 i 的所有倍数去掉。请用这个方法求出2~N之间的所有质数。这个方法称为 Eratosthenes(人名)筛法(Sieve Mothod)

说明:下面通过一个例子来加强对筛法的印象,求出2~40之间的质数。首先,把2~40这
些数一字排开:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

2是质数, 所以把2的倍数都筛掉

3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39

下一个数自然是质数3, 所以把3的倍数都筛掉

5 7 11 13 17 19 23 25 29 31 35 37

下一个是5, 把5的倍数筛掉

7 11 13 17 19 23 29 31 37

下一个是7, 把7的倍数筛掉(其实在此之前都已经筛掉了)

11 13 17 19 23 29 31 37

再下来是11, 比20/2大了, 所以工作停止, 没有被筛掉的就是质数, 它们是2,3.5,
7,11,13,17,19,23,29,31,37。

可以按照这一逻辑来编写程序,但是需注意下面几点:

1. 2是质数,所以2的倍数是一定会被删除的,所以在一开始时根本没有把2的倍
   数放到筛子中的必要,这就省下了一半的空间。

2. 如果要求2~N之间的质数,做到N/2就可以停下来,因为大过N/2的数都不可
   能整除N

3. 程序不可以使用乘法与除法,只能用加或减,以求加快速度。

请基于这3项要求来编制程序。

解答见sieve.py