蓝桥杯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]
相关文章:
蓝桥杯Python赛道备赛——Day5:算术(一)(数学问题)
笔者计划用两期博客对蓝桥杯中所涉及的算术(数学问题)进行解释,本期博客包括:GCD(最大公约数)、LCM(最小公倍数)、质数判断、埃氏筛法、线性筛法(欧拉筛)和质…...
Android的消息机制
Android的消息机制-从入门到精通 前言Android消息机制概述Android 的消息机制分析ThreadLocal 的工作原理消息队列的工作原理Looper的工作原理Handler的工作原理 主线程的消息循环 前言 作为开发者,提及Android的消息机制,必然绕不开Handler,…...
Three.js 阴影 (Shadow) 知识点整理
阴影主要由 castShadow 和 receiveShadow 控制,并通过不同类型的光源 (DirectionalLight、SpotLight、PointLight) 生成。我们将系统地整理与阴影相关的知识点。 1️⃣ 基础概念 castShadow 🎭:物体是否投射阴影。receiveShadow Ἵ…...
从C语言开始的C++编程生活(1)
前言 本系列文章承接C语言的学习,需要有C语言的基础才能学会哦。 第1篇主要讲的是有关于C的命名空间、输入和输出。 C才起步,都很简单呢! 目录 前言 命名空间namespace 基本语法 作用 使用命名空间 域作用限定符 :: 基本语法 using n…...
【数据库】如何用索引优化查询性能
引言 在数据库查询中,索引是提升性能的关键工具。合理使用索引可以显著减少数据扫描量,加快查询速度。然而,索引的使用也需要谨慎,错误的索引策略可能导致性能下降甚至系统崩溃。本文将深入探讨如何通过索引优化查询性能…...
【Go每日一练】随机密码生成器
👻创作者:丶重明 👻创作时间:2025年3月17日 👻擅长领域:运维 目录 1.😶🌫️题目:随机密码生成器2.😶🌫️密码生成可用资源3.😶&…...
【QA】模板方法模式在Qt中有哪些应用?
在 Qt 框架中,模板方法模式(Template Method Pattern)被广泛应用于框架的设计中,通过定义算法骨架并允许子类在不改变结构的情况下重写部分步骤。以下是 Qt 中典型的应用场景及示例: 1. 事件处理(Event Ha…...
VSTO(C#)Excel开发13:实现定时器
初级代码游戏的专栏介绍与文章目录-CSDN博客 我的github:codetoys,所有代码都将会位于ctfc库中。已经放入库中我会指出在库中的位置。 这些代码大部分以Linux为目标但部分代码是纯C的,可以在任何平台上使用。 源码指引:github源…...
Vue:单文件组件
Vue:单文件组件 1、 什么是单文件组件? 在传统的Vue开发里,我们接触的是非单文件组件,它们通常被定义在同一个HTML文件中,随着项目规模的扩大,代码会变得杂乱无章,维护起来极为困难。而单文件…...
网络编程---创建客户端和服务端以及协议包
一,创建客户端和服务端的思维导图 首先我们要知道客户端和服务端在网络中进行通信是依靠IP地址和端口号的,所以第一步就是创建一个套接字存储ip和port。通过套接字建立连接后通过read,write函数实现两者之间的交流(套接字的描述符…...
云安全相关博客阅读(四)
How we built Pingora, the proxy that connects Cloudflare to the Internet 基于 Rust 构建 Pingora,作为 Nginx 的替代方案; Nginx 作为常用代理服务,广泛应用于 CDN、WAF、Stream、Tunnel 等场景,是基础网络设施 然而&…...
靶场(十三)---小白心得思路分享---Levram
启程: 老样子开扫端口,22端口自动忽略,看到8000端口搭载着Gerapy服务 PORT STATE SERVICE VERSION 22/tcp open ssh OpenSSH 8.9p1 Ubuntu 3 (Ubuntu Linux; protocol 2.0) | ssh-hostkey: | 256 b9:bc:8f:01:3f:85:5d:f9…...
高级java每日一道面试题-2025年3月04日-微服务篇[Eureka篇]-Eureka是什么?
如果有遗漏,评论区告诉我进行补充 面试官: Eureka是什么? 我回答: 在Java高级面试中,关于Eureka的讨论通常会涵盖其基本概念、组件与架构、工作原理、高级特性以及与其他服务发现工具的比较等多个方面。以下是结合提供的内容对Eureka进行的详细解析和…...
Linux的根目录全知道
Linux的根目录(/)遵循文件系统层次结构标准(FHS),定义了各目录的用途。以下是主要目录及其功能的详细说明: 核心目录结构 /bin 作用:存放基础用户命令(所有用户可用)。示例:ls, cp, cat, bash等。注意:在部分系统中,/bin可能是/usr/bin的符号链接(通过usrmerge合并…...
嵌入式裸机设计--MCU常用裸机架构有哪些?
为什么是裸机设计 792125321入群学习更高效! 在MCU(微控制器单元)裸机开发中,我们常见的架构设计主要围绕如何高效管理资源和任务调度。认识这些开发方式,对我们开发一个小型项目来说及有好处! 下面介绍…...
基于FPGA频率、幅度、相位可调的任意函数发生器(DDS)实现
基于FPGA实现频率、幅度、相位可调的DDS 1 摘要 直接数字合成器( DDS ) 是一种通过生成数字形式的时变信号并进行数模转换来产生模拟波形(通常为正弦波)的方法,它通过数字方式直接合成信号,而不是通过模拟信号生成技术。DDS主要被应用于信号生成、通信系统中的本振、函…...
Rocky Linux 9.x 基于 kubeadm部署k8s 1.32
一、部署说明 1、主机操作系统说明 序号操作系统及版本备注1Rocky Linux release 9下载链接:https://mirrors.163.com/rocky/9.5/isos/x86_64/Rocky-9.5-x86_64-minimal.iso 2、主机硬件配置说明 作用IP地址操作系统配置关键组件k8s-master01192.168.234.51Rocky…...
linux入侵排查-综合日志分析
1.综合日志分析 1.掌握linux环境下系统日志的分析方法 2.掌握web访问日志的分析方法 3.掌握数据库日志的分析方法 4.掌握数据库日志的分析方法 5.熟悉linux中常用日志分析命令 实验环境 2.实验预设问题 1.定位攻击者ip地址 2.分析攻击者首次成功登录web管理后台的时间 …...
网络华为HCIA+HCIP 以太网链路聚合与交换机堆叠、集群
网络可靠性 网络的可靠性指当设备或者链路出现单点或者多点故障时保证网络服务不间断的能力。网络的可靠性可以从单板、设备、链路多个层面实现。 单板可靠性 以S12700E-8为例,设备提供8个线路板槽位、4个交换网板槽位、2个主控板槽位、6个电源模块槽位、4个风扇…...
[原创](Modern C++)现代C++的关键性概念: 灵活多变的绑定: std::bind
[作者] 常用网名: 猪头三 出生日期: 1981.XX.XX 企鹅交流: 643439947 个人网站: 80x86汇编小站 编程生涯: 2001年~至今[共24年] 职业生涯: 22年 开发语言: C/C、80x86ASM、Object Pascal、Objective-C、C#、R、Python、PHP、Perl、 开发工具: Visual Studio、Delphi、XCode、C …...
[QT]深入理解Qt中的信号与槽机制
文章目录 信号与槽1. 信号和槽概述信号的本质槽的本质说明 2. 信号和槽的使用2.1 连接信号和槽2.2 查看内置信号和槽2.3 通过 Qt Creator 生成信号槽代码 3. 自定义信号和槽3.1 基本语法3.2 带参数的信号和槽**示例1:重载信号槽****示例2:信号槽参数列表…...
电脑管家如何清理内存及垃圾,提升电脑性能
电脑在长时间使用后,常常会变得越来越卡顿,打开程序的速度变慢,甚至响应迟缓。这时,不少用户会选择使用电脑管家来进行内存清理和垃圾清理。那么,电脑管家是如何清理内存的?它又是如何清理垃圾的࿱…...
OpenCV图像处理:分割、合并、打码、组合与边界填充
引言 OpenCV是一个功能强大的计算机视觉库,广泛应用于图像处理、视频分析、物体检测等领域。本文将结合代码示例,详细介绍如何使用OpenCV进行图像的分割、合并、打码、组合以及边界填充等操作。 1. 图像的分割与合并 1.1 图像分割 在OpenCV中ÿ…...
游戏立项时期随笔记录(1)
模拟经营的项目还没有完全结束,这几天又有可能涉及到一个新项目。感想随笔记录一下,防止忘记。今天一天整理这个,搞得今天没时间看数学和AI。 在 Unity3D 游戏前端主程序的立项时期,核心目标是明确技术方向、评估可行性、搭建基础…...
C#入门学习记录(四)C#运算符详解:掌握算术与条件运算符的必备技巧+字符串拼接
一、运算符概述 运算符是程序进行数学运算、逻辑判断的核心工具,C#中的运算符分为: 算术运算符 → 数学计算( - * / %) 条件运算符 → 三目判断(?:) 关系运算符 → 比较大小(> < &#…...
DeepSeek 3FS 与 JuiceFS:架构与特性比较
近期,DeepSeek 开源了其文件系统 Fire-Flyer File System (3FS),使得文件系统这一有着 70 多年历时的“古老”的技术,又获得了各方的关注。在 AI 业务中,企业需要处理大量的文本、图像、视频等非结构化数据,还需要应对…...
汽车PKE无钥匙进入系统一键启动系统定义与原理
汽车智能钥匙(PKE无钥匙进入系统)一键启动介绍 系统定义与原理 汽车无钥匙进入系统,简称PKE(Passive Keyless Entry),该系统采用了RFID无线射频技术和车辆身份编码识别系统,率先应用小型化、小…...
【深度学习与大模型基础】第6章-对角矩阵,对称矩阵,正交矩阵
一、对角矩阵 对角矩阵(Diagonal Matrix)是一种特殊的方阵,其非对角线上的元素均为零,只有对角线上的元素可能非零。具体来说,对于一个 nn的矩阵 A[],如果满足 则 AA 称为对角矩阵。对角矩阵通常表示为&am…...
go语言中切片的长度和容量详解
Go 语言中,切片(Slice) 是一种动态数组,它的核心特性由 长度(Length) 和 容量(Capacity) 共同定义。这两个概念是操作切片时的关键,理解它们的含义和区别能帮助你高效管理内存并避免常见错误。 一、长度(Length) 定义:切片的长度表示当前包含的实际元素个数,即可以…...
在Vue3中使用$router.push方法进行路由跳转时,如何传递多个路径参数?
在 Vue 3 里,你可以借助 $router.push 方法进行路由跳转,同时传递多个路径参数。下面为你详细介绍具体实现方式: 1. 路由配置 首先,要在路由配置中定义好需要的路径参数。示例如下: import { createRouter, createW…...
C语言学习笔记(第三部份)
说明:由于所有内容放在一个md文件中会非常卡顿,本文件将接续C_1.md文件的第三部分 整型存储和大小端 引例: int main(void) {// printf("%d\n", SnAdda(2, 5));// PrintDaffodilNum(10000);// PrintRhombus(3);int i 0;int arr[…...
软考 中级软件设计师 考点知识点笔记总结 day05
文章目录 4、栈和队列4.1、栈的定义4.2、队列定义 5、串、数组、矩阵和广义表5.1、串5.2、 数组5.3、稀疏矩阵5.4、广义表 4、栈和队列 4.1、栈的定义 线性表是具有相同数据类型的n个数据元素的有限序列, n为表厂。n0时 线性表是一个空表 L (a1,a2,a3…...
【Linux】system V消息队列,信号量
🔥个人主页:Quitecoder 🔥专栏:linux笔记仓 目录 01.消息队列System V 消息队列接口 02.信号量System V 信号量接口 03.OS对system V ipc的管理消息队列管理结构共享内存管理结构信号量管理结构 01.消息队列 消息队列提供了一个…...
【新能源汽车“心脏”赋能:三电系统研发、测试与应用匹配的恒压恒流源技术秘籍】
新能源汽车“心脏”赋能:三电系统研发、测试与应用匹配的恒压恒流源技术秘籍 在新能源汽车蓬勃发展的浪潮中,三电系统(电池、电机、电控)无疑是其核心驱动力。而恒压源与恒流源,作为电源管理的关键要素,在…...
在 Vue.js 中使用递归组件:轻松处理嵌套数据结构
在开发前端应用时,我们经常会遇到需要处理嵌套数据结构的场景,比如树形菜单、评论列表、文件夹结构等。Vue.js 提供了一种优雅的方式来解决这类问题——递归组件。通过递归组件,我们可以轻松地渲染嵌套数据,并保持代码的简洁和可维…...
飞腾2000+/64核加固服务器
在当今信息化高速发展的时代,数据中心作为信息技术的核心支撑,其稳定性、安全性和高效性成为了各行各业关注的焦点。特别是在国防、金融、电信等关键领域,对服务器的性能、可靠性和安全性提出了前所未有的高要求。正是在这样的背景下…...
AutoMQ x OSS 的 Iceberg 数据入湖的最佳实践
背景 在数字化转型进程中,用户交互行为产生的多维度数据已成为企业的重要战略资产。以短视频平台为例,基于用户点赞事件的实时推荐算法能显著提升用户活跃度和平台粘性。这类实时数据主要通过 Apache Kafka 流处理平台进行传输,通过其扇出&a…...
深度学习大模型补充知识点
文章目录 VIT用途处理方法与CNN区别 多模态LLM:大语言模型预训练指令微调强化学习 总结 VIT ViT(Vision Transformer) 首次将 Transformer架构成功应用于计算机视觉领域(尤其是图像分类任务)。传统视觉任务主要依赖卷…...
定义模型生成数据表
1. 数据库配置 js import { Sequelize, DataTypes } from sequelize; // 创建一个 Sequelize 实例,连接到 SQLite 数据库。 export const sequelize new Sequelize(test, sa, "123456", { host: localhost, dialect: sqlite, storage: ./blog.db })…...
C++与C的基本不同
文章目录 变量定义规则1. 基本语法2. 初始化3. 作用域4. 存储类别 函数定义规则1. 基本语法2. 函数声明和定义3. 默认参数4. 内联函数 解析输出流void BluetoothA2DPSink::start(const char* name)class BluetoothA2DPSink : public BluetoothA2DPCommon C是在C语言基础上发展而…...
React19源码系列之createRoot的执行流程是怎么的?
2024年12月5日,react发布了react19版本。后面一段时间都将学习它的源码,并着手记录。 react官网:react19新特性 https://react.dev/blog/2024/12/05/react-19 在用vite创建react项目的使用,main.tsx主文件都会有以下代码。 //i…...
【CXX-Qt】1.5 使用CMake构建
在本示例中,我们将演示如何使用CMake将CXX-Qt代码集成到C应用程序中。Cargo将CXX-Qt代码构建为静态库,然后CMake将其链接到C可执行文件中。 我们首先需要修改项目结构,以分离项目的不同部分。 tutorial cpp qml rust将Rust项目移动到rust文…...
前端面试项目拷打
Axios相关 1.在Axios二次封装时,具体封装了哪些内容,如何处理请求拦截和响应拦截? axios二次封装的目的:为了统一处理请求和响应拦截器、错误处理、请求超时、请求头配置等,提高代码可维护性和复用性。 首先创建axios…...
“Ubuntu禁止root用户通过SSH直接登录”问题的解决
目录 1 前言 2 问题的解决 2.1 修改sshd_config文件 2.2 重启 SSH 服务 1 前言 最近在做毕设的时候,由于使用普通用户,在MobaXterm的图形界面上,无法正常查看/root文件夹内容,如下图所示: 于是我就想直接想用oot…...
Kafka的零拷贝
Kafka的零拷贝(Zero-Copy)技术是其实现高吞吐量的关键优化之一,主要通过减少数据在内核空间和用户空间之间的冗余复制及上下文切换来提升性能。以下是其核心要点: 1. 传统数据拷贝的问题 多次复制:传统文件传输需经历…...
《大语言模型》学习笔记(三)
GPT系列模型的技术演变 2022 年11月底,OpenAI推出了基于大语言模型的在线对话应用—ChatGPT。由于具备出色的人机对话能力和任务解决能力,ChatGPT一经发布就引发了全社会对于大语言模型的广泛关注,众多的大语言模型应运而生,并且…...
华为OD机试 - 最长回文字符串 - 贪心算法(Java 2024 E卷 100分)
题目描述 如果一个字符串正读和反读都一样(大小写敏感),则称之为一个「回文串」。例如: level 是一个「回文串」,因为它的正读和反读都是 level。art 不是一个「回文串」,因为它的反读 tra 与正读不同。Level 不是一个「回文串」,因为它的反读 leveL 与正读不同(因大小…...
K8S-etcd服务无法启动问题排查
一、环境、版本信息说明 k8s:v1.19.16 etcdctl version: 3.5.1 3台etcd(10.xxx.xx.129、10.xxx.xx.130、10.xxx.xx.131)组成的集群。 二、问题根因 129节点的etcd数据与其他两台数据不一致,集群一致性校验出错导致无法加入集…...
基于WebRTC的嵌入式音视频通话SDK:EasyRTC跨平台兼容性技术架构实时通信的底层实现
EasyRTC的核心架构围绕WebRTC技术构建,同时通过扩展信令服务、媒体服务器和NAT穿透机制,解决了WebRTC在实际部署中的痛点。其架构可以分为以下几个核心模块: 1)WebRTC基础层 媒体捕获与处理:通过getUserMediaAPI获取…...
SpringBoot-已添加并下载的依赖,reload和mvn clean 后还是提示找不到jar包问题
背景: 添加spring-jdbc依赖时,原来是指定版本的,担心版本冲突,就改成依赖托管,悲剧的是反复reload和mvn clean,import到类的该包一直标红,提示jar包找不到。。。 解决方案: Idea左上…...