3.1 埃拉托色尼筛选
筛选 3.1
2023-09-14 09:06:55 时间
埃拉托色尼筛选Sieve of Eratosthenes是最简单的一种质数筛选算法。这种算法我们小学就学过,就是数字写入格子里。然后从2开始,以2为第一个质数,划掉2后面所有2的倍数。划掉2的倍数后,再看下一个没被划掉的数字,作为质数,继续划掉它的倍数。
用表格做个演示:
步骤 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
初始化 | / | / | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
2的倍数 | / | / | 1 | 1 | / | 1 | / | 1 | / | 1 | / | 1 | / | 1 | / | 1 | / | 1 | / | 1 | / |
3的倍数 | / | / | 1 | 1 | / | 1 | / | 1 | / | / | / | 1 | / | 1 | / | / | / | 1 | / | 1 | / |
5的倍数 | / | / | 1 | 1 | / | 1 | / | 1 | / | / | / | 1 | / | 1 | / | / | / | 1 | / | 1 | / |
7的倍数 | / | / | 1 | 1 | / | 1 | / | 1 | / | / | / | 1 | / | 1 | / | / | / | 1 | / | 1 | / |
代码比较简单: |
# _*_ coding:utf-8 _*_
def eratoshenes(n):
array = [True] * (n + 1)
array[2] = True
result = []
for i in range(2, n):
if array[i]:
result.append(i)
for j in range(i << 1, n + 1, i):
array[j] = False
return result
if __name__ == '__main__':
print(eratoshenes(20))
相关文章
- 批量筛选QQ靓号教程
- AISecOps:量化评估告警筛选方案的性能
- Excel高级筛选完全指南
- Pandas | 数据筛选
- 机器学习中的特征选择(变量筛选)方法简介
- MCE虚拟筛选化合物库 | MedChemExpress
- 浙大团队基于ML的抗菌肽筛选模型,可识别整个肽库空间发现新药
- IDoc接口运维-添加筛选条件详解编程语言
- MySQL中使用when条件实现数据筛选(mysql中使用when)
- 数据排序mysql中升序和降序筛选(mysql中升序和降序)
- 怎么用的使用Oracle中条件语句实现条件筛选(oracle中条件语句是)
- 字段Oracle数据库筛选非空值字段的技巧(oracle中筛选不为空)
- Oracle横线筛选精确得出你想要的结果(oracle下横杠筛选)