知识卡片

普通读书笔记卡 · 1971.w.1.k.1.a.1 · 生成模型:未记录

筛法按小因子排除合数

理解等级:中级

先考虑2到上界的整数,依次找到未被排除的数并标记它的倍数,剩下的就是素数。若一个数是合数,它至少有一个不大于自身平方根的因子,所以不必对每个大数都重新排倍数。书中用数组索引表示整数并从2的倍数开始;平方根取数组长度是略保守边界,性能收益仍要按负载判断,未在本机运行。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 2 处

    参考来源

    - 位置:《代码整洁之道》全书 · 第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