使⽤列表实现筛选法求素数(利⽤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的倍数整除),因此就可⽤这规律减少运算次数