异常教程

Python 判断一个数是否是质数（千字长文）

更新时间:

💡一则或许对你有用的小广告

欢迎加入小哈的星球 ，你将获得：专属的项目实战 / 1v1 提问 / Java 学习路线 / 学习打卡 / 每月赠书 / 社群讨论

截止目前， 星球 内专栏累计输出 90w+ 字，讲解图 3441+ 张，还在持续爆肝中.. 后续还会上新更多项目，目标是将 Java 领域典型的项目都整一波，如秒杀系统, 在线商城, IM 即时通讯，权限管理，Spring Cloud Alibaba 微服务等等，已有 3100+ 小伙伴加入学习 ，欢迎点击围观

质数的定义与基本概念

在数学领域，质数（Prime Number）是指大于1的自然数中，除了1和它本身外，不能被其他自然数整除的数。例如，2、3、5、7都是质数，而4、6、8、9则不是，因为它们可以被除了1和自身之外的其他数整除。质数在密码学、算法设计等领域具有重要应用，因此理解如何判断一个数是否为质数，对编程学习者而言是一项基础且实用的技能。

在Python编程中，判断质数的核心逻辑是遍历可能的因数，并检查是否存在其他因数。接下来我们将从基础到进阶，逐步探讨不同的实现方法，并分析其优缺点。

基础判断方法：遍历所有可能的因数

最直观的质数判断方法是遍历从2到目标数（n）的前一个数（n-1），检查是否存在能整除n的因数。如果找到任何一个因数，则说明该数不是质数；否则，它是质数。

代码示例

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

代码解析

  1. 输入验证：首先判断n是否小于等于1，因为质数定义中明确要求大于1。
  2. 循环范围：从2开始遍历到n-1，逐个检查是否能整除n。
  3. 提前终止：一旦发现因数，立即返回False，无需继续遍历。

缺点与优化方向

虽然这种方法逻辑简单，但存在明显的效率问题。例如，当n是10000时，需要循环9998次，这在处理大数时会导致性能瓶颈。因此，我们需要寻找更高效的优化方法。

优化方法一：遍历到平方根（√n）

数学上有一个重要性质：如果n有一个大于√n的因数，那么它必然有一个小于√n的因数。因此，只需遍历到√n即可。例如，判断100是否是质数时，只需检查到10（√100=10），因为如果存在因数11，那么对应的因数100/11≈9.09，显然小于10。

代码示例

import math  

def is_prime_optimized(n):  
    if n <= 1:  
        return False  
    sqrt_n = int(math.sqrt(n)) + 1  # 取整并加1避免漏掉整数  
    for i in range(2, sqrt_n):  
        if n % i == 0:  
            return False  
    return True

关键改进

  • 循环范围：通过math.sqrt(n)计算平方根，并转换为整数类型。例如，当n=15时，√15≈3.87，取整后为3，但需要加1以确保覆盖到4的因数（如n=16时，√16=4，加1后为5，但实际循环到4即可）。
  • 效率提升：当n=10000时，循环次数从9998次减少到100次，性能提升显著。

优化方法二：排除偶数与6的倍数规律

进一步观察质数的分布规律可以发现：

  1. 所有偶数（除2外）都不是质数，因此可以跳过偶数的遍历。
  2. 质数的分布遵循“6k±1”规律：除了2和3，所有质数都可以表示为6k±1的形式，其中k是自然数。例如，5=6×1-1，7=6×1+1，11=6×2-1，等等。

基于此，我们可以进一步优化循环条件：

  1. 首先排除偶数和3的倍数。
  2. 仅检查形如6k±1的候选因数。

代码示例

def is_prime_further_optimized(n):  
    if n <= 1:  
        return False  
    elif n <= 3:  
        return True  # 2和3是质数  
    elif n % 2 == 0 or n % 3 == 0:  
        return False  
    i = 5  
    while i * i <= n:  
        if n % i == 0 or n % (i + 2) == 0:  
            return False  
        i += 6  
    return True

代码逻辑解析

  1. 快速排除：直接处理n≤3的情况，以及能被2或3整除的数。
  2. 循环步长：从5开始，每次增加6（即i=5、11、17…），并同时检查i和i+2（如5和7、11和13等），覆盖所有可能的质因数。
  3. 时间复杂度：循环次数进一步减少，例如当n=10000时，仅需循环约16次。

高级方法：使用Python标准库与第三方库

对于更复杂的场景，可以借助Python的数学库或第三方库来简化代码。

方法一：利用math.isqrt()（Python 3.8+）

Python 3.8引入的math.isqrt()函数可以直接计算平方根的整数部分，避免浮点数精度问题。

import math  

def is_prime_math(n):  
    if n <= 1:  
        return False  
    for i in range(2, math.isqrt(n) + 1):  
        if n % i == 0:  
            return False  
    return True

方法二：调用sympy库的isprime()函数

sympy是一个数学符号计算库，提供了高效的质数判断函数：

from sympy import isprime  

print(isprime(7))    # 输出：True  
print(isprime(15))   # 输出：False

注意：sympy需通过pip install sympy安装，适用于需要高性能或复杂数学运算的场景。

实际案例与应用场景

案例1：生成指定范围内的质数列表

def generate_primes(limit):  
    primes = []  
    for num in range(2, limit + 1):  
        if is_prime_further_optimized(num):  
            primes.append(num)  
    return primes  

print(generate_primes(30))

案例2：密码学中的质数应用

在RSA加密算法中，需要生成两个大质数来生成公钥和私钥。此时，高效的质数判断算法是关键：

import random  
from sympy import isprime  

def generate_large_prime(bits=1024):  
    while True:  
        num = random.getrandbits(bits) | (1 << (bits - 1)) | 1  # 确保最高位和最低位为1  
        if isprime(num):  
            return num  

print(generate_large_prime(16))  # 生成一个16位的随机质数

性能对比与选择建议

以下表格对比了不同方法的性能表现（以n=10000为例）：

方法名称循环次数适用场景
基础遍历法9998小数值或教学演示
平方根优化法100中等规模数值
6k±1优化法16高效需求的常规场景
sympy.isprime()内部实现需要极致性能的场景

选择建议

  • 学习阶段：优先使用基础方法或平方根优化法，便于理解核心逻辑。
  • 实际项目：推荐使用6k±1优化法或第三方库，平衡代码简洁性与性能。
  • 大规模计算：结合sympy库或并行计算技术，例如多线程处理。

总结与扩展思考

通过本文，我们系统地学习了Python中判断质数的多种方法，并通过代码示例和性能对比，明确了不同场景下的最佳实践。质数判断不仅是编程的基础技能，更是理解算法优化与数学逻辑的窗口。

对于希望进一步深入学习的读者，可以尝试以下方向：

  1. 埃拉托斯特尼筛法（Sieve of Eratosthenes）：高效生成质数列表的方法。
  2. 米勒-拉宾素性测试（Miller-Rabin）：概率性算法，适合超大质数的快速判断。
  3. 分布式计算：利用多核CPU或集群资源处理超大规模质数问题。

掌握质数判断的底层逻辑后，你将更从容地应对编程挑战，并为后续学习加密算法、数据结构等进阶内容打下坚实基础。

最新发布

查看更多文章