Discuss / Python / 怎么理解素数的算法

怎么理解素数的算法

Topic source

白霓裳酱

#1 Created at ... [Delete] [Delete and Lock User]

def _odd_iter(): n = 1 while True: n = n + 2 yield n 以上是一个生产器,生成3,5,7,9,11.....无限的奇数序列

def _not_divisible(n): return lambda x: x % n > 0 返回了一个匿名函数,换个写法: def_not_divisible(n): def f(x): return x % n > 0 return f 主要是定义了筛选的规则,既x 除以n的余数不为0

def primes(): yield 2 it = _odd_iter() while True: n = next(it) yield n it = filter(_not_divisible(n), it)

这段代码逻辑稍微复杂一点,循环里面还嵌套了循环,首先要明白一点,以上定义的_odd_iter、 _not_divisible、primes 这三个函数,虽然设定的参数里面有共同的字母,比如n,但这些只是参数名字,没有任何关联,不代表上一个函数定义的n就是下一个函数输入的n。其实可以将这些参数名字换成完全不一样的字母,只要逻辑是对的就行。 因为素数数列从2开始,故先把2打印出来(yield 2),然后定义了一个迭代对象(it = _odd_iter() ),进入循环后 n = next(it) ,既显示之前定义的奇数序列的第一个数3,然后将其打印( yield n),自此已经产生了素数序列的前两个数2,3. 进入最后一句代码,用filter进行筛选,筛选的函数是以前定义的_not_divisible(n),这是其实算是在调用匿名函数f(),既换了个写法的那段代码中的f(),这个f()需要两个参数,x和n,而这个n由_not_divisible(n)传入,既是 n = next(it),也就是基数序列的第一个数3。那么参数x从哪来呢? 别忘了filter函数的作用,是将后面的序列的每一个元素带入筛选函数,故这个x是由it传入,it是什么?是_odd_iter()这个无限奇数序列的的迭代对象,可以把它想象成3,5,7,9,11.... 素数的埃氏筛法之前已经有详细描述,所以在这里既是把3,5,7,9,11....这个无限奇数序列,按照x % n > 0这个法则进行第一次筛选,既留下这个无限奇数序列中除以3后余数大于0的数列,既5,7,11....,并赋值给新的it。 自此,完成第一次的while循环。此时的素数列表已经更新为2,3,5,7,11,13,17,19....等,总之3的倍数被筛掉 然后开始第二次循环, n = next(it) 输出5,_not_divisible(n)将5代入x % n > 0,it经过第一的循环已经被更新为5,7,11....,然后用5把序列的5的倍数筛掉,类似输出7,11...并再赋值给新的it,第二次循环结束.此时素数列表已经更新为2,3,5,7,11,13...等,5的倍数被筛掉 然后第三次循环,7倍数被筛掉 .....以此类推.

最重要的两点,第一是理解筛选函数中x的来源,这也是filter函数的作用所在. 第二理解iterable和iterator,类似it就是一个发生器的迭代对象,在被储存或者被调用的时候其实是一种函数算法。

白霓裳酱

#2 Created at ... [Delete] [Delete and Lock User]

def ziranshu(): n=0 yield 0 while True: n=n+1 yield n

def bijiao(s): zifu=str(s) return zifu==zifu[::-1]

def huishu(): return filter(bijiao,ziranshu())

for i in huishu(): if i<100: print(i) else: break 这样可以输出100之内的回数,或者任意数之内的回数


  • 1

Reply