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

算法之 数论

文章目录

质数

质数的定义:除了本身和1,不能被其他小于它的数整除,最小的质数是 2

求解质数的几种方法
法1,根据定义,直接求解

        def zhi(i):if i == 1:return Falsefor j in range(2,i):if i % j ==0:return Falsereturn True

法2:优化暴力的解法,判断的时候只用判断到根号n,因为你如果存在一个大于根号n的因子,那就说明会存在一个小于根号n的因子,所以就不用重新判断

def zhi(i):if n <= 1:return Falsefor i in range(2, int(math.sqrt(n)) + 1):if n % i == 0:return Falsereturn True

常用的素数筛:

埃氏筛

def eratosthenes_sieve(n):is_prime = [True] * (n + 1)  # 初始化所有数为质数is_prime[0] = is_prime[1] = False  # 0 和 1 不是质数for i in range(2, int(n**0.5) + 1):  # 只需遍历到 sqrt(n)if is_prime[i]:  # 如果 i 是质数for j in range(i * i, n + 1, i):  # 标记 i 的所有倍数为合数is_prime[j] = Falseprimes = [i for i, prime in enumerate(is_prime) if prime]  # 提取所有质数return primes

欧式筛
在这里插入图片描述

def euler_sieve(n):is_prime = [True] * (n + 1)  # 初始化所有数为质数primes = []  # 存储筛选出的质数for i in range(2, n + 1):if is_prime[i]:primes.append(i)  # i 是质数,加入 primes 数组for p in primes:if i * p > n:break  # 超过范围,退出循环is_prime[i * p] = False  # 标记 i * p 为合数if i % p == 0: # 说明 p 是 i 的最小的质因数break  # 保证每个合数只被最小质因数筛掉return primes

判断质数

3115.质数的最大距离

3115.质数的最大距离

在这里插入图片描述

思路分析:采用双指针进行判断,这样可以快速求解

class Solution:def maximumPrimeDifference(self, nums: List[int]) -> int:# 策略,使用双指针,从两边进行遍历,如果发现是质数就停下来# 判断质数def zhi(i):if i == 1:return Falsefor j in range(2,i):if i % j ==0:return Falsereturn Truen = len(nums)# 双指针l,r = 0,n-1while not zhi(nums[l]):l+=1while not zhi(nums[r]):r-=1return r-l

质数筛选

204.计数质数

204.计数质数

在这里插入图片描述

思路分析:直接考虑使用欧式筛,注意题目是小于n的素数个数

class Solution:def countPrimes(self, n: int) -> int:# 两种做法,可以采用欧式筛def euler(m):isprime = [True]*(m+1) # 存储判断i是否是素数prime = []for i in range(2,m):# 如果是素数if isprime[i]:prime.append(i)for j in prime:if i*j > m:breakisprime[i*j] = Falseif i%j ==0:break # 确保每个数字只能被最小的质因数筛选return primereturn len(euler(n))

2761.和等于目标值的质数对

2761.和等于目标值的质数对

在这里插入图片描述

思路分析:首先使用欧拉筛进行筛选出小于等于n的素数的情况,然后使用双指针进行判断

class Solution:def findPrimePairs(self, n: int) -> List[List[int]]:# 先使用欧式筛进行预处理def euler(m):isprime = [True]*(m+1)prime = []for i in range(2,m+1):if isprime[i]:prime.append(i)for j in prime:if i*j > m:breakisprime[i*j] = Falseif i%j == 0:breakreturn primeprime = euler(n)# 还是采用双指针吧length = len(prime)l,r = 0,length-1ans = []while l<=r:if prime[l]+prime[r] < n:l+=1elif prime[l]+prime[r] == n:ans.append([prime[l],prime[r]])l+=1r-=1else:r-=1# 排序非递减排序ans.sort(key=lambda x : x[0])return ans

2521.数组乘积中的不同质因数数目

2521.数组乘积中的不同质因数数目
在这里插入图片描述

思路分析:通过不断的判断

class Solution:def distinctPrimeFactors(self, nums: List[int]) -> int:s = set()for x in nums:i = 2while i*i <=x:if x % i == 0:s.add(i)x //= iwhile x%i == 0:x//=i i+=1# 最后可能只剩下那个数直接加进去if x>1:s.add(x)return len(s)

相关文章:

算法之 数论

文章目录 质数判断质数3115.质数的最大距离 质数筛选204.计数质数2761.和等于目标值的质数对 2521.数组乘积中的不同质因数数目 质数 质数的定义&#xff1a;除了本身和1&#xff0c;不能被其他小于它的数整除&#xff0c;最小的质数是 2 求解质数的几种方法 法1&#xff0c;根…...

Java 大视界 -- 人工智能驱动下 Java 大数据的技术革新与应用突破(83)

&#x1f496;亲爱的朋友们&#xff0c;热烈欢迎来到 青云交的博客&#xff01;能与诸位在此相逢&#xff0c;我倍感荣幸。在这飞速更迭的时代&#xff0c;我们都渴望一方心灵净土&#xff0c;而 我的博客 正是这样温暖的所在。这里为你呈上趣味与实用兼具的知识&#xff0c;也…...

【04】RUST特性

文章目录 隐藏shadowing所有权ownership堆区&栈区所有权规则变量&数据Copy Trait与Drop TraitCopy TraitDrop Trait移动克隆函数参数与返回值的所有权参数引用可变引用悬垂引用slice生命周期隐藏shadowing 有点像同名覆盖 let mut guess = String::new();let guess: u3…...

PlantUml常用语法

PlantUml常用语法&#xff0c;将从类图、流程图和序列图这三种最常用的图表类型开始。 类图 基础语法 在 PlantUML 中创建类图时&#xff0c;你可以定义类&#xff08;Class&#xff09;、接口&#xff08;Interface&#xff09;以及它们之间的关系&#xff0c;如继承&#…...

保存字典类型的文件用什么格式比较好

保存 Python 字典类型的数据时&#xff0c;有几个常见的格式可以选择&#xff0c;这些格式都具有良好的可读性和提取内容的便利性。以下是几种推荐的格式&#xff1a; JSON 格式&#xff1a; 优点&#xff1a;JSON 格式非常适合存储和传输结构化数据&#xff0c;具有良好的跨平…...

开源模型应用落地-Qwen1.5-MoE-A2.7B-Chat与vllm实现推理加速的正确姿势(一)

一、前言 在人工智能技术蓬勃发展的当下,大语言模型的性能与应用不断突破边界,为我们带来前所未有的体验。Qwen1.5-MoE-A2.7B-Chat 作为一款备受瞩目的大语言模型,以其独特的架构和强大的能力,在自然语言处理领域崭露头角。而 vllm 作为高效的推理库,为模型的部署与推理提…...

一竞技瓦拉几亚S4预选:YB 2-0击败GG

在2月11号进行的PGL瓦拉几亚S4西欧区预选赛上,留在欧洲训练的YB战队以2-0击败GG战队晋级下一轮。双方对阵第二局:对线期YB就打出了优势,中期依靠卡尔带队进攻不断扩大经济优势,最终轻松碾压拿下比赛胜利,以下是对决战报。 YB战队在天辉。阵容是潮汐、卡尔、沙王、隐刺、发条。G…...

deepseek+kimi一键生成PPT

1、deepseek生成大纲内容 访问deepseek官方网站&#xff1a;https://www.deepseek.com/ 将你想要编写的PPT内容输入到对话框&#xff0c;点击【蓝色】发送按钮&#xff0c;让deepseek生成内容大纲&#xff0c;并以markdown形式输出。 等待deepseek生成内容完毕后&#xff0c…...

mybatis 是否支持延迟加载?延迟加载的原理是什么?

1. MyBatis 是否支持延迟加载&#xff1f; 是的&#xff0c;MyBatis 支持延迟加载。延迟加载的主要功能是推迟数据加载的时机&#xff0c;直到真正需要时再去加载。这种方式能提高性能&#xff0c;尤其是在处理关系型数据时&#xff0c;可以避免不必要的数据库查询。 具体来说…...

【Android开发】安卓手机APP拍照并使用机器学习进行OCR文字识别

前言:点击手机APP上的拍照后,调取手机设备相机拍照并获取图片显示到手机APP页面,进行提取照片内的文字,并将识别结果显示在界面上,在离线模式下也可用。文末工程链接下载 演示视频: 目录 1.新建java项目 2.添加依赖 3. MainActivity.java文件 4.activity_main.xml 文…...

力扣 15.三数之和

题目&#xff1a; 给你一个整数数组 nums &#xff0c;判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k&#xff0c;同时还满足 nums[i] nums[j] nums[k] 0 。请你返回所有和为 0 且不重复的三元组。 注意&#xff1a;答案中不可以包含重复的…...

机器学习:二分类和多分类

1. 二分类(Binary Classification) 定义 二分类是指将输入样本分成两个互斥的类别。例如: 邮件 spam 或不是 spam。病人是有病或健康。物品是正品或假货。实现方法 二分类任务可以通过多种算法实现,包括: 逻辑回归(Logistic Regression):通过sigmoid函数将输出值映射…...

安科瑞光伏发电防逆流解决方案——守护电网安全,提升能源效率

安科瑞 华楠 18706163979 在当今大力发展清洁能源的时代背景下&#xff0c;光伏发电作为一种可持续的能源解决方案&#xff0c; 正得到越来越广泛的应用。然而&#xff0c;光伏发电过程中出现的逆流问题&#xff0c;给电网的安全稳定 运行带来了诸多挑战。若不能有效解决&…...

ml5.js框架实现AI图片识别

ml5.js ml5.js 提供了简单的接口来加载和使用机器学习模型&#xff0c;如图像分类、文本生成、姿态估计等&#xff0c;不需要深入理解底层的数学原理或复杂的编程技巧 ml5.js 构建在 TensorFlow.js 之上&#xff0c;提供了一系列预训练模型和简易的 API 接口 图片识别 先进行一…...

HDFS应用-后端存储cephfs-文件存储和对象存储数据双向迁移

DistCp&#xff08;分布式拷贝&#xff09;是用于大规模集群内部和集群之间拷贝的工具。 它使用Map/Reduce实现文件分发&#xff0c;错误处理和恢复&#xff0c;以及报告生成。 它把文件和目录的列表作为map任务的输入&#xff0c;每个任务会完成源列表中部分文件的拷贝 配置/…...

关于atomic 是否是线程安全的问题

在 Objective - C 里&#xff0c;atomic 特性并不能保证对象是完全线程安全的&#xff0c;下面从其基本原理、部分线程安全场景以及局限性来详细说明&#xff1a; 先看一个例子 #import <Foundation/Foundation.h>interface MyClass : NSObject property (atomic, assi…...

在实体机和wsl2中安装docker、使用GPU

正常使用docker和gpu&#xff0c;直接命令行安装dcoker和&#xff0c;nvidia-container-toolkit。区别在于&#xff0c;后者在于安装驱动已经cuda加速时存在系统上的差异。 1、安装gpu驱动 在实体机中&#xff0c;安装cuda加速包&#xff0c;我们直接安装 driver 和 cuda 即可…...

HTTP3.0:QUIC协议详解

文章目录 HTTP3.0:QUIC协议详解QUIC是什么QUIC为什么这么快**连接建立快&#xff1a;一见钟情型协议****拥抱UDP&#xff1a;轻装上阵****多路复用&#xff1a;一条路走到黑****更智能的丢包处理****内置加密****网络切换无压力****拥塞控制更智能** QUIC的应用场景QUIC未来会取…...

【EXCEL】【VBA】处理GI Log获得Surf格式的CONTOUR DATA

【EXCEL】【VBA】处理GI Log获得Surf格式的CONTOUR DATA data source1: BH coordination tabledata source2:BH layer tableprocess 1:Collect BH List To Layer Tableprocess 2:match Reduced Level from "Layer"+"BH"data source1: BH coordination…...

【数据处理】使用python收集网络数据--爬虫基础

我们经常需要获取大量的网络数据用于分析&#xff0c;靠人工获取效率太低&#xff0c;所以用代码获取成为大多数人的主要选择&#xff0c;这里简单介绍下使用python进行网络数据爬取的方法 数据获取 由于我们没有各个平台的内部数据和接口&#xff0c;要想获取数据只能从网页…...

华为云AI开发平台ModelArts

华为云ModelArts&#xff1a;重塑AI开发流程的“智能引擎”与“创新加速器”&#xff01; 在人工智能浪潮席卷全球的2025年&#xff0c;企业拥抱AI的意愿空前高涨&#xff0c;但技术门槛高、流程复杂、资源投入巨大的现实&#xff0c;却让许多创新构想止步于实验室。数据科学家…...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)

说明&#xff1a; 想象一下&#xff0c;你正在用eNSP搭建一个虚拟的网络世界&#xff0c;里面有虚拟的路由器、交换机、电脑&#xff08;PC&#xff09;等等。这些设备都在你的电脑里面“运行”&#xff0c;它们之间可以互相通信&#xff0c;就像一个封闭的小王国。 但是&#…...

【Python】 -- 趣味代码 - 小恐龙游戏

文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

基于数字孪生的水厂可视化平台建设:架构与实践

分享大纲&#xff1a; 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年&#xff0c;数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段&#xff0c;基于数字孪生的水厂可视化平台的…...

python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)

更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...

OpenLayers 分屏对比(地图联动)

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能&#xff0c;和卷帘图层不一样的是&#xff0c;分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝

目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为&#xff1a;一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...

并发编程 - go版

1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程&#xff0c;系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...

代码规范和架构【立芯理论一】(2025.06.08)

1、代码规范的目标 代码简洁精炼、美观&#xff0c;可持续性好高效率高复用&#xff0c;可移植性好高内聚&#xff0c;低耦合没有冗余规范性&#xff0c;代码有规可循&#xff0c;可以看出自己当时的思考过程特殊排版&#xff0c;特殊语法&#xff0c;特殊指令&#xff0c;必须…...

android RelativeLayout布局

<?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match_parent"android:gravity&…...