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

(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开始到jk<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; jk < 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;
}
其他语言亦可以轻松实现.