Python – 获取 100 以内的质数（完整指南）

Python – 获取 100 以内的质数：从零开始的编程实践

在学习编程的过程中，你有没有遇到过这样的问题：如何用代码找出 100 以内的所有质数？这看似简单的小任务，其实包含了判断逻辑、循环控制、函数封装等多个核心知识点。今天我们就来一起动手实现这个经典题目——Python – 获取 100 以内的质数，适合初学者打基础，也适合中级开发者复习算法思维。

质数，就是只能被 1 和它本身整除的大于 1 的自然数。比如 2、3、5、7、11 都是质数，而 4、6、8、9 这些数因为能被其他数整除，所以不是质数。我们要做的，就是让 Python 帮我们自动筛选出所有符合条件的数。

什么是质数？一个形象的比喻

想象一下，你有一堆数字，它们像一群小朋友在排队。我们要做的，就是找出那些“独来独往”的小朋友——他们只愿意和自己玩，不愿意和别人一起分享糖果（也就是被整除）。

比如 7，它只能被 1 和 7 整除，不能被 2、3、4、5、6 整除，所以它是个“独行侠”——质数。
而 8 就不一样了，它能被 2 和 4 整除，说明它“有朋友”，不是质数。

这个“独来独往”的特性，就是我们判断质数的核心依据。

方法一：基础判断法（暴力枚举）

我们先从最直观的方式开始。对 1 到 100 的每一个数，都去检查它是不是质数。

def is_prime(n):
    # 小于等于 1 的数不是质数
    if n <= 1:
        return False
    # 2 是质数，直接返回 True
    if n == 2:
        return True
    # 偶数（除了 2）都不是质数
    if n % 2 == 0:
        return False
    # 从 3 开始，只检查到 sqrt(n) 为止
    # 因为如果 n 有因子，一定有一个小于等于 sqrt(n)
    i = 3
    while i * i <= n:
        if n % i == 0:
            return False  # 找到因子，说明不是质数
        i += 2  # 只检查奇数，提高效率
    return True  # 没找到因子，是质数

primes = []
for num in range(1, 101):
    if is_prime(num):
        primes.append(num)

print("100 以内的质数有：")
print(primes)

代码解析

• is_prime(n)：判断一个数是否为质数，是整个逻辑的核心。
• if n <= 1：质数必须大于 1，所以直接排除。
• if n == 2：2 是唯一的偶数质数，提前返回。
• if n % 2 == 0：所有其他偶数都不可能是质数，跳过。
• while i * i <= n：这是关键优化。如果一个数 n 有大于 sqrt(n) 的因子，那必然有一个小于 sqrt(n) 的对应因子。所以只需检查到根号 n 即可。
• i += 2：因为已经排除了偶数，所以只检查奇数，节省一半时间。

运行这段代码，你会看到输出：

100 以内的质数有：
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

共 25 个质数，完全正确。

方法二：埃拉托斯特尼筛法（高效算法）

如果你觉得上面的方法虽然正确，但效率不够高，我们可以引入一个更高效的算法——埃拉托斯特尼筛法（Sieve of Eratosthenes）。

这个方法的思路很巧妙：先假设所有数都是质数，然后逐步“筛掉”不是质数的数。

筛法原理

想象你有一张 1 到 100 的数字表。你从 2 开始，把 2 的所有倍数（4, 6, 8, ...）都标记为“非质数”。然后跳到下一个未被标记的数，也就是 3，把 3 的倍数（6, 9, 12, ...）也筛掉。接着是 5、7……直到处理完所有小于等于 sqrt(100) 的数。

最终剩下的没被筛掉的，就是质数。

def sieve_of_eratosthenes(n):
    # 创建一个布尔数组，初始都设为 True
    # is_prime[i] 表示数字 i 是否为质数
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False  # 0 和 1 不是质数

    # 从 2 开始，到 sqrt(n) 结束
    i = 2
    while i * i <= n:
        if is_prime[i]:  # 如果 i 是质数
            # 将 i 的所有倍数从 i*i 开始标记为非质数
            # 从 i*i 开始，是因为更小的倍数已经被更小的质数筛过了
            j = i * i
            while j <= n:
                is_prime[j] = False
                j += i
        i += 1

    # 收集所有为 True 的数，即质数
    primes = [num for num in range(2, n + 1) if is_prime[num]]
    return primes

primes = sieve_of_eratosthenes(100)
print("100 以内的质数有：")
print(primes)

代码解析

• is_prime = [True] * (n + 1)：创建一个长度为 101 的列表，索引代表数字，值代表是否为质数。
• is_prime[0] = is_prime[1] = False：明确排除 0 和 1。
• while i * i <= n：只需要处理到根号 n，因为更大的数的倍数已经在前面处理过了。
• j = i * i：从 i*i 开始标记，因为 2*i、3*i 等可能已经被更小的质数筛过了（比如 6 已被 2 筛掉）。
• j += i：逐步标记 i 的倍数。
• 最后用列表推导式提取所有为 True 的数字。

这个方法的时间复杂度是 O(n log log n)，远优于暴力法的 O(n√n)，尤其适合处理大范围的质数筛选。

性能对比：两种方法谁更快？

为了直观感受差异，我们来做一个小实验。分别用两种方法计算 100 以内的质数，记录耗时。

import time

start = time.time()
primes1 = []
for num in range(1, 101):
    if is_prime(num):
        primes1.append(num)
time1 = time.time() - start

start = time.time()
primes2 = sieve_of_eratosthenes(100)
time2 = time.time() - start

print(f"基础判断法耗时：{time1:.6f} 秒")
print(f"筛法耗时：{time2:.6f} 秒")

运行结果通常显示：筛法快 5 到 10 倍。

这说明，算法的优化，远比硬件提升更重要。在编程中，选对算法，是写出高效代码的关键。

实际应用场景

你可能会问：这些质数有什么用？其实它们在现实中有不少应用场景：

• 密码学：RSA 加密算法依赖大质数的难以分解特性。
• 哈希表：选择质数作为数组长度，能减少冲突。
• 随机数生成：某些算法会用质数作为模数。

即使你只是想写个小程序验证质数，掌握这些方法也能为你后续学习打下坚实基础。

常见误区与调试建议

在实现过程中，初学者常犯几个错误：

1. 忘记处理 2：2 是唯一的偶数质数，不能直接排除所有偶数。
2. 循环边界错误：比如 i <= n 而不是 i * i <= n，会导致程序变慢。
3. 从 2*2 开始筛：漏掉 i*i，可能导致重复标记或漏筛。

建议：写完代码后，手动验证几个关键数，比如 2、3、4、5、9、25、49，确保逻辑正确。

总结：Python – 获取 100 以内的质数的完整实践

通过本文，我们从基础判断法入手，逐步引入更高效的筛法，不仅完成了“Python – 获取 100 以内的质数”这一任务，还深入理解了质数的本质、算法优化的重要性，以及实际应用价值。

• 基础判断法适合理解逻辑，代码清晰易懂。
• 埃拉托斯特尼筛法适合处理大范围数据，性能卓越。

无论你是编程新手，还是想巩固基础的开发者，掌握这两种方法，都能让你在算法思维上更进一步。

最后提醒一句：编程不是背代码，而是理解问题本质，选择合适工具。下次遇到类似问题，不妨先问自己：有没有更聪明的办法？也许，答案就在“筛法”里。

Python – 获取 100 以内的质数，不只是一个练习题，更是一次思维的训练。动手试试吧，你会发现编程的乐趣，就藏在一行行代码里。