质数（素数）是大于1且只能被1和自身整除的自然数。例如：2, 3, 5, 7… 🧮
在编程中，质数检测是基础算法之一，常用于加密、数学计算等领域。

判断质数的常见方法

1. 试除法

从2开始依次尝试除到√n，若存在能整除的数则不是质数。
示例代码（Python）： 

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

👉 了解更多时间复杂度分析

2. 埃拉托斯特尼筛法

通过筛选出所有非质数来高效生成质数列表。
核心思想：创建一个布尔数组，标记非质数。

质数_示意图

3. 米勒-拉宾素性检验

一种概率算法，适用于大数的快速质数检测。
特点：效率高但有一定误判率，需结合其他方法验证。
扩展学习：质数生成进阶方法

质数的应用场景

  • 密码学：RSA算法依赖大质数的分解难题 🔐
  • 算法优化：减少不必要的计算步骤 🚀
  • 数学研究：质数分布规律探索 📊
埃拉托斯特尼筛法_示意图

小贴士

  • 质数检测的效率与算法选择密切相关 📈
  • 可结合质数表加速验证
  • 注意处理边界条件（如n=1的情况）⚠️

如需进一步学习质数相关的算法实现，可参考本站其他教程。