异常教程

Python 求出 1 到 100 的质数（保姆级教程）

更新时间:

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

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

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

前言

在编程学习中，质数（Prime Number）的判断是一个经典的入门问题，也是理解算法效率和数学逻辑的重要案例。对于 Python 初学者而言，如何通过代码高效、准确地求出 1 到 100 的质数，既能巩固基础语法，又能培养逻辑思维。本文将从质数的定义出发，逐步讲解如何用 Python 实现这一目标，并通过案例分析和代码优化，帮助读者掌握这一知识点的核心逻辑。

一、质数的基本概念与数学原理

1.1 什么是质数？

质数是指大于 1 的自然数中，除了 1 和它本身以外没有其他因数的数。例如，2、3、5 是质数，而 4（因数有 1、2、4）和 6（因数有 1、2、3、6）则不是质数。
形象比喻：质数就像一群“孤独的数字”，它们只能被 1 和自己整除，无法被其他数字“拉拢”或“分解”。

1.2 如何判断一个数是否是质数？

判断质数的核心逻辑是：

  1. 遍历可能的因数：从 2 开始，到该数的平方根（√n）为止。
  2. 检查是否能整除：如果存在能整除的数，则该数不是质数；否则是质数。

数学优化点：

  • 无需遍历到 n-1，只需要遍历到 √n。例如，判断 100 是否是质数时，只需检查到 10（因为 10×10=100）。
  • 偶数（除了 2）都不是质数，可以提前排除。

二、基础实现：循环遍历法

2.1 最简单的暴力解法

直接遍历 1 到 100 的每个数，逐个判断是否是质数。

for num in range(1, 101):  
    if num > 1:  # 质数必须大于 1  
        is_prime = True  
        for i in range(2, num):  
            if num % i == 0:  
                is_prime = False  
                break  
        if is_prime:  
            print(num)

代码解析：

  • 外层循环：遍历 1 到 100 的所有数。
  • 内层循环：对每个数 num，从 2 开始遍历到 num-1，检查是否存在因数。
  • 标记变量 is_prime：默认为 True，若发现因数则设为 False，并跳出内层循环。

缺点：

  • 效率低：对于大数（如 100），内层循环次数过多。例如，判断 100 是否是质数时，需要遍历到 99 次。

2.2 优化：减少循环次数

利用数学原理，将内层循环的上限改为 √num。

import math  

for num in range(1, 101):  
    if num > 1:  
        is_prime = True  
        # 计算平方根作为循环上限  
        max_divisor = int(math.sqrt(num)) + 1  
        for i in range(2, max_divisor):  
            if num % i == 0:  
                is_prime = False  
                break  
        if is_prime:  
            print(num)

优化效果：

  • 计算 √num：例如，判断 100 时，只需遍历到 10（√100=10）。
  • 时间复杂度降低：从 O(n²) 优化到 O(n√n)，但对 100 这样的小范围数据，提升不明显。

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

3.1 筛法的原理

埃拉托斯特尼筛法是一种高效的质数筛选算法，其核心思想是：

  1. 创建一个布尔数组，初始时所有元素设为 True（假设都是质数）。
  2. 逐个筛除非质数：从最小的质数 2 开始，将它的倍数标记为 False；然后找到下一个未被标记的数，继续筛除其倍数，直到处理完整个数组。

形象比喻：想象有一排数字，像“筛子”一样不断过滤掉非质数，最终剩下的就是质数。

3.2 筛法的 Python 实现

def sieve_of_eratosthenes(n):  
    sieve = [True] * (n + 1)  
    sieve[0:2] = [False, False]  # 0 和 1 不是质数  
    for current in range(2, int(math.sqrt(n)) + 1):  
        if sieve[current]:  
            # 将当前数的倍数标记为非质数  
            sieve[current*current : n+1 : current] = [False]*len(sieve[current*current : n+1 : current])  
    primes = [num for num, is_prime in enumerate(sieve) if is_prime]  
    return primes  

primes = sieve_of_eratosthenes(100)  
print(primes)

代码解析：

  • 初始化筛子数组：长度为 n+1，初始值全为 True。
  • 遍历到 √n：因为更大的数的倍数已经被之前的质数筛掉了。
  • 步长标记：从 current*current 开始，以 current 为步长，将倍数标记为 False。
  • 最终结果：通过列表推导式提取所有标记为 True 的索引（即质数）。

优势：

  • 时间复杂度：O(n log log n)，比暴力法更高效。
  • 适合大规模数据：例如求 1 到 10000 的质数时，筛法的效率优势会更明显。

四、代码优化与性能对比

4.1 不同方法的性能测试

通过对比三种方法的执行时间，可以直观看到优化效果：

import time  

def method1(n):  
    primes = []  
    for num in range(2, n+1):  
        for i in range(2, num):  
            if num % i == 0:  
                break  
        else:  
            primes.append(num)  
    return primes  

def method2(n):  
    primes = []  
    for num in range(2, n+1):  
        max_divisor = int(math.sqrt(num)) + 1  
        for i in range(2, max_divisor):  
            if num % i == 0:  
                break  
        else:  
            primes.append(num)  
    return primes  

start = time.time()  
method1(100)  
print(f"Method1: {time.time() - start:.6f} seconds")  

start = time.time()  
method2(100)  
print(f"Method2: {time.time() - start:.6f} seconds")  

start = time.time()  
sieve_of_eratosthenes(100)  
print(f"Sieve: {time.time() - start:.6f} seconds")

结果示例（理论值，实际可能因环境有差异）：

方法名执行时间（秒）
Method10.002
Method20.001
Sieve0.0001

分析：

  • Method1：未优化的暴力法，效率最低。
  • Method2：通过 √n 优化，时间减半。
  • Sieve：筛法的高效性在大规模数据中会更显著。

五、常见问题与调试技巧

5.1 为什么 1 不是质数？

根据质数的定义，质数必须有 恰好两个不同的因数（1 和自身）。而 1 只有一个因数，因此被排除。

5.2 如何避免重复计算？

在筛法中，从 current*current 开始标记倍数，因为更小的倍数已经被之前的质数处理过。例如，当处理到 3 时，6 已经被 2 的倍数标记过。

5.3 代码中常见的错误

  • 循环范围错误：例如，将 range(2, n) 写成 range(2, n+1)，导致漏掉最后一个数。
  • 逻辑错误：在暴力法中，忘记排除 1 或未正确重置 is_prime 标记。

六、总结与扩展

6.1 核心知识点回顾

本文通过三种方法逐步优化了 Python 求质数的逻辑：

  1. 暴力循环法：直观但低效。
  2. 数学优化法：利用 √n 减少循环次数。
  3. 埃拉托斯特尼筛法：高效且适合大规模数据。

6.2 学习建议

  • 动手实践：尝试修改代码，求解 1 到 1000 的质数，并观察时间差异。
  • 深入数学：研究质数分布规律，例如孪生质数、梅森质数等。
  • 算法学习：探索其他质数判断算法，如米勒-拉宾素性测试（Miller-Rabin）。

6.3 结语

质数的求解不仅是编程的基础练习，更是理解算法优化和数学逻辑的桥梁。通过本文的方法对比和代码示例，读者可以逐步掌握从“能运行”到“高效运行”的编程思维，为更复杂的算法问题打下坚实基础。

通过本文的学习，读者可以轻松掌握如何用 Python 实现“求出 1 到 100 的质数”，并理解不同方法背后的数学原理与优化逻辑。希望这些内容能激发你对编程和数学的兴趣，继续探索更深层次的知识！

最新发布

查看更多文章