蓝桥杯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):
# 循环直到余数为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]