【数论】试除法判断质数,分解质因数,筛质数
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,这里是Ppeua。平时主要更新C语言,C,数据结构算法......感兴趣就关注我吧!你定不会失望。 🌈个人主页:主页链接 🌈算法专栏:专栏链接 现已更新完KMP算法、排序模板,之…...
【C++】红黑树
文章目录红黑树的概念红黑树的性质特征红黑树结点的定义红黑树的插入操作情况1情况2情况3特殊情况代码实现红黑树的验证红黑树的删除红黑树和AVL树的比较红黑树的应用红黑树的概念 红黑树,是一种二叉搜索树,但是每一个结点都增加一个存储位表示结点的颜…...
【剧前爆米花--爪哇岛寻宝】进程的调度以及并发和并行,以及PCB中属性的详解。
作者:困了电视剧 专栏:《JavaEE初阶》 文章分布:这是关于进程调度、并发并行以及相关属性详解的文章,我会在之后文章中更新有关线程的相关知识,并将其与进程进行对比,希望对你有所帮助。 目录 什么是进程/…...
网络的瓶颈效应
python从小白到总裁完整教程目录:https://blog.csdn.net/weixin_67859959/article/details/129328397?spm1001.2014.3001.5501 ❤ 网络的瓶颈效应 网络瓶颈,指的是影响网络传输性能及稳定性的一些相关因素,如网络拓扑结构,网线࿰…...
【C++进阶】四、红黑树(三)
目录 一、红黑树的概念 二、红黑树的性质 三、红黑树节点的定义 四、红黑树的插入 五、红黑树的验证 六、红黑树与AVL树的比较 七、完整代码 一、红黑树的概念 红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可…...
Spring——AOP切入点表达式和AOP通知类型
切入点:要进行增强的方法 切入点表达式:要进行增强的方法的描述式 第一种方法的本质是基于接口实现的动态代理(jdk) 第二种是基于cglib实现的动态代理 AOP切入点表达式 而需要加载多个切入点时,不可能每个切入点都写一个切入点表达式 例子 下面的代理描述的是匹配…...
Hadoop学习:Yarn
1.YARN介绍 一个通用的资源管理系统和调度平台 YARN不分配磁盘,由HDFS分配 相当于一个分布式的操作系统平台,为上层MR等计算程序提供运算所需要的资源(内存、CPU等) 2.YARN三大组件 不要忘记AppMaster,他是程序内部…...
Spring Data JPA
文章目录一、Spring Data基础概念二、JPA与JDBC的相同与不同之处三、Hibernate & JPA快速搭建1.添加依赖2.实体类3.hibernate的配置文件 ——hibernate.cfg.xml四、测试——基于hibernate的持久化(单独使用)五、测试——基于JPA的持久化(…...
java List报错Method threw ‘java.lang.UnsupportedOperationException‘ exception. 解决
问题描述:List使用Arrays.asList()初始化后,再add对象时报错:Method threw java.lang.UnsupportedOperationException exception.错误示例如下: List<ExportListVO.ExportSheet> sheetVOList Arrays.asList(new ExportList…...
数据结构-用栈实现队列
前言: 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty): 实现 MyQueue 类: void push(int x) 将元素 x 推到队列的末尾 int pop() 从队列的开头移除并返回元素 int…...
第十四章 从 Windows 客户端控制 IRIS
文章目录第十四章 从 Windows 客户端控制 IRISIRISctlGetDirsSyntaxReturn ValuesIRISctlConfigStatusSyntaxReturn ValuesIRISctlControlSyntaxReturn Values第十四章 从 Windows 客户端控制 IRIS IRIS 为 Windows 客户端程序提供了一种机制来控制 IRIS 配置并启动 IRIS 进程…...
数据结构---双链表
专栏:数据结构 个人主页:HaiFan. 专栏简介:从零开始,数据结构!! 双链表前言双链表各接口的实现为要插入的值开辟一块空间BuyLN初始化LNInit和销毁LNDestory打印链表中的值LNPrint尾插LNPushBack和尾删LNPop…...
Windows 环境安装Scala详情
为了进一步学习Spark,必须先学习Scala 编程语言。首先开始Scala 环境搭建。温馨提示:本文是基于Windows 11 安装Scala 2.13.1 版本第一步:确保本机已经正确安装JDK1.8 环境第二步:Scala 官网下载我们所属scala版本文件。Scala 官网…...
C++ Qt自建网页浏览器
C Qt自建网页浏览器如需安装运行环境或远程调试,见文章底部个人QQ名片,由专业技术人员远程协助!前言这篇博客针对<<C Qt自建网页浏览器>>编写代码,代码整洁,规则,易读。 学习与应用推荐首选。文…...
Flink从入门到精通系列(四)
5、DataStream API(基础篇) Flink 有非常灵活的分层 API 设计,其中的核心层就是 DataStream/DataSet API。由于新版本已经实现了流批一体,DataSet API 将被弃用,官方推荐统一使用 DataStream API 处理流数据和批数据。…...
Nginx 配置实例-反向代理案例一
实现效果:使用nginx反向代理,访问 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…...
为什么北欧的顶级程序员数量远超中国?
说起北欧,很多人会想到寒冷的冬天,漫长的极夜,童话王国和圣诞老人,但是如果我罗列下诞生于北欧的计算机技术,恐怕你会惊掉下巴。Linux:世界上最流行的开源操作系统,最早的内核由Linus Torvalds开…...
vuex getters的作用和使用(求平均年龄),以及辅助函数mapGetters
getters作用:派生状态数据mapGetters作用:映射getters中的数据使用:方法名自定义,系统自动注入参数:state,每一个方法中必须有return,其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 第一次运行出现如下的警告: Fresh drivers from upstream, currently shipping Nvidia. ## Curren…...
2023腾讯面试真题:
【腾讯】面试真题: 1、Kafka 是什么?主要应用场景有哪些? Kafka 是一个分布式流式处理平台。这到底是什么意思呢? 流平台具有三个关键功能: 消息队列:发布和订阅消息流,这个功能类似于消息…...
深度学习在微纳光子学中的应用
深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向: 逆向设计 通过神经网络快速预测微纳结构的光学响应,替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...
深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录
ASP.NET Core 是一个跨平台的开源框架,用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录,以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...
【JavaEE】-- HTTP
1. HTTP是什么? HTTP(全称为"超文本传输协议")是一种应用非常广泛的应用层协议,HTTP是基于TCP协议的一种应用层协议。 应用层协议:是计算机网络协议栈中最高层的协议,它定义了运行在不同主机上…...
练习(含atoi的模拟实现,自定义类型等练习)
一、结构体大小的计算及位段 (结构体大小计算及位段 详解请看:自定义类型:结构体进阶-CSDN博客) 1.在32位系统环境,编译选项为4字节对齐,那么sizeof(A)和sizeof(B)是多少? #pragma pack(4)st…...
iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版分享
平时用 iPhone 的时候,难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵,或者买了二手 iPhone 却被原来的 iCloud 账号锁住,这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...
macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用
文章目录 问题现象问题原因解决办法 问题现象 macOS启动台(Launchpad)多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显,都是Google家的办公全家桶。这些应用并不是通过独立安装的…...
基于数字孪生的水厂可视化平台建设:架构与实践
分享大纲: 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年,数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段,基于数字孪生的水厂可视化平台的…...
Psychopy音频的使用
Psychopy音频的使用 本文主要解决以下问题: 指定音频引擎与设备;播放音频文件 本文所使用的环境: Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...
NFT模式:数字资产确权与链游经济系统构建
NFT模式:数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新:构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议:基于LayerZero协议实现以太坊、Solana等公链资产互通,通过零知…...
Razor编程中@Html的方法使用大全
文章目录 1. 基础HTML辅助方法1.1 Html.ActionLink()1.2 Html.RouteLink()1.3 Html.Display() / Html.DisplayFor()1.4 Html.Editor() / Html.EditorFor()1.5 Html.Label() / Html.LabelFor()1.6 Html.TextBox() / Html.TextBoxFor() 2. 表单相关辅助方法2.1 Html.BeginForm() …...



