前言：为什么质数如此重要
在学习编程的过程中，我们经常会遇到一些经典的算法问题，其中一个非常基础但又极具代表性的问题就是 “求出 1 到 100 的质数”。质数（Prime Number），也叫素数，是指大于 1 的自然数，除了 1 和它本身之外，无法被其他自然数整除的数。比如 2、3、5、7、11 都是质数，而 4、6、8、9 则不是。
掌握如何在 Python 中求出质数，不仅能帮助我们理解循环、判断等基本语法，还能提升算法设计能力。本文将围绕 Python 求出 1 到 100 的质数 这个主题，从基础概念讲起，逐步深入，并给出完整的代码示例与详细注释，适合编程初学者和有一定经验的中级开发者阅读。
质数的定义与判断逻辑
什么是质数
质数是数学中的一个基础概念，简单来说，如果一个大于 1 的自然数，不能被除了 1 和它本身以外的任何自然数整除，那么它就是质数。例如，数字 2 只能被 1 和 2 整除，所以它是质数。而数字 4 可以被 2 整除，所以它不是质数。
质数的判断方法
要判断一个数是否是质数，我们可以采用以下逻辑：
- 如果这个数小于 2，那么它不是质数；
- 如果这个数是 2，那么它是质数；
- 如果这个数是偶数（能被 2 整除），那么它也不是质数；
- 对于奇数，我们需要尝试从 3 开始，直到该数的平方根，看看是否能被其中任何一个数整除；
- 如果都不能整除，则为质数；否则，不是质数。
这种逻辑可以帮助我们高效地判断一个数是否是质数，而不会陷入不必要的循环中。
编写第一个版本：暴力解法
我们可以使用一个简单的循环结构来遍历 1 到 100 的所有数字，并对每个数字进行判断。下面是使用 Python 编写的第一个版本代码：
def is_prime(n):
if n <= 1:
return False # 小于等于1的数不是质数
if n == 2:
return True # 2是最小的质数
if n % 2 == 0:
return False # 偶数不是质数
for i in range(3, n): # 从3到n-1进行遍历
if n % i == 0:
return False # 如果能被其他数整除，就不是质数
return True # 都不能整除，就是质数
for num in range(1, 101):
if is_prime(num):
print(num)
这段代码的逻辑非常直观，适合初学者理解。但是它有一个明显的缺点：效率较低。因为对于每个数，我们都要从 3 遍历到 n-1，这在处理较大的数据范围时会浪费大量时间。
优化版本：降低判断范围
如前所述，我们其实不需要遍历到 n-1，只需要遍历到 n 的平方根即可。这是基于一个数学原理：如果一个数 n 不是质数，那么它一定有一个因数小于或等于它的平方根。通过这个优化，我们可以大幅减少判断次数，提高程序的运行效率。
下面是优化后的代码示例：
import math # 引入math模块，用于计算平方根
def is_prime(n):
if n <= 1:
return False
if n == 2:
return True
if n % 2 == 0:
return False
max_divisor = math.isqrt(n) + 1 # 计算n的平方根并加1
for i in range(3, max_divisor, 2): # 只遍历奇数
if n % i == 0:
return False
return True
for num in range(1, 101):
if is_prime(num):
print(num)
在这段代码中，math.isqrt(n) 是 Python 3.8 及以上版本中提供的一个函数，用来计算 n 的平方根并返回整数部分。相比使用 int(math.sqrt(n))，math.isqrt 更加高效且不会引入浮点数误差。
为什么只遍历奇数
如果一个数不是 2 的倍数，那它一定是奇数。我们只需要检查奇数是否能整除 n，而无需考虑偶数。因为如果 n 是偶数，它已经被我们排除在外了。这样可以进一步减少循环次数，提升效率。
高级技巧：使用列表推导式简化代码
Python 的一大优势是其简洁的语法，尤其是在使用列表推导式时。我们可以通过一个简洁的列表推导式，快速获取 1 到 100 之间的所有质数。
import math
def is_prime(n):
if n <= 1:
return False
if n == 2:
return True
if n % 2 == 0:
return False
for i in range(3, math.isqrt(n) + 1, 2):
if n % i == 0:
return False
return True
primes = [num for num in range(1, 101) if is_prime(num)]
print("1到100的质数有：", primes)
代码解析
math.isqrt(n) + 1：计算 n 的平方根并加 1，作为循环的上限；range(3, math.isqrt(n) + 1, 2)：从 3 开始，只遍历奇数；- 列表推导式
[num for num in ... if ...]：快速构造一个包含所有符合条件的质数的列表； print("1到100的质数有：", primes)：输出所有质数。
进阶方法：埃拉托斯特尼筛法（Sieve of Eratosthenes）
除了逐个判断的方式，我们还可以使用一种高效的算法——埃拉托斯特尼筛法，来找出 1 到 100 的所有质数。这种方法特别适合找出一定范围内的所有质数，它的核心思想是：
- 建立一个标记列表，初始时所有数都标记为“是质数”；
- 从最小的质数 2 开始，将它的所有倍数标记为“不是质数”；
- 接下来找下一个未被标记的数，重复上述过程；
- 直到遍历完所有数字。
下面是 Python 实现的埃氏筛法代码：
def sieve_of_eratosthenes(n):
is_prime = [True] * (n + 1) # 初始化一个标记数组，索引0到n
is_prime[0] = is_prime[1] = False # 0和1不是质数
for i in range(2, int(n ** 0.5) + 1): # 从2到sqrt(n)
if is_prime[i]:
for multiple in range(i*i, n+1, i): # 标记所有i的倍数
is_prime[multiple] = False
return [x for x in range(2, n+1) if is_prime[x]] # 返回所有标记为True的数
primes = sieve_of_eratosthenes(100)
print("1到100的质数有：", primes)
代码亮点
- 使用布尔数组来记录哪些数是质数；
- 从 2 开始，逐步筛去非质数；
- 最终通过列表推导式提取所有质数；
- 时间复杂度为 O(n log log n)，在大数据量下表现优于逐个判断。
实际案例：质数在现实中的应用
加密算法中的质数
质数在现代密码学中有着广泛的应用，例如 RSA 加密算法就是基于两个大质数的乘积。通过这种方式，可以生成一对公钥和私钥，用于安全的数据传输。质数的不可预测性和难以分解的特性，使其成为加密技术中的核心工具。
编程中的性能优化
质数问题不仅是数学上的挑战，也是编程中常见的性能优化案例。通过学习质数的判断与筛法，我们可以掌握如何通过算法优化提升代码执行效率。这对于处理大量数据或设计高性能程序非常有帮助。
程序调试与逻辑训练
编写质数判断程序，也是锻炼编程逻辑的好机会。我们需要处理边界条件、循环嵌套、判断条件等多个方面，这对于初学者理解程序结构、调试逻辑非常有帮助。
总结：掌握质数判断，提升编程能力
通过本文的讲解，我们不仅学会了如何 使用 Python 求出 1 到 100 的质数，还了解了不同方法的优缺点，以及质数在实际生活中的应用场景。对于初学者而言，可以从最基础的逐个判断开始，逐步过渡到更高效的筛法。而对中级开发者来说，这是一个锻炼算法优化思维的绝佳机会。
质数问题虽然简单，但它背后蕴含的数学与编程思想却非常深刻。通过不断实践与优化，我们可以写出更高效、更优雅的 Python 代码。希望本文对你有所帮助，也欢迎在评论区留言交流你的见解和代码实现方式。