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

【数论】试除法判断质数,分解质因数,筛质数

Halo,这里是Ppeua。平时主要更新C语言,C++,数据结构算法......感兴趣就关注我吧!你定不会失望。

 

🌈个人主页:主页链接

🌈算法专栏:专栏链接

     现已更新完KMP算法、排序模板,之后我会继续往里填充内容哒。

🌈LeetCode专栏:专栏链接 

    目前在刷初级算法的LeetBook 。若每日一题当中有力所能及的题目,也会当天做完发出

🌈代码仓库:Gitee链接

🌈点击关注=收获更多优质内容🌈

用一篇Blog来讲解下最近学到的数论,为日后的刷题打下坚实的基础。

目录

试除法判断质数:

朴素做法:

代码模板:

改进做法:

 代码模板:

分解质因数:

 代码模板:

筛质数:

 埃式筛法:

欧拉筛(线性筛):

完结撒花:


什么是质数?

一个大于1的自然数,除了1和它自身外,不能被其他自然数整除的数

试除法判断质数:

朴素做法:

将定义进行模拟,若整除了除1与其自身的另外的数,则为质数

代码模板:

#include<iostream>
using namespace std;
int n;
void prime(int x)
{if(x<2){cout<<"No"<<endl;return;}for(int i=2;i<=x;i++){if(x%i==0){cout<<"No"<<endl;return ;}}cout<<"Yes"<<endl;return;
}
int main()
{cin>>n;while(n--){int x;cin>>x;prime(x);}
}

改进做法:

一个数的两个因数都是成对出现的,例如:6的因数为 1 2 3 6 

这里的2与3是成对出现的。所以我们无需从2-x的范围去遍历,因为若前半部分没有出现,则后半部分必然没有其因数

通过反证法:若后半部分有其因数,则就会出现这两个因数相乘会大于其本身。

所以应该满足 i*i<=x的范围,但又因为i*i在数字极大的情况下,很容易溢出,所以改成i<=x/i

 代码模板:

#include<iostream>
using namespace std;
int n;
void prime(int x)
{if(x<2){cout<<"No"<<endl;return;}for(int i=2;i<=x/i;i++){if(x%i==0){cout<<"No"<<endl;return ;}}cout<<"Yes"<<endl;return;
}
int main()
{cin>>n;while(n--){int x;cin>>x;prime(x);}
}

分解质因数:

 

与上文相同,依然是用到了i*i<=n的这个性质,需要注意一下,最多存在一个>=sqrt(n)的质因子,同样可以用反证法来证明,这里就不过多赘述.所以当最后跳出循环时若还存在x>1,也就是没有被模掉的情况时,则认为x为其较大的那个因子,也需要放进去.

若一个数能整除i,则i是其一个因子,又因为我们从小到达进行遍历,被整除的这个i必然为质因子,因为若为普通因子,在循环整除的时候已经被消掉了,化为其指数.

 代码模板:

#include<iostream>
using namespace std;
void divide(int x)
{for(int i=2;i<=x/i;i++)if(x%i==0){int s=0;while(x%i==0){x/=i;s++;}printf("%d %d\n",i,s);}if(x>1)printf("%d %d\n",x,1);puts("");return ;
}
int main()
{int n=0;cin>>n;while(n--){int x;cin>>x;divide(x);}return 0;
}

筛质数:

 

 埃式筛法:

一个约数其必然可以由数相乘得到.

假设有如下2到10的数

埃式筛法的核心就是:从头遍历每个数字,将其与每一个小于本身它本身的质数相乘,再将之后的数标记为非质数

也就是这样

 可以看出 这里的质数就为2 3 5 7,

但我们很快就会发现,这个算法有一个弊端,假设这里的范围到12,就会出现当4*3的时候把十二标记为false了,但6*2又会将其标记一次,十分的不优雅.

所以就提出了另一个改进的算法

欧拉筛(线性筛):

当发现相乘的这个质数为其最小质因子时,则停止遍历

#include<iostream>
using namespace std;
const int N=1e6+9;
bool st[N];
int prime[N];
int main()
{int n=0;int cnt=0;cin>>n;for(int i=2;i<=n;i++){if(!st[i]){prime[cnt++]=i;}for(int j=0;prime[j]<=n/i;j++){st[prime[j]*i]=true;if(i%prime[j]==0)break;}}cout<<cnt;
}

完结撒花:

🌈本篇博客的内容【数论:试除法判断质数,分解质因数,筛质数】已经结束。

🌈若对你有些许帮助,可以点赞、关注、评论支持下博主,你的支持将是我前进路上最大的动力。

🌈若以上内容有任何问题,欢迎在评论区指出。若对以上内容有任何不解,都可私信评论询问。

🌈诸君,山顶见!

相关文章:

【数论】试除法判断质数,分解质因数,筛质数

Halo&#xff0c;这里是Ppeua。平时主要更新C语言&#xff0c;C&#xff0c;数据结构算法......感兴趣就关注我吧&#xff01;你定不会失望。 &#x1f308;个人主页&#xff1a;主页链接 &#x1f308;算法专栏&#xff1a;专栏链接 现已更新完KMP算法、排序模板&#xff0c;之…...

【C++】红黑树

文章目录红黑树的概念红黑树的性质特征红黑树结点的定义红黑树的插入操作情况1情况2情况3特殊情况代码实现红黑树的验证红黑树的删除红黑树和AVL树的比较红黑树的应用红黑树的概念 红黑树&#xff0c;是一种二叉搜索树&#xff0c;但是每一个结点都增加一个存储位表示结点的颜…...

【剧前爆米花--爪哇岛寻宝】进程的调度以及并发和并行,以及PCB中属性的详解。

作者&#xff1a;困了电视剧 专栏&#xff1a;《JavaEE初阶》 文章分布&#xff1a;这是关于进程调度、并发并行以及相关属性详解的文章&#xff0c;我会在之后文章中更新有关线程的相关知识&#xff0c;并将其与进程进行对比&#xff0c;希望对你有所帮助。 目录 什么是进程/…...

网络的瓶颈效应

python从小白到总裁完整教程目录:https://blog.csdn.net/weixin_67859959/article/details/129328397?spm1001.2014.3001.5501 ❤ 网络的瓶颈效应 网络瓶颈&#xff0c;指的是影响网络传输性能及稳定性的一些相关因素&#xff0c;如网络拓扑结构&#xff0c;网线&#xff0…...

【C++进阶】四、红黑树(三)

目录 一、红黑树的概念 二、红黑树的性质 三、红黑树节点的定义 四、红黑树的插入 五、红黑树的验证 六、红黑树与AVL树的比较 七、完整代码 一、红黑树的概念 红黑树&#xff0c;是一种二叉搜索树&#xff0c;但在每个结点上增加一个存储位表示结点的颜色&#xff0c;可…...

Spring——AOP切入点表达式和AOP通知类型

切入点:要进行增强的方法 切入点表达式:要进行增强的方法的描述式 第一种方法的本质是基于接口实现的动态代理(jdk) 第二种是基于cglib实现的动态代理 AOP切入点表达式 而需要加载多个切入点时&#xff0c;不可能每个切入点都写一个切入点表达式 例子 下面的代理描述的是匹配…...

Hadoop学习:Yarn

1.YARN介绍 一个通用的资源管理系统和调度平台 YARN不分配磁盘&#xff0c;由HDFS分配 相当于一个分布式的操作系统平台&#xff0c;为上层MR等计算程序提供运算所需要的资源&#xff08;内存、CPU等&#xff09; 2.YARN三大组件 不要忘记AppMaster&#xff0c;他是程序内部…...

Spring Data JPA

文章目录一、Spring Data基础概念二、JPA与JDBC的相同与不同之处三、Hibernate & JPA快速搭建1.添加依赖2.实体类3.hibernate的配置文件 ——hibernate.cfg.xml四、测试——基于hibernate的持久化&#xff08;单独使用&#xff09;五、测试——基于JPA的持久化&#xff08;…...

java List报错Method threw ‘java.lang.UnsupportedOperationException‘ exception. 解决

问题描述&#xff1a;List使用Arrays.asList()初始化后&#xff0c;再add对象时报错&#xff1a;Method threw java.lang.UnsupportedOperationException exception.错误示例如下&#xff1a; List<ExportListVO.ExportSheet> sheetVOList Arrays.asList(new ExportList…...

数据结构-用栈实现队列

前言&#xff1a; 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作&#xff08;push、pop、peek、empty&#xff09;&#xff1a; 实现 MyQueue 类&#xff1a; void push(int x) 将元素 x 推到队列的末尾 int pop() 从队列的开头移除并返回元素 int…...

第十四章 从 Windows 客户端控制 IRIS

文章目录第十四章 从 Windows 客户端控制 IRISIRISctlGetDirsSyntaxReturn ValuesIRISctlConfigStatusSyntaxReturn ValuesIRISctlControlSyntaxReturn Values第十四章 从 Windows 客户端控制 IRIS IRIS 为 Windows 客户端程序提供了一种机制来控制 IRIS 配置并启动 IRIS 进程…...

数据结构---双链表

专栏&#xff1a;数据结构 个人主页&#xff1a;HaiFan. 专栏简介&#xff1a;从零开始&#xff0c;数据结构&#xff01;&#xff01; 双链表前言双链表各接口的实现为要插入的值开辟一块空间BuyLN初始化LNInit和销毁LNDestory打印链表中的值LNPrint尾插LNPushBack和尾删LNPop…...

Windows 环境安装Scala详情

为了进一步学习Spark&#xff0c;必须先学习Scala 编程语言。首先开始Scala 环境搭建。温馨提示&#xff1a;本文是基于Windows 11 安装Scala 2.13.1 版本第一步&#xff1a;确保本机已经正确安装JDK1.8 环境第二步&#xff1a;Scala 官网下载我们所属scala版本文件。Scala 官网…...

C++ Qt自建网页浏览器

C Qt自建网页浏览器如需安装运行环境或远程调试&#xff0c;见文章底部个人QQ名片&#xff0c;由专业技术人员远程协助&#xff01;前言这篇博客针对<<C Qt自建网页浏览器>>编写代码&#xff0c;代码整洁&#xff0c;规则&#xff0c;易读。 学习与应用推荐首选。文…...

Flink从入门到精通系列(四)

5、DataStream API&#xff08;基础篇&#xff09; Flink 有非常灵活的分层 API 设计&#xff0c;其中的核心层就是 DataStream/DataSet API。由于新版本已经实现了流批一体&#xff0c;DataSet API 将被弃用&#xff0c;官方推荐统一使用 DataStream API 处理流数据和批数据。…...

Nginx 配置实例-反向代理案例一

实现效果&#xff1a;使用nginx反向代理&#xff0c;访问 www.suke.com 直接跳转到本机地址127.0.0.1:8080 一、准备工作 Centos7 安装 Nginxhttps://liush.blog.csdn.net/article/details/125027693 1. 启动一个 tomcat Centos7安装JDK1.8https://liush.blog.csdn.net/arti…...

为什么北欧的顶级程序员数量远超中国?

说起北欧&#xff0c;很多人会想到寒冷的冬天&#xff0c;漫长的极夜&#xff0c;童话王国和圣诞老人&#xff0c;但是如果我罗列下诞生于北欧的计算机技术&#xff0c;恐怕你会惊掉下巴。Linux&#xff1a;世界上最流行的开源操作系统&#xff0c;最早的内核由Linus Torvalds开…...

vuex getters的作用和使用(求平均年龄),以及辅助函数mapGetters

getters作用&#xff1a;派生状态数据mapGetters作用&#xff1a;映射getters中的数据使用&#xff1a;方法名自定义&#xff0c;系统自动注入参数&#xff1a;state&#xff0c;每一个方法中必须有return&#xff0c;其return的结果被该方法名所接收。在state中声明数据listst…...

20230311给Ubuntu18.04下的GTX1080M安装驱动

20230311给Ubuntu18.04下的GTX1080M安装驱动 2023/3/11 12:50 2. 安装GTX1080驱动 安装 Nvidia 驱动 367.27 sudo add-apt-repository ppa:graphics-drivers/ppa 第一次运行出现如下的警告&#xff1a; Fresh drivers from upstream, currently shipping Nvidia. ## Curren…...

2023腾讯面试真题:

​【腾讯】面试真题&#xff1a; 1、Kafka 是什么&#xff1f;主要应用场景有哪些&#xff1f; Kafka 是一个分布式流式处理平台。这到底是什么意思呢&#xff1f; 流平台具有三个关键功能&#xff1a; 消息队列&#xff1a;发布和订阅消息流&#xff0c;这个功能类似于消息…...

Debian系统简介

目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版&#xff…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

Matlab | matlab常用命令总结

常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

基于IDIG-GAN的小样本电机轴承故障诊断

目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) ​梯度归一化(Gradient Normalization)​​ (2) ​判别器梯度间隙正则化(Discriminator Gradient Gap Regularization)​​ (3) ​自注意力机制(Self-Attention)​​ 3. 完整损失函数 二…...

深度剖析 DeepSeek 开源模型部署与应用:策略、权衡与未来走向

在人工智能技术呈指数级发展的当下&#xff0c;大模型已然成为推动各行业变革的核心驱动力。DeepSeek 开源模型以其卓越的性能和灵活的开源特性&#xff0c;吸引了众多企业与开发者的目光。如何高效且合理地部署与运用 DeepSeek 模型&#xff0c;成为释放其巨大潜力的关键所在&…...

Linux 下 DMA 内存映射浅析

序 系统 I/O 设备驱动程序通常调用其特定子系统的接口为 DMA 分配内存&#xff0c;但最终会调到 DMA 子系统的dma_alloc_coherent()/dma_alloc_attrs() 等接口。 关于 dma_alloc_coherent 接口详细的代码讲解、调用流程&#xff0c;可以参考这篇文章&#xff0c;我觉得写的非常…...