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

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

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

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

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

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

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

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

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

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

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

用Python实现(迭代器):

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

def main():
    for n in primes():
        if n < 1000:
            print(n)
        else:
            break

def _odd_iter():
    n = 1
    while True:
        n = n + 2
        yield n

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

def primes():
    yield 2
    it = _odd_iter()
    while True:
        n = next(it)
        yield n
        it = filter(_not_divisible(n), it)

if __name__ == '__main__':
    main()

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

#include <stdio.h>
#define TRUE 1
#define FALSE 0
#define SIZE 10000
int main()
{
int i; /*i表示整数和对应的下标*/
int j; /*j表示正要处理的质数j之前的已处理j之后的未处理*/
int k; /*k表示正在处理的j的倍数从2开始到j*k<SIZE*/
int a[SIZE]; /*下标表示整数内容判断是否为质数*/
int *p; /*控制循环*/
for(p = a; p < a+SIZE; ++p) { /*初始化数组全是TRUE*/
    *p = TRUE;
    }
a[0] = a[1] = FALSE; /*设置前面两个不是质数的数的状态为FALSE*/
i = 2;
while(i < SIZE) { /*找到下一个质数*/
    while(a[i++] == TRUE) {
      j = i-1;
    break;
    }
for(k = 2; j*k < SIZE && i < SIZE; ++k) { /*处理质数的倍数*/
a[j*k] = FALSE;
}
}
for(p = a; p < a+SIZE; ++p) { /*打印出质数*/
if(*p == TRUE) {
printf("%8d", p-a);
}
}
printf("\n");
return 0;
}

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