知识卡片
筛法按小因子排除合数
先考虑2到上界的整数,依次找到未被排除的数并标记它的倍数,剩下的就是素数。若一个数是合数,它至少有一个不大于自身平方根的因子,所以不必对每个大数都重新排倍数。书中用数组索引表示整数并从2的倍数开始;平方根取数组长度是略保守边界,性能收益仍要按负载判断,未在本机运行。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 第4章 注释
原书出处 · 2 处
- 第4章 注释 4.4.16 不明显的联系 · 查看原书依据
The algorithm used is the Sieve of Eratosthenes
- 第4章 注释 4.4.19 范例(续) · 查看原书依据
Every multiple in the array has a prime factor
参考来源
- 位置:《代码整洁之道》全书 · 第4章 注释,spine013单元010;来源项目book-sources,extracted/代码整洁之道/_epub-src/OEBPS/Text/part0011.xhtml。
- 结论依据:原文旧/新两份代码及下一单元平方根理由共同支持筛除机制和因子界,中文因子说明为对该理由的展开,不冒充性能实测。未在本机运行示例或改变环境。
- 原始内容:pecified * maximum. The algorithm used is the Sieve of Eratosthenes. * <p> * Eratosthenes of Cyrene, b. c. 276 BC, Cyrene, Libya -- * d. c. 194, Alexand