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

蓝桥杯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]

http://www.kler.cn/a/586987.html

相关文章:

  • 在Linux中安装Nginx
  • 机器学习之线性代数
  • 【蓝桥杯】24省赛:数字串个数
  • 使用 BookMarkHub 插件进行书签同步
  • 一文了解CAS
  • linux 命令 ls
  • 网络爬虫【简介】
  • 基于vue-grid-layout 实现自定义首页视图
  • Tailwindcss开启黑夜模式
  • Python扑克牌游戏更新哦~【增加更多牌类】
  • 获取golang变量的类型
  • Redis分片集群
  • 机器学习与深度学习中模型训练时常用的四种正则化技术L1,L2,L21,ElasticNet
  • springboot集成flink实现DM数据库同步到ES
  • RabbitMq C++客户端的使用
  • 使用SetupTools 管理你的项目打包工作
  • 如何用URDF文件构建机械手模型并与MoveIt集成
  • 【Tools】Visual Studio Code安装保姆级教程(2025版)
  • Typora最新版破解教程
  • 音视频入门基础:RTP专题(20)——通过FFprobe显示RTP流每个packet的信息