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

笔者计划用两期博客对蓝桥杯中所涉及的算术（数学问题）进行解释，本期博客包括：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):# 循环直到余数为0while 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):# 循环直到余数为0while 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 Falseif n == 2: return Trueif 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 Falsereturn Trueprint(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] = Falsereturn [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:breakmin_prime[i*p] = p  # 这是关键，标记最小质因子return primesprint(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 = 3while i*i <= n:while n % i == 0:factors.append(i)n = n // ii += 2  # 跳过偶数# 处理剩余质数if n > 2:factors.append(n)return factorsprint(prime_factors(123456)) 
# 输出：[2, 2, 2, 2, 2, 2, 3, 643]