Python 输出指定范围内的素数（一文讲透）

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

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

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

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

在编程与数学的交汇点上，素数（质数）始终是一个令人着迷的主题。素数是仅能被1和自身整除的自然数，它们如同数学世界的“建筑基石”，在密码学、算法设计等领域扮演着重要角色。对于编程学习者而言，如何用Python高效输出指定范围内的素数，不仅是一道经典的编程练习题，更是理解算法逻辑与优化思维的绝佳机会。本文将从基础概念出发，逐步拆解这一问题，通过代码实现与案例演示，帮助读者掌握从理论到实践的完整路径。

素数的基本概念

什么是素数？

素数是大于1的自然数中，除了1和它本身外，不能被其他自然数整除的数。例如：

• 2 是最小的素数，因为它只能被1和2整除；
• 3、5、7 等也是素数；
• 4 不是素数，因为它可以被2整除。

素数的特性与应用场景

素数的“唯一分解定理”表明，每个合数都可以分解为素数的乘积。这一特性使得素数在加密算法（如RSA）、随机数生成等领域至关重要。而在编程中，掌握素数的判定与生成方法，能为解决数学问题或算法竞赛提供基础支持。

判断素数的数学原理

基本试除法

判断一个数 n 是否为素数的最直观方法是：试除法。具体步骤如下：

1. 从2开始，逐个尝试是否能整除 n；
2. 若找到一个能整除的数，则 n 不是素数；
3. 若遍历到 n-1 仍未找到，则 n 是素数。

示例：判断 7 是否为素数

• 试除2→7/2=3.5（余0.5），不能整除；
• 试除3→7/3≈2.333，不能整除；
• 试除4→同理，直到 6；
• 因此 7 是素数。

优化：平方根的数学规律

试除法的效率问题显而易见——当 n 巨大时，遍历到 n-1 的时间成本极高。但数学规律能帮助我们大幅减少计算量：
定理：若 n 不是素数，则它必有一个小于或等于 √n 的因数。

证明：假设 n = a × b，且 a ≤ b，则 a ≤ √n。因此，只需遍历到 √n 即可判断 n 是否为素数。

优化后步骤：

1. 计算 √n 的整数部分（如 √100=10）；
2. 从2遍历到 √n，若无因数则为素数。

这一优化将时间复杂度从 O(n) 降至 O(√n)，效率提升显著。

Python 实现基础版

初级函数编写

基于试除法的基本逻辑，我们可以编写一个基础版的素数判断函数：

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

代码解析：

• n <=1：直接返回False（素数定义为大于1的数）；
• 循环范围：从2到 n-1，逐个试除；
• 返回条件：若存在因数返回False，否则返回True。

测试与局限性

测试 is_prime(7) 返回 True，而 is_prime(9) 返回 False（因3×3=9）。但此方法在处理大数时效率低下，例如判断 1000003（一个素数）时，需循环近百万次，耗时显著。

优化时间效率：平方根判断法

引入数学优化的代码实现

利用平方根原理，改进后的函数如下：

import math  

def is_prime_optimized(n):  
    if n <= 1:  
        return False  
    sqrt_n = int(math.sqrt(n)) + 1  # 确保包含√n的整数部分  
    for i in range(2, sqrt_n):  
        if n % i == 0:  
            return False  
    return True  

关键改进点：

• sqrt_n 的计算：通过 math.sqrt(n) 得到精确值，加1避免因浮点数截断丢失整数；
• 循环范围：从2到 sqrt_n，例如 n=100 时，循环仅到10次。

效率对比

假设 n=1000000：

• 原始方法：需循环 999,998 次；
• 优化后：循环仅 1000 次（√1e6=1000）。
  效率提升近 1000倍，这在处理大规模数据时至关重要。

进一步优化：跳过偶数检查

偶数的特殊性

除了2以外，所有偶数都不是素数。因此，可以：

1. 提前排除偶数（除2外）；
2. 仅检查奇数因数，进一步减少循环次数。

改进逻辑：

• 若 n 是偶数且 n≠2，直接返回False；
• 循环时从3开始，步长设为2（跳过偶数）。

代码实现

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

效率提升：

• 循环次数再次减半。例如，当 sqrt_n=1000 时，奇数循环仅需 500次。

输出指定范围内的素数

整合函数与生成素数列表

基于优化后的判断函数，编写一个生成指定范围内素数的函数：

def primes_in_range(start, end):  
    primes = []  
    for num in range(start, end + 1):  
        if is_prime_further_optimized(num):  
            primes.append(num)  
    return primes  

参数说明

• start：起始整数（例如2）；
• end：终止整数（例如100）；
• 返回值：包含素数的列表。

案例演示

输入：primes_in_range(10, 30)
输出：[11, 13, 17, 19, 23, 29]

优化算法与性能提升

更高级的筛法：埃拉托斯特尼筛法

对于连续范围内的素数生成，埃拉托斯特尼筛法（Sieve of Eratosthenes）效率更高。其核心思想是：

1. 初始化一个布尔数组标记数字是否为素数；
2. 从最小素数2开始，逐步筛去其倍数；
3. 剩余未被筛去的即为素数。

代码示例：

def sieve_of_eratosthenes(limit):  
    sieve = [True] * (limit + 1)  
    sieve[0:2] = [False, False]  # 0和1非素数  
    for num in range(2, int(math.sqrt(limit)) + 1):  
        if sieve[num]:  
            sieve[num*num : limit+1 : num] = [False]*len(range(num*num, limit+1, num))  
    primes = [num for num, is_prime in enumerate(sieve) if is_prime]  
    return primes  

适用场景：当需要生成连续且较大范围的素数时（如1e6以内），筛法时间复杂度为 O(n log log n)，远优于逐个判断。

实际案例与代码示例

案例1：输出1到100内的素数

print(primes_in_range(1, 100))  

案例2：用户输入范围动态输出

start = int(input("请输入起始值："))  
end = int(input("请输入终止值："))  
print(primes_in_range(start, end))  

案例3：大范围优化对比

import time  

start_time = time.time()  
primes = primes_in_range(1, 1000000)  # 使用进一步优化的函数  
print(f"耗时：{time.time() - start_time:.2f}秒")  

start_time = time.time()  
primes_sieve = sieve_of_eratosthenes(1000000)  
print(f"筛法耗时：{time.time() - start_time:.2f}秒")  

结果示例：

• 优化函数：约 0.5秒；
• 筛法：约 0.05秒（具体取决于硬件性能）。

结论

通过本文的逐步讲解，我们掌握了从素数定义到Python实现的完整路径。从基础的试除法到平方根优化、偶数排除，再到埃拉托斯特尼筛法，每一步都体现了算法优化的思维逻辑。对于编程初学者，建议从基础函数开始实践，逐步理解数学原理与代码逻辑的结合；中级开发者则可探索筛法等进阶算法，以应对大规模数据场景。

掌握“Python 输出指定范围内的素数”不仅是技术能力的提升，更是对编程思维的锤炼——从问题分解到效率优化，每一步都在培养解决问题的系统性与创造性。未来的学习中，可进一步研究素数分布规律、加密算法中的应用，或尝试将此方法扩展到其他数学问题中。

关键词布局统计：

• 核心关键词“Python 输出指定范围内的素数”自然出现在标题、前言、案例标题及结论中；
• 相关变体如“生成指定范围素数”“素数列表输出”贯穿代码示例与实际案例部分。