异常教程

Python 质数判断（建议收藏）

更新时间:

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

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

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

前言

在编程领域，质数判断是一个基础却重要的问题。无论是算法学习、密码学应用，还是数学建模，质数都扮演着关键角色。对于编程初学者而言，掌握质数判断的逻辑和实现方法，不仅能提升对循环、条件判断等基础语法的理解，还能培养算法优化的思维能力。而中级开发者则可以通过深入探索质数判断的高效算法，进一步掌握算法复杂度分析和优化技巧。本文将以 Python 质数判断 为核心，从基础到进阶，结合代码示例和实际案例，帮助读者系统掌握这一技能。

什么是质数？

质数（Prime Number）是指在大于1的自然数中，除了1和它本身外，不能被其他自然数整除的数。例如，2、3、5、7 是质数，而 4、6、8、9 则不是质数。

我们可以用一个形象的比喻来理解质数：

质数就像独居的孤岛，它无法被其他数字“分割”或“合并”，只能独自存在。而合数则像由多个小岛拼接而成的大陆，可以被其他数字整除。

质数的判断逻辑看似简单，但实现高效的算法却需要一定的技巧。接下来，我们将从最基础的试除法开始，逐步探索优化方法。

基础算法：试除法（Trial Division）

实现思路

试除法是最直观的质数判断方法：

  1. 输入一个大于1的整数n。
  2. 从2开始遍历到n-1，检查是否存在能整除n的数。
  3. 若存在，则n是合数；若不存在，则n是质数。

代码示例

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

缺陷与改进

试除法的缺陷在于效率低下。例如，判断一个1000以内的数时，最坏情况下需要执行998次循环。对于更大的数字，这种算法显然不可行。

优化1：平方根优化（Square Root Optimization）

数学原理

根据数学定理，若一个数n存在大于1的因数，则它至少有一个因数小于或等于√n。因此，我们只需遍历到√n即可。

形象比喻

想象一个长方形的面积为n，若长和宽均大于√n，则它们的乘积必然超过n。因此，至少有一个因数小于或等于√n。

代码实现

import math  

def is_prime(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

效率对比

数值范围原始试除法循环次数平方根优化后循环次数
1009810
100099831
100009998100

优化2：奇数筛选法

观察规律

除了2以外，所有偶数都不是质数。因此，我们可以直接跳过偶数的判断，进一步减少循环次数。

代码改进

def is_prime(n):  
    if n <= 1:  
        return False  
    if n == 2:  
        return True  
    if n % 2 == 0:  
        return False  
    sqrt_n = int(math.sqrt(n)) + 1  
    for i in range(3, sqrt_n, 2):  # 步长设为2，只检查奇数  
        if n % i == 0:  
            return False  
    return True

效率提升

通过奇数筛选法，循环次数再次减少约50%。例如，判断n=997时，原始平方根优化需要循环31次，而奇数筛选法仅需15次。

进阶算法：埃拉托斯特尼筛法（Sieve of Eratosthenes）

适用场景

当需要批量判断一定范围内的所有质数时，筛法的效率远高于逐个判断的方法。

实现原理

  1. 创建一个布尔数组is_prime[0...n]，初始值设为True。
  2. 将0和1标记为False。
  3. 从2开始，将当前数的倍数全部标记为False。
  4. 重复步骤3，直到处理完所有小于√n的数。

代码示例

def sieve_of_eratosthenes(n):  
    is_prime = [True] * (n + 1)  
    is_prime[0] = is_prime[1] = False  
    for i in range(2, int(n**0.5) + 1):  
        if is_prime[i]:  
            for j in range(i*i, n+1, i):  
                is_prime[j] = False  
    return is_prime

实际应用

假设需要找出100以内的所有质数，调用sieve_of_eratosthenes(100) 后，返回的数组中True的位置即为质数。

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

RSA加密算法

在RSA加密中，需要生成两个大质数p和q，其乘积n=p*q作为公钥的一部分。此时，高效的质数判断算法至关重要。例如，判断一个200位数是否为质数，若用试除法需数百万年，而用米勒-拉宾素性检验（Miller-Rabin）则能在秒级完成。

米勒-拉宾算法简介

该算法通过概率方法判断质数，虽然存在极小误差，但通过多次测试可将错误率降低到忽略不计的水平。

import random  

def is_prime_miller_rabin(n, k=5):  # k为测试轮数  
    if n <= 1:  
        return False  
    # 处理2和奇数情况  
    if n == 2 or n % 2 == 0:  
        return n == 2  
    d = n - 1  
    s = 0  
    while d % 2 == 0:  
        d //= 2  
        s += 1  
    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(s-1):  
            x = pow(x, 2, n)  
            if x == n-1:  
                break  
        else:  
            return False  
    return True

常见问题与解答

Q1：如何处理输入为负数或0的情况？

A1：在函数开始时直接返回False，并添加类型检查。

if not isinstance(n, int) or n < 2:  
    return False

Q2：为什么筛法适合批量判断？

A2：筛法的时间复杂度为O(n log log n)，远低于逐个试除的O(n√n)。

Q3：如何选择适合的算法？

A3：

  • 单个数判断：优化后的试除法或米勒-拉宾算法。
  • 批量判断：埃拉托斯特尼筛法或其改进版本。

结论

通过本文的学习，我们掌握了从基础到进阶的 Python 质数判断 方法。从试除法到筛法，从确定性算法到概率算法，每个步骤都体现了算法优化的核心思想：减少不必要的计算。对于编程初学者，建议从试除法开始实践，逐步理解循环和条件判断的逻辑；中级开发者则可以深入研究筛法和米勒-拉宾算法，探索算法复杂度的优化策略。

质数判断不仅是数学与编程的交汇点，更是算法思维的训练场。希望读者能通过本文，不仅掌握具体代码的实现，更能培养举一反三、不断优化的编程习惯。

最新发布

查看更多文章