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

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

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

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

---

一、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]