python素数筛算法实现

python中有列表生成式这种机制,可以很方便的产生一个无穷可列的序列。另外python中提供了filter函数,该函数可以作用在任何可迭代的对象上,更重要的是该函数的结果本质上是一个生成式,也就是惰性序列。

结合以上几点可以很容易的使用python实现素数筛的算法。
1.一个无穷序列,从自然数2一次递增
2.依次得到一个素数,并使用该素数对无穷序列进行筛选,只留下无法整除的
3.使用筛选结果更新无穷序列

代码如下:

#! /usr/bin/evs pthon3
# -*- encoding = utf-8 -*-

__author__ = 'www.iaccepted.net'

def _sequences():
	start = 2
	while True:
		yield start
		start += 1

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

def primes():
	ite = _sequences()
	while True:
		n = next(ite)
		yield n
		ite = filter(_not_divisible(n), ite)

i = 0
g = primes()
while i < 10:
	print(next(g))
	i += 1

filter函数要求输入一个函数,和一个可迭代对象,并将该函数应用到可迭代对象中的所有元素,通过筛选的元素组成一个新的序列返回。这里_not_divisible函数就利用了闭包,将传入的n作为除数,保存在闭包中,然后将该lambda表达式作用域序列中的每一个元素进行筛选。

本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:python素数筛算法实现

本文链接地址:http://www.iaccepted.net/python/knowledge-tree/142.html

相关文章



发表评论

电子邮件地址不会被公开。 必填项已用*标注