当前位置：首页 > article >正文

蓝桥杯Python赛道备赛——Day5：算术（一）（数学问题）

article 2025/3/17 13:53:31

笔者计划用两期博客对蓝桥杯中所涉及的算术（数学问题）进行解释，本期博客包括：GCD（最大公约数）、LCM（最小公倍数）、质数判断、埃氏筛法、线性筛法（欧拉筛）和质因子分解。

每一种数学问题都在给出定义的同时，给出了其求解方法的示例代码，以供低年级师弟师妹们学习和练习。

前序知识：
（1）Python基础语法

基础算法（操作）

- - 一、GCD（最大公约数）
  - 二、LCM（最小公倍数）
  - 三、质数判断
  - 四、埃氏筛法
  - 五、线性筛法（欧拉筛）
  - 六、质因子分解

一、GCD（最大公约数）

1. 定义：
能同时整除两个数的最大正整数。

2. 算法原理——欧几里得算法（辗转相除法）：

用较大数除以较小数得到余数；
将较小数与余数重复步骤1；
当余数为0时，当前除数即为GCD。

3. 优缺点：

优点：时间复杂度O(log(min(a,b)))，效率极高；
缺点：依赖除法运算，对大整数运算需要优化。

4. 用途：
分数化简、线性同余方程、密码学。

5. 代码：

# 最大公约数 GCD
def gcd(a, b):
    # 循环直到余数为0
    while b != 0:
        # a接收除数，b接收余数
        a, b = b, a % b  # 核心计算步骤
    return abs(a)  # 保证返回正值

# 示例：计算48和18的最大公约数
print(gcd(48, 18))  # 输出：6

二、LCM（最小公倍数）

1. 定义：
能被两个数整除的最小正整数。

2. 算法原理：
公式法：lcm(a,b) = |a*b| / gcd(a,b)

3. 优缺点：

优点：计算快速，时间复杂度与gcd相同；
缺点：直接相乘可能溢出，需先做除法。

4. 用途：
周期性问题、时间同步计算。

5. 代码：

# 最小公倍数 LCM
# 最小公倍数可以通过最大公约数来计算
def gcd(a, b):
    # 循环直到余数为0
    while b != 0:
        # a接收除数，b接收余数
        a, b = b, a % b  # 核心计算步骤
    return abs(a)  # 保证返回正值

def lcm(a, b):
    # 先计算最大公约数
    g = gcd(a, b)
    # 使用整数除法避免浮点误差
    return abs(a * b) // g  # 注意处理负数

print(lcm(12, 18))  # 输出：36

三、质数判断

1. 定义：
大于1的自然数，仅能被1和自身整除。

2. 算法原理（试除法）：

检查2的特殊情况；
检查偶数快速返回；
只需试除到√n。

3. 优缺点：

优点：对小数字效率高；
缺点：对大数（>1e12）效率低。

4. 用途：
密码学、哈希函数。

5. 代码：

# 素数（质数）判断
def is_prime(n):
    if n < 2: return False
    if n == 2: return True
    if n % 2 == 0: return False
    # 只需检查到平方根的奇数
    max_divisor = int(n**0.5) + 1  # 避免浮点误差
    for i in range(3, max_divisor, 2):
        if n % i == 0:
            return False
    return True

print(is_prime(1000003))  # 输出：True

四、埃氏筛法

1. 定义：
通过标记倍数筛选质数的算法。

2. 算法原理：

创建布尔数组初始化标记；
从2开始，标记所有倍数；
剩余未标记的即为质数。

3. 优缺点：

优点：简单易懂，适合生成小范围质数；
缺点：重复标记（如6会被2和3标记）。

4. 用途：
预处理质数表、质因数分解。

5. 代码：

# 埃式筛法（埃拉托斯特尼筛法）
# 埃式筛法是一种用于找出一定范围内所有素数的算法。它通过迭代地标记非素数来工作。
def sieve_eratosthenes(n):
    is_prime = [True] * (n+1)
    is_prime[0:2] = [False, False]  # 0和1不是质数
    for i in range(2, int(n**0.5)+1):
        if is_prime[i]:
            # 从i²开始标记（i*(i-1)已被之前标记）
            for j in range(i*i, n+1, i):
                is_prime[j] = False
    return [i for i, prime in enumerate(is_prime) if prime]

print(sieve_eratosthenes(50)) 
# 输出：[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

五、线性筛法（欧拉筛）

1. 定义：
通过最小质因子筛选质数的算法。

2. 算法原理：

维护最小质因子数组；
每个合数只被其最小质因子标记；
保证每个数只被标记一次。

3. 优缺点：

优点：时间复杂度O(n)，无重复标记；
缺点：需要额外存储空间。

4. 用途：
需要大量质数的场景。

5. 代码：

# 线性筛法（欧拉筛法）
# 线性筛法是一种更高效的筛法，它可以在O(n)时间复杂度内找出一定范围内的所有素数。
def linear_sieve(n):
    primes = []
    min_prime = [0] * (n+1)  # 存储最小质因子
    for i in range(2, n+1):
        if min_prime[i] == 0:  # i是质数
            primes.append(i)
            min_prime[i] = i
        # 用已有质数筛后续数
        for p in primes:
            if p > min_prime[i] or i*p > n:
                break
            min_prime[i*p] = p  # 这是关键，标记最小质因子
    return primes

print(linear_sieve(50))  # 输出同埃氏筛

六、质因子分解

1. 定义：
将数分解为质数乘积形式。

2. 算法原理：

处理2的因子；
处理奇数因子；
处理剩余大质数。

3. 优缺点：

优点：直观展示数的组成；
缺点：对大质数效率低。

4. 代码：

# 质因子分解
def prime_factors(n):
    factors = []
    # 处理2的因子
    while n % 2 == 0:
        factors.append(2)
        n = n // 2  # 整除运算符
    # 处理奇数因子
    i = 3
    while i*i <= n:
        while n % i == 0:
            factors.append(i)
            n = n // i
        i += 2  # 跳过偶数
    # 处理剩余质数
    if n > 2:
        factors.append(n)
    return factors

print(prime_factors(123456)) 
# 输出：[2, 2, 2, 2, 2, 2, 3, 643]