首页 > 其他分享 >质数基础筛法

质数基础筛法

时间:2024-02-08 13:33:22浏览次数:24  
标签:埃氏 筛法 rep int 质数 基础 vis 线性 复杂度

目录

埃氏筛

埃氏筛是一种筛素数的方法,埃氏筛的思想很重要,主要是时间复杂度

朴素的埃氏筛的时间复杂度是\(O(nlogn)\)
这个复杂度是调和级数

vector<int>p;
int vis[N];

void solve()
{
	rep(i,2,n){
		if(!vis[i])	p.pb(i);
		for(int j=i+i;j<=n;j+=i)	vis[j]=1;		
	}
}

优化的埃氏筛的时间复杂度O(nloglogn)是很小的,基本上已经接近线性了


int vector<int>p;
vis[N];

void solve()
{
	rep(i,2,n){
		if(!vis[i])	p.pb(i);
		for(int j=i+i;j<=n;j+=i)	vis[j]=1;		
	}
}

线性筛

线性筛的时间复杂度之所以是线性,是因为每个数只会被它的最小素因子筛一次。
image

vector<int>p;
int vis[N];

void solve()
{
	rep(i,2,n){
		if(!vis[i])	p.pb(i);
		for(int j=0;p[j]*i<=n;++j){
			vis[p[j]*i]=1;
			if(i%p[j]==0)	break;
		}	
	}
}

标签:埃氏,筛法,rep,int,质数,基础,vis,线性,复杂度
From: https://www.cnblogs.com/cxy8/p/18011717

相关文章

  • 1,信息技术基础---软件技术
    1,信息技术基础---软件技术面向对象的基本概念包括对象、类、抽象、封装、继承、多态、接口、消息、组件、复用和模式等。对象:由数据及操作所构成的封装体,是系统中用来描述客观事物的一个模块,是构成系统的基本单位。对象包含三个基本要素,分别是对象标识、对象状态和对象行为。类......
  • redis基础知识梳理
    性能测试工具redis-benchmark-hhost-pport-cconnections-nrequests-hhost:指定Redis服务器的主机名或IP地址。-pport:指定Redis服务器的端口号。-cconnections:指定并发连接数,即同时向服务器发起的连接数量。-nrequests:指定总的请求数量,即测试期间每个连接向服务......
  • linux基础
    flutter安装直接通过克隆官方仓库安装是最舒服的gitclone-bdevhttps://github.com/flutter/flutter.gitflatpak卸载软件flatpaklistflatpakuninstallapp_idflatpakuninstall--unused相关概念在这里有时候并不严格区分目录和文件。物理磁盘:/dev/sd--虚拟磁盘:/de......
  • Redis基础命令集
    一、基础命令1、ping(心跳命令)若看到PONG响应,则说明客户端与Redis的连接时正常的。2、select(切换数据库)redis默认有16个数据库,默认使用的是0号DB。3、dbsize(查看key数量)查看当前数据库中key的数量。4、flushdb(删除当前库中所有数据)清楚当前DB中的所有数据,不影响其他DB......
  • 学习 Redis 基础数据结构,不讲虚的。
    学习Redis基础数据结构,不讲虚的。一个群友给我发消息,“该学的都学了,怎么就找不到心意的工作,太难了”。很多在近期找过工作的同学一定都知道了,背诵八股文已经不是找工作的绝对王牌。企业最终要的是可以创造价值,或者首先需要干活的人,所以实战很重要。今天这篇文章就是给大家分享......
  • 【视频】小甲鱼零基础入门学习Python(全96集)
    视频下载地址:https://pan.quark.cn/s/c17e3da33a76目录1.第一讲:我和Python的第一次亲密接触2.第二讲:用Python设计第一个游戏3.第三讲:小插曲之变量和字符串4.第四讲:改进我们的小游戏5.第五讲:Python的数据类型6.第六讲:常用的操作符7.第七-九讲:了不起的分支和循环8.第十讲:一个......
  • UGUI 基础控件
    基础控件ImageSourceImage:图片来源(图片类型必须是“精灵”类型)Color:图像的颜色Material:图像的材质(一般不修改,会使用UI的默认材质)RaycastTarget:是否作为射线检测的目标(如果不勾选将不会影响射线检测)Maskable:是否能被遮罩ImageType:图片类型Simple:普......
  • 【转帖】基础软件开发 -- 神秘的MESI和坑爹的LockFree
    https://zhuanlan.zhihu.com/p/681321783 又开新坑,继续掰扯基础软件开发。这里已经更新到第二季了,欲先睹为快的可以到这里:基础软件开发新坑--神秘的MESI和坑爹的LockFree(一)基础软件开发新坑--神秘的MESI和坑爹的LockFree(二)正文开始:在《HPC(高性能计算第一篇):一文......
  • 高级FPGA开发之基础协议之PCIe(二)
    高级FPGA开发之基础协议之PCIe(二)一、TLP报文类型在PCIe总线中,存储器读写、I/O读写和配置读写请求TLP主要由以下几类报文组成:1.1存储器读请求TLP和读完成TLP当PCIe主设备(RC或者EP)访问目标设备的存储器空间时,使用non-posted总线事务向目标设备发出存储器读请求TLP,目标设备收到这个存......
  • 【Java核心基础】揭秘Iterable接口和Iterator接口的核心区别!
    在Java中,Iterable接口和Iterator接口都用于遍历集合(Collection)中的元素,但它们的使用方式和功能有所不同。官方文档传送门:https://docx.iamqiang.com/jdk11/api/java.base/java/lang/Iterable.htmlhttps://docx.iamqiang.com/jdk11/api/java.base/java/util/Iterator.html核心......