异常教程
Python – 获取 100 以内的质数（一文讲透）
💡一则或许对你有用的小广告
欢迎加入小哈的星球 ，你将获得：专属的项目实战 / 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+ 小伙伴加入学习 ，欢迎点击围观
前言
质数（Prime Number）是数学中一个基础但重要的概念，它指的是只能被 1 和 自身 整除的大于 1 的自然数。例如，2、3、5、7 等都是质数，而 4、6、8、9 等则不是。在编程领域，尤其是 Python 中，如何高效获取一定范围内的质数，是初学者和中级开发者常遇到的实践问题。本文将从基础概念出发，逐步讲解多种实现方法，并通过 代码示例 和 性能对比，帮助读者掌握“Python – 获取 100 以内的质数”的核心技巧。
一、质数的基本概念与判断逻辑
1.1 质数的数学定义
质数的定义可以用一句话概括：
一个大于 1 的自然数，如果除了 1 和它本身之外，没有其他因数，则称为质数。
例如，5 是质数，因为它只能被 1 和 5 整除；而 6 不是质数，因为它还能被 2 和 3 整除。
1.2 判断质数的核心逻辑
判断一个数是否为质数，可以通过以下步骤实现：
- 排除小于 2 的数：直接判定为非质数。
- 尝试除以 2 到该数的平方根之间的所有整数：如果存在能整除的数，则不是质数；否则是质数。
为什么只需要检查到平方根？
这里可以用一个比喻：
想象你有一块长方形的巧克力，面积是 N。如果一边的长度超过√N，另一边就必须小于√N。因此，若 N 有因数大于√N，必然存在一个对应的因数小于√N。因此，检查到√N 就足够了。
二、Python 实现质数判断的代码基础
2.1 简单暴力法（Brute Force）
最基础的实现方式是遍历所有可能的因数：
def is_prime(n):
if n < 2:
return False
for i in range(2, n):
if n % i == 0:
return False
return True
缺点分析：
- 当 n 较大时（如 100），循环次数过多。例如判断 100 是否为质数时，需要循环 98 次。
- 效率低，不适合处理更大的数据范围。
2.2 优化到平方根的循环
通过计算 平方根 作为循环的上限，可以大幅减少循环次数：
import math
def is_prime_optimized(n):
if n < 2:
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 = 100 为例，原暴力法需要循环 98 次，而优化后仅需循环 10 次（
sqrt(100) = 10）。
三、生成 100 以内质数的多种方法
3.1 方法一：遍历 + 单个判断函数
通过循环 2 到 100 的所有数，并调用上述优化后的 is_prime_optimized 函数：
primes = []
for num in range(2, 101):
if is_prime_optimized(num):
primes.append(num)
print(primes)
输出结果：
[2, 3, 5, 7, 11, ..., 89, 97]
3.2 方法二：列表推导式（List Comprehension）
用更简洁的 Python 语法实现相同逻辑：
primes = [num for num in range(2, 101) if is_prime_optimized(num)]
print(primes)
四、进阶优化：埃拉托斯特尼筛法（Sieve of Eratosthenes）
4.1 筛法的数学原理
筛法 是一种古老的质数筛选算法，其核心思想是：
- 初始化一个布尔型数组
is_prime，初始值全设为True。 - 从 2 开始，将当前数的所有倍数标记为
False。 - 重复步骤 2，直到处理到平方根位置。
形象比喻：
想象你有一张写满数字的网格纸，每次划掉当前质数的所有倍数，剩下的未被划掉的数字就是质数。
4.2 Python 实现代码
def sieve_of_eratosthenes(limit):
is_prime = [True] * (limit + 1)
is_prime[0], is_prime[1] = False, False # 0和1不是质数
for num in range(2, int(limit**0.5) + 1):
if is_prime[num]:
# 标记num的倍数为非质数
for multiple in range(num*num, limit+1, num):
is_prime[multiple] = False
primes = [num for num, prime in enumerate(is_prime) if prime]
return primes
print(sieve_of_eratosthenes(100))
性能对比：
| 方法 | 时间复杂度 | 适用场景 |
|--------------------|------------|------------------------|
| 暴力法 | O(n²) | 小规模数据（如 n ≤ 100）|
| 平方根优化法 | O(n√n) | 中等规模数据 |
| 埃拉托斯特尼筛法 | O(n log log n) | 大规模数据（如 n = 1e6） |
五、代码封装与函数复用
5.1 封装质数生成函数
将上述方法封装为一个可复用的函数，支持动态调整范围：
def get_primes_up_to(limit=100, method='sieve'):
if method == 'sieve':
return sieve_of_eratosthenes(limit)
else:
primes = []
for num in range(2, limit+1):
if is_prime_optimized(num):
primes.append(num)
return primes
print(get_primes_up_to(100, method='sieve'))
5.2 单元测试验证
编写简单测试用例，确保函数正确性：
def test_primes():
assert get_primes_up_to(10) == [2, 3, 5, 7]
assert get_primes_up_to(2) == [2]
assert get_primes_up_to(1) == []
print("所有测试通过！")
test_primes()
六、常见问题与扩展思考
6.1 为什么从 2 开始遍历？
因为 1 不是质数，且所有自然数都可以被 1 整除，因此遍历从 2 开始。
6.2 如何处理更大的范围（如 1000 或 10000）？
- 筛法 是更优的选择，其时间复杂度远低于逐个判断的方法。
- 可以进一步优化筛法的内存使用，例如使用位操作或布尔数组的压缩形式。
6.3 是否有其他数学库或工具可用？
Python 的 sympy 库提供了现成的质数函数：
from sympy import primerange
print(list(primerange(1, 100)))
结论
通过本文的讲解，读者可以掌握以下关键内容：
- 质数的数学定义与判断逻辑。
- 从暴力法到筛法的算法优化路径。
- Python 中的代码实现与性能对比。
“Python – 获取 100 以内的质数” 不仅是一个基础编程问题，更是理解算法优化与数学思维结合的典型案例。无论是编程初学者通过基础循环理解逻辑，还是中级开发者通过筛法提升效率，本文提供的方法与思路都具有实际参考价值。
希望读者能够将这些知识应用到更复杂的场景中，例如密码学、数据加密或数学建模等领域，进一步探索 Python 在算法实现中的强大能力。