高效率素数生成 - 埃拉托色尼筛选法

计算素数的一个方法是埃氏筛法，它的算法理解起来非常简单：

(1).首先，列出从2开始的所有自然数，构造一个序列：

1
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...

(2).取序列的第一个数2，它一定是素数，然后用2把序列的2的倍数筛掉：

1
3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...

(3).取新序列的第一个数3，它一定是素数，然后用3把序列的3的倍数筛掉：

1
5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...

(4).取新序列的第一个数5，然后用5把序列的5的倍数筛掉：

1
7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...

不断筛下去，就可以得到所有的素数。

用Python实现(迭代器):

1
#!/usr/bin/env python3
2
# -*- coding: utf-8 -*-
3

4
def main():
5
    for n in primes():
6
        if n < 1000:
7
            print(n)
8
        else:
9
            break
10

11
def _odd_iter():
12
    n = 1
13
    while True:
14
        n = n + 2
15
        yield n
16

17
def _not_divisible(n):
18
    return lambda x: x % n > 0
19

20
def primes():
21
    yield 2
22
    it = _odd_iter()
23
    while True:
24
        n = next(it)
25
        yield n
26
        it = filter(_not_divisible(n), it)
27

28
if __name__ == '__main__':
29
    main()

类似的,可以使用C语言实现(百度):

1
#include <stdio.h>
2
#define TRUE 1
3
#define FALSE 0
4
#define SIZE 10000
5
int main()
6
{
7
int i; /*i表示整数和对应的下标*/
8
int j; /*j表示正要处理的质数j之前的已处理j之后的未处理*/
9
int k; /*k表示正在处理的j的倍数从2开始到j*k<SIZE*/
10
int a[SIZE]; /*下标表示整数内容判断是否为质数*/
11
int *p; /*控制循环*/
12
for(p = a; p < a+SIZE; ++p) { /*初始化数组全是TRUE*/
13
    *p = TRUE;
14
    }
15
a[0] = a[1] = FALSE; /*设置前面两个不是质数的数的状态为FALSE*/
16
i = 2;
17
while(i < SIZE) { /*找到下一个质数*/
18
    while(a[i++] == TRUE) {
19
      j = i-1;
20
    break;
21
    }
22
for(k = 2; j*k < SIZE && i < SIZE; ++k) { /*处理质数的倍数*/
23
a[j*k] = FALSE;
24
}
25
}
26
for(p = a; p < a+SIZE; ++p) { /*打印出质数*/
27
if(*p == TRUE) {
28
printf("%8d", p-a);
29
}
30
}
31
printf("\n");
32
return 0;
33
}

其他语言亦可以轻松实现.