2022年 11月 9日

python3利用埃氏筛法求素数

python3利用埃氏筛法求素数@TOC

埃氏筛法,在1~n这n个连续的数里面开始筛出合数,剩下全部为素数,大致流程如下:

第一步:能够确定1不是素数,所以将1筛出,剩下从2开始的数列

第二步:找到2为第一个素数,那么遍历这个数列,将2的倍数筛出,形成一个新的数列

第三步:新的数列的第一位是下一个素数 x,此时 x = 3,那么再次遍历这个数列,筛出 x 的倍数,剩下的数再次形成一个新的数列

第四步:重复第三步,直到将所有合数筛出

先构造一个从3开始的奇数序列:

在这里插入图片描述
定义一个筛选函数,将x的倍数(不是素数的)全部筛除:

在这里插入图片描述
最后定义一个生成器,yield和next()配合使用,不断返回下一个素数:
在这里插入图片描述
这个生成器首先返回第一个素数2,然后it是生成的初始奇数序列,用next()返回序列的第一个数,前面说了序列的第一个数是素数,然后用filter筛选出it中的素数。
primes()是一个无限序列,调用时应设置一个退出循环的条件,例如打印100以内的素数,将n设置小于100
在这里插入图片描述
输出结果:
在这里插入图片描述

yield的用法及理解可以参考:yield