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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/34164.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

OTP单片机调试工具之—单线数据编码

OTP单片机调试工具在实现过程中离不开单线数据的传输&#xff0c;那么使用哪一种方式的数据编码会比较好呢&#xff1f; 我所了解的主要有以下三种&#xff1a; 1.UART&#xff08;串口&#xff09;&#xff0c;这种方式在单片机和pc之间进行传输都非常常见&#xff0c;效率比较…

背诵--2

DAY01 面向对象回顾、继承、抽象类 学习目标 能够写出类的继承格式public class 子类 extends 父类{}public class Cat extends Animal{} 能够说出继承的特点子类继承父类,就会自动拥有父类非私有的成员 能够说出子类调用父类的成员特点1.子类有使用子类自己的2.子类没有使用…

穷举vs暴搜vs深搜vs回溯vs剪枝刷题 + 总结

文章目录 全排列题解代码 子集题解代码 总结 全排列 题目链接 题解 1. 画一颗决策树 2. 全局变量&#xff1a; int[ ][ ] ret&#xff1a;用于存结果的二维数组 int[ ] path&#xff1a;用于存每次路径的答案 bool[ ] check&#xff1a;判断这个数是否已经用过&#xff0c;…

深度学习中学习率调整策略

学习率衰减策略是深度学习优化过程中的一个关键因素&#xff0c;它决定了训练过程中学习率的调整方式&#xff0c;从而影响模型收敛的速度和效果。不同的衰减策略在不同的任务和模型上可能有不同的表现&#xff0c;下面从我用到过的几个衰减策略进行记录&#xff0c;后续慢慢跟…

《Electron 学习之旅:从入门到实践》

前言 Electron 简介 Electron 是由 GitHub 开发的一个开源框架&#xff0c;基于 Chromium 和 Node.js。 它允许开发者使用 Web 技术&#xff08;HTML、CSS、JavaScript&#xff09;构建跨平台的桌面应用程序。 Electron 的优势 跨平台&#xff1a;支持 Windows、macOS 和 Linux…

UBuntu24.04-JDK7-TOMCAT7安装

jdk7 apt-get 找不到。 tomcat7 也没找到。 以下是安装成功的&#xff0c;供大家参考。 1.JAVA openjdk-7-jdk /usr/lib/jvm/java-7-openjdk-amd641.安装指定版本apt search jdk //查找版本sudo apt install default-jdk //此为默认版本sudo apt install ope…

美畅物联丨WebRTC 技术详解:构建实时通信的数字桥梁

在互联网技术飞速发展的今天&#xff0c;实时通信已成为数字生活的核心需求。WebRTC作为一个开源项目&#xff0c;凭借卓越的技术实力与创新理念&#xff0c;为网页和移动应用带来了颠覆性的实时通信能力。它突破了传统通信方式的限制&#xff0c;实现了音频、视频和数据在用户…

驾驭 DeepSeek 科技之翼,翱翔现代学习新天际

在当今这个信息爆炸的时代&#xff0c;学习的方式和途径正在经历着前所未有的变革。人工智能技术的飞速发展&#xff0c;为我们的学习带来了全新的机遇和挑战。DeepSeek 作为一款强大的大语言模型&#xff0c;凭借其卓越的性能和丰富的功能&#xff0c;为现代学习注入了新的活力…

写时拷贝技术

目录 写时拷贝 核心思想 基本原理 基本过程 一个例子深入理解 补充知识--引用计数 小总结 写时拷贝实现 宏观理解&#xff08;进程、线程角度&#xff09; 资源共享 只读访问 写操作触发拷贝 独立修改 微观理解&#xff08;fork系统调用角度&#xff09; 进程创…

requests库的request和response对象的属性和方法

Python requests库 request 参数信息 response 参数信息

MySQL数据库操作

目录 SQL语句 1、SQL的背景 2、SQL的概念 SQL的分类 SQL的书写规范 MySQL数据库 1、MySQL数据库的编码 &#xff08;1&#xff09;utf8和utf8mb4的区别 &#xff08;2&#xff09;MySQL的字符集 &#xff08;3&#xff09;MySQL默认编码为 latin1 &#xff0c;如何更改…

Blender-MCP服务源码5-BlenderSocket插件安装

Blender-MCP服务源码5-BlenderSocket插件安装 上一篇讲述了Blender是基于Socket进行本地和远程进行通讯&#xff0c;现在尝试将BlenderSocket插件安装到Blender中进行功能调试 1-核心知识点 将开发的BlenderSocket插件安装到Blender中 2-思路整理 1&#xff09;将SocketServe…

Androidstudio实现一个app引导页(超详细)

文章目录 1. 功能需求2. 代码实现过程1. 创建布局文件2. 创建引导页的Adapter3. 实现引导页Activity4. 创建圆点指示器的Drawable5. 创建“立即体验”按钮的圆角背景 2.效果图 1. 功能需求 1、需要和原型图设计稿对应的元素保持一致的样式。 2、引导页需要隐藏导航栏&#xff…

蓝桥杯省赛真题C++B组-小球反弹

一、题目 有一长方形&#xff0c;长为 343720 单位长度&#xff0c;宽为 233333 单位长度。在其内部左上角顶点有一小球(无视其体积)&#xff0c;其初速度如图所示且保持运动速率不变&#xff0c;分解到长宽两个方向上的速率之比为 dx:dy 15:17。小球碰到长方形的边框时会发生…

基于深度学习的多模态人脸情绪识别研究与实现(视频+图像+语音)

这是一个结合图像和音频的情绪识别系统&#xff0c;从架构、数据准备、模型实现、训练等。包括数据收集、预处理、模型训练、融合方法、部署优化等全流程。确定完整系统的组成部分&#xff1a;数据收集与处理、模型设计与训练、多模态融合、系统集成、部署优化、用户界面等。详…

AI 数字人短视频源码开发:开启虚拟世界的创意引擎

在当今数字化浪潮中&#xff0c;AI 数字人正以惊人的速度融入我们的生活&#xff0c;尤其是在短视频领域&#xff0c;AI 数字人凭借其独特的魅力吸引了无数目光。从虚拟偶像的舞台表演到智能客服的贴心服务&#xff0c;AI 数字人已成为推动短视频行业创新发展的重要力量。而这背…

Java 代理模式:从静态代理到动态代理

前言 代理模式是 Java 中常见的设计模式之一&#xff0c;它的核心思想是通过一个代理对象来控制对真实对象的访问。代理模式不仅可以扩展目标对象的功能&#xff0c;而且在不修改原目标对象的情况下&#xff0c;可以增加一些我们自定义的操作。 1. 代理模式简介 代理模式的核心…

PyCharm 2019.1.3使用python3.9创建虚拟环境setuptools-40.8.0报错处理

目录 前置&#xff1a; 一劳永逸方法&#xff08;缺最后一步&#xff0c;没有成行&#xff09; step one: 下载高版本的pip、setuptools、virtualenv的tar.gz包 step two: 进入PyCharm安装目录的 helpers 目录下 step three: 下载并安装grep和sed命令&#xff0c;然后执行 …

word处理控件Aspose.Words教程:使用 Python 删除 Word 中的空白页

Aspose.Words 是一种高级Word文档处理API&#xff0c;用于执行各种文档管理和操作任务。API支持生成&#xff0c;修改&#xff0c;转换&#xff0c;呈现和打印文档&#xff0c;而无需在跨平台应用程序中直接使用Microsoft Word。 Aspose API支持流行文件格式处理&#xff0c;并…

C++数据结构1——栈结构详解

一、栈的基本概念与特性 1. 栈的定义与特点 栈&#xff08;Stack&#xff09;是一种遵循后进先出&#xff08;LIFO, Last In First Out&#xff09;原则的线性数据结构&#xff0c;其核心特征包括&#xff1a; 单端操作&#xff1a;所有操作仅通过栈顶进行 动态存储&#xf…