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

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

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

• 新项目:《从零手撸：仿小红书（微服务架构）》 正在持续爆肝中，基于 Spring Cloud Alibaba + Spring Boot 3.x + JDK 17...，点击查看项目介绍 ;
• 《从零手撸：前后端分离博客项目（全栈开发）》 2 期已完结，演示链接： http://116.62.199.48/ ;

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

前言：质数判断的现实意义

在密码学、数据加密、算法竞赛等领域，质数判断是一个基础但重要的问题。例如，RSA加密算法的安全性就依赖于大质数的分解难度。对于编程初学者而言，掌握这一技能不仅能提升逻辑思维能力，还能为后续学习更复杂的算法打下基础。接下来，我们将从最基础的试除法开始，逐步探索如何用Python高效实现这一功能。

试除法：质数判断的入门方法

基本思路

试除法的核心思想是：用小于该数的所有自然数去试除目标数，若均无法整除，则说明该数是质数。这如同用一把“筛子”过滤掉所有能被其他数整除的数字，剩下的就是质数。

代码示例（基础版）

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

代码解析：

1. 若输入的数小于等于1，直接返回False（因质数定义需大于1）。
2. 从2开始遍历到n-1，检查是否存在能整除n的数。
3. 若找到任意一个能整除的数，立即返回False；否则返回True。

缺点：当n很大时（例如百万级），此方法效率极低，时间复杂度为O(n)。

优化方法一：平方根优化

数学原理

通过数学推导可知，若一个数n存在除1和它本身以外的因数，那么至少有一个因数小于或等于√n。因此，我们只需遍历到√n即可。

代码示例（平方根优化版）

import math  

def is_prime_sqrt(n):  
    if n <= 1:  
        return False  
    sqrt_n = int(math.sqrt(n)) + 1  
    for i in range(2, sqrt_n):  
        if n % i == 0:  
            return False  
    return True  

改进点：

• 将循环上限从n-1缩减到√n，时间复杂度降至O(√n)，例如当n=100时，循环次数从98次减少到10次。

注意：需注意math.sqrt()返回的是浮点数，因此需转换为整数并加1以确保覆盖所有可能因数。

优化方法二：6k±1法则

数学规律

所有质数（除了2和3）都可以表示为6k ± 1的形式。因此，我们可以跳过大部分非必要检查：

1. 若n能被2或3整除，直接返回False。
2. 否则，仅检查形如6k±1的数。

代码示例（6k±1优化版）

def is_prime_6k(n):  
    if n <= 1:  
        return False  
    if n <= 3:  
        return True  
    if n % 2 == 0 or n % 3 == 0:  
        return False  
    i = 5  
    w = 2  
    while i * i <= n:  
        if n % i == 0:  
            return False  
        i += w  
        w = 6 - w  # 在5→7→11→13之间循环  
    return True  

运行逻辑：

• 初始检查排除2和3的倍数。
• 通过变量w控制步长，在5→7→11→13…的序列中循环，跳过偶数和3的倍数。
• 时间复杂度进一步降低至O(√n/3)，效率提升约30%。

进阶方法：米勒-拉宾素性检验（可选）

对于超大质数（例如加密级数），试除法效率不足。此时可使用概率性算法——米勒-拉宾素性检验。其核心思想是：

通过随机选取底数a，利用模幂运算快速判断n是否为合数。若多次测试均未发现矛盾，则认为n为质数的概率极高。

代码示例（简化版）

import random  

def miller_rabin(n, k=5):  # k为测试轮数  
    if n <= 1:  
        return False  
    elif n <= 3:  
        return True  
    elif n % 2 == 0:  
        return False  
    # 将n-1分解为d*2^r  
    d = n - 1  
    r = 0  
    while d % 2 == 0:  
        d //= 2  
        r += 1  
    # 进行k次测试  
    for _ in range(k):  
        a = random.randint(2, n - 2)  
        x = pow(a, d, n)  
        if x == 1 or x == n - 1:  
            continue  
        for __ in range(r - 1):  
            x = pow(x, 2, n)  
            if x == n - 1:  
                break  
        else:  
            return False  
    return True  

适用场景：当n超过10^18时，此方法效率远高于试除法。但需注意，其结果为概率性判断（可通过调整k值提升准确性）。

性能对比与选择建议

选择建议：

• 对于编程练习或小规模数据，推荐使用6k±1优化版。
• 处理超大质数时，优先使用米勒-拉宾检验，并结合确定性测试（如预置底数列表）。

实际案例：质数判断的应用场景

案例1：生成质数列表

def generate_primes(n):  
    primes = []  
    for num in range(2, n+1):  
        if is_prime_6k(num):  # 使用优化后的函数  
            primes.append(num)  
    return primes  

print(generate_primes(30))  # 输出 [2, 3, 5, 7, ..., 29]  

案例2：密码学中的质数验证

在生成RSA密钥时，需验证两个大质数：

p = 1234567891  # 假设的候选质数  
if miller_rabin(p, k=20):  
    print(f"{p} 是质数，可用作密钥")  
else:  
    print("需重新选择质数")  

结论

通过本文的讲解，读者应能掌握从基础到进阶的质数判断方法，并理解不同算法的适用场景。编程的本质是解决问题，而优化算法则是提升效率的关键。建议读者在实际项目中根据需求选择合适的方法，并通过测试不同输入值来验证代码的正确性。

最后，希望本文能帮助读者在编程之路上迈出扎实的一步——毕竟，每个复杂的算法，都始于对基础问题的深刻理解。