素数定义为在大于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)来操作,方便而简单。
领取专属 10元无门槛券
私享最新 技术干货