type
status
date
slug
summary
tags
category
icon
password
质数，也称为素数，是只能被1和自身整除的大于1的自然数。在数学领域，质数的研究一直是一个重要课题，它在密码学、编码理论等多个计算机科学分支中扮演着核心角色。为了高效地找出一定范围内的所有质数，研究者们发明了多种质数筛选算法。这些算法在提高计算效率、节约计算资源方面有着不可小觑的作用。
常用的质数筛算法
一、试除法
基本概念
试除法是最直观的质数判断方法，它通过逐一试除，检验目标数是否只能被1和自身整除。这种方法易于理解，但在大规模的质数筛选任务中效率较低。
算法解释
试除法的步骤相对简单：对于每一个待检验的数n，我们尝试用2到√n之间的所有自然数去除n。如果n不能被这些自然数整除，则n是质数；否则，n不是质数。
代码示例
二、埃拉托斯特尼筛法
基本概念
埃拉托斯特尼筛法，亦称埃氏筛，是一种经典的筛选质数方法。它的基本思想是从小到大依次标记倍数，未被标记的即为质数。
相比于试除法，埃氏筛的效率更高，尤其适用于筛选较大范围内的质数。
算法解释
埃氏筛的步骤可以分为以下几个阶段：
- 创建一个布尔数组，长度为筛选范围上限加一，初始时所有元素设为未标记状态（即表示为质数）。
- 从2开始，对每一个未被标记的数i，将其所有的倍数2i, 3i, 4i,...标记为已标记状态（即非质数）。
- 重复步骤2，直到筛选范围内所有数被检验完毕。
代码示例
三、欧拉筛法
基本概念
欧拉筛法，又称线性筛，是对埃氏筛的改进。其核心思想是每个合数只被其最小质因数筛选一次，从而达到线性时间复杂度，适合筛选极大范围内的质数。
算法解释
欧拉筛法的步骤如下：
- 初始化质数列表和布尔数组，布尔数组用于标记非质数。
- 遍历每个数i，如果i是质数，则将其添加到质数列表中。
- 对于每个质数p和当前数i，如果p*i超过筛选范围或者p大于i的最小质因数，则停止标记。
- 重复步骤2和3，直到筛选结束。
代码示例
总结
质数筛算法是数论和计算机科学中的基础工具，它们在不同的应用场景下有着重要的作用。
试除法直观易懂，但效率较低；
埃拉托斯特尼筛法效率较高，适合中等规模的筛选；
欧拉筛法则以其线性时间复杂度在大规模筛选中表现出色。
- 作者:VyronLee
- 链接:https://vyronlee.com/article/675d13ae-8a6e-404b-8f8a-0ad70fa34d58
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。