埃氏筛法求素数

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

首先,列出从2开始的所有自然数,构造一个序列:

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

取序列的第一个数2,它一定是素数,然后用2把序列的2的倍数筛掉:

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

取新序列的第一个数3,它一定是素数,然后用3把序列的3的倍数筛掉:

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

取新序列的第一个数5,然后用5把序列的5的倍数筛掉:

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

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

#!usr/bin/env python
#-*-coding=utf-8-*-
def _odd_inter():   #先构造一个从3开始的奇数序列
    n = 1
    while True:
        n = n+1
        yield n
def _not_divisible(n):    #筛选函数
    return lambda x: x%n >0
def primes():    #定义一个生成器,不断返回下一个素数
    yield 2
    it = _odd_inter()  # 初始序列
    while True:
        n = next(it)   # 返回序列的第一个数
        yield n
        # 构造新序列
        it = filter(_not_divisible,it)   #出错:这里是_not_divisible(n),或者写_not_divisible,而非_not_divisible()
#给无限序列primes()设置退出循环的条件:打印1000以内的素数
for n in primes():
    if n < 1000:
        print(n)
    else:
        break

 

埃氏筛法求素数埃氏筛法求素数 采蘑菇的老姑娘 发布了2 篇原创文章 · 获赞 0 · 访问量 423 私信 关注
上一篇:File API 读取上传的文件


下一篇:Keil C51里关于堆栈指针的处理