用filter函数输出素数与回文数

素数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。100以内的素数为：

2，3，5，7，11，13，17，19，23，29，31，37，41，43，47，53，59，61，67，71，73，79，83，89，97。可见素数是很“稀少”的，但是素数有无穷多个（欧几里得证明）。且至少目前素数是没有通项公式的。因此寻找素数现在都是用编程方法得到。

计算素数的一个方法是埃氏筛法，其算法如下：

首先，列出从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的倍数筛掉：

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

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

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

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

代码如下：

defprimes():

yield2

defodd():

n =2

while True:

n +=1

yieldn

defnot_in(n):

return lambdax: x % n !=

s = odd()

while True:

n =next(s)

yieldn

s =filter(not_in(n),s)

看过上一篇文章的朋友肯定发现这段代码用了两次'yield'。事实上这里面的'primes()'和'odd()'均为generator。odd()函数给出了一列由2开始的自然数序列。当

n =next(s)

yieldn

后，

s =filter(not_in(n),s)

筛选了这个序列，filter()函数把not_in(n)这个函数作用在s序列的每一个元素上，当结果为True时，元素留下，而结果为False时，元素删去。注意not_in(n)是一个函数名，即是在调用函数：

lambdax: x % n !=

lambda是个匿名函数的写法。这里用到了“闭包(Closure)”的概念。这里的x是s里的元素位置，n是not_in(n)中的参数，但是由于闭包，所以给了lambda x: x % n != 0来用。由于是个generator，所以需要如下调用：

forninprimes():

ifn

print(n)

else:

break

输出100以内的素数。

回文数指正反顺序相倒数值大小不变的自然数，如0，1，11和13431。

回文数代码如下：

defpalindrome(n):

N =str(n)

returnN == N[::-1]

output =filter(palindrome,range(1,1000))

print(list(output))

后两行为输出代码这里的filter()把palindrome()作用在range生成的序列上。str()函数把整数型转化为字符串，这样可以用切片(Slice)来操作，方便而简单。