使⽤列表实现筛选法求素数（利⽤python的内置函数，快速求素数）
代码如下：（具体内置函数可以⾃⾏搜索，我主要记录这样求素数的原理即好处，帮助⼤家和⾃⼰体验⼀下这种⾼级的感觉【来⾃⼩⽩的乐趣】）
1 maxNumber = int(input("请输⼊⼀个⼤于2的⾃然数"))
2 lst = list(range(2, maxNumber))
3print(lst)
4# 最⼤整数的平⽅根
5 m = int(maxNumber ** 0.5)
6for index, value in enumerate(lst):
7
8# 如果当前数字已⼤于最⼤整数的平⽅根，结束判断(素数判断⽅法：⽤⼀个数分别去除2到sqrt(这个数)，如果能被整除，则表明此数不是素数，反之是素数。）
9if value > m:
10break
11# 对该位置之后的元素进⾏过滤，每次除以value，若余数为0，则淘汰它
12    lst[index + 1:] = filter(lambda x: x % value != 0, lst[index + 1:])
13print("lst:",lst)
14print(lst)
原理：
前提须知：
素数判断⽅法：⽤⼀个数分别去除2到sqrt(这个数)，如果能被整除，则表明此数不是素数，反之是素数。
举例使⽤36来跑跑上⾯的代码
lst = [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35]
m = 6
进⼊循环
① index = 0 value = 2(对应lst中的第⼀个元素)
从lst[1]开始进⾏过滤出lst⾥不能被2整除的数
lst = [2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35]
python index函数② index =1 value = 3(对应lst中的第⼆个元素)
从lst[2]开始进⾏过滤出lst⾥不能被3整除的数
lst = [2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35]
③ index = 2 value = 5 (对应lst中的第三个元素)
从lst[3]开始进⾏过滤出lst⾥不能被5整除的数
lst = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]
④ index = 3 value = 7
此时已经⼤于6（36的平⽅根），所以结束判断
相⽐从2到所求数的平⽅根进⾏遍历，通过是否能被整除来求素数，这个的循环次数更少，譬如从上述②到③，就已经省去了对是否能整除4的判断，若我们所求的数越⼤，那这个体现的效率就越⾼（因为能减少更多的运算次数），为什么可以这样呢？如果⼀个数不能被2整除，那它肯定不能被4整除（即不能被n整除的数，肯定不能被n的倍数整除），因此就可⽤这规律减少运算次数

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。