知识卡片
素数筛逐层排除倍数
筛法从最小素数开始,排除其倍数,再用下一个尚未排除的数继续筛。没有被更小素数筛除的数,才成为下一轮的候选素数。
同一思想可以用数组标记、递归过滤或任务流水线表达。比较实现时应统一目标与停止条件;原文C例只输出限定数量,Go例输出前十个素数,不能据这些不同程序直接比较性能或一般规模的正确性。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
算法描述:先用最小的素数2去筛,把2的倍数筛除;下一个未筛除的数就是素数(这里是3)。再用这个素数3去筛,筛除3的倍数……这样不断重复下去,直到筛完为止(算法图示见图4-1)。 图4-1 素数筛算法图示 下面是该素数筛算
参考来源
- 位置:《Go语言精进之路 _ 从新手到高手的编程思想,方法和技巧 = Go programming from beginners》第04章《4.2 现实中的“投影”》(来源项目book-sources:extracted/Go语言精进之路 _ 从新手到高手的编程思想,方法和技巧 = Go programming from beginners/_epub-src/Text/Chapter4_0002.xhtml;spine 22,归一字符[182,292))
- 结论依据:原文解释埃拉托斯特尼筛法并提供三语言实现,本卡保留排除机制和比较前提。
- 原始内容:算法描述:先用最小的素数2去筛,把2的倍数筛除;下一个未筛除的数就是素数(这里是3)。再用这个素数3去筛,筛除3的倍数……这样不断重复下去,直到筛完为止(算法图示见图4-1)。 图4-1 素数筛算法图示 下面是该素数筛算