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

【算法每日一练]-数论(保姆级教程 篇1 埃氏筛,欧拉筛)

目录

保证给你讲透讲懂

第一种:埃氏筛法

第二种:欧拉筛法

 题目:质数率

题目:不喜欢的数

思路:


        

        

        
问题:1~n 中筛选出所有素数(质数)

有两种经典的时间复杂度较低的筛法,即埃氏筛法和欧拉筛法。

既然是筛子,那么核心思想就是:根据当前的数筛掉后面的一些不合法数据,留下的每个数都是质数。    

第一种:埃氏筛法

(也是最好理解的筛子,不过速度O(n*loglogn))

        

首先2是最小的素数,将表中所有的2的倍数划去。

表中剩下的最小的数字就是3,所以3是素数。再将表中所有的3的倍数划去……

以此类推,如果表中剩余的最小的数是几,几就是素数。然后将其倍数筛掉

核心代码: 

第二个for为什么从i*i开始:

答:我们会先筛2的所有倍数,然后是3的倍数,但是后面在筛3的倍数的时候我们还需要从2开始筛吗?筛掉3*2?这个之前在筛2的时候就已经标记过了的,那么直接从3本身筛开始多好啊。

int eprime(int n){judge[0]=judge[1]=1;for(int i=2;i<=n;i++){if(judge[i]==0){prime[cnt++]=i;for(int j=i*i;j<=n;j+=i) judge[j]=1;//直接从i本身开始筛}}return cnt;
}

重点: 虽然埃氏筛易理解,但是个别时候还是会被卡的。

我们深入理解埃氏筛的思想:

要想得到 n以内的质数,就要把不大于根号n的质数的倍数全部剔除,剩下的就是质数。从 2 开始,把 2 的倍数(不包括本身)标记为合数,然后向后枚举,查到一个未标记为合数的,就把它的倍数(不包括本身)标记为合数。以此类推,查到 n 为止。
例如一个数 24,它会被 2 标记一次,被3标记一次。如果这个数的质因数较多,那么重复的就会更多,每个已经被筛掉的数重复的被筛,这就会导致时间变长

        (放心,欧拉来了) 

第二种:欧拉筛法

欧拉筛法的原理同埃氏筛法,只不过多了一个判断删除与标记最小质因子的过程。

在埃氏筛法中,一个合数来说可能会被筛多次,比如6可以被2筛去,也可以被3筛去,而欧拉筛要做的事情就是让一个合数只被筛一次。

我们规定这个合数只会被它的最小质因数筛掉。这样能保证每个合数只会被筛一次。

核心代码 

int oprime(int n){//线性筛O(n)速度求出小于n的所有质数!!!judge[0]=judge[1]=1;for(int i=2;i<=n;i++){if(!judge[i]) prime[cnt++]=i;//没有被标记过的数必然是质数,加入质数中for(int j=0;prime[j]*i<=n;j++){//质数性倍增(只枚举当然已放入的质数)judge[prime[j]*i]=true;//此数的质数倍数加入标记中if(i%prime[j]==0)break;//保证了一个合数只被它最小的质因子枚举标记,而一个质数只会一直枚举标记到本身}}return cnt;
}

过程如下:

从 2开始:2 加入 prime 数组,从小到大枚举质数(现在只有 2),筛掉质数与 2 的乘积(4 被筛掉)。
到了 3:   3 加入 prime 数组,从小到大枚举质数(此时有 2,3),筛掉质数与 3 的乘积(6,9 被筛掉)。

到了 4:   4 没加入 prime 数组,枚举质数(有2,3),筛掉 8 后,因为 4mod2=0,触发退出条件。(不触发,就会筛掉 12,而 12=2×2×3,又会被 2 和 6筛一次,懂了吗)
以此类推,可做出一张表:

不难发现保证一个合数只被它最小的质因子枚举标记,而一个质数只会一直枚举标记到本身。保证了合数只被一次筛掉。

下面是完整代码:

#include <bits/stdc++.h>//线性筛模板
using namespace std;
bool judge[1000000];
int n,cnt,prime[1000];
int oprime(int n){//线性筛O(n)速度求出小于n的所有质数!!!judge[0]=judge[1]=1;for(int i=2;i<=n;i++){if(!judge[i]) prime[cnt++]=i;//没有被标记过的数加入质数中for(int j=0;prime[j]*i<=n;j++){//1,质数性倍增(只枚举当然已放入的质数)judge[prime[j]*i]=true;//此数的质数倍数加入标记中(必然不是质数)if(i%prime[j]==0)break;//2,保证一个合数只被它最小的质因子枚举标记,而一个质数只会一直枚举标记到本身}}return cnt;
}
int eprime(int n){judge[0]=judge[1]=1;for(int i=2;i<=n;i++){if(judge[i]==0){prime[cnt++]=i;for(int j=i*i;j<=n;j+=i) judge[j]=1;}}return cnt;
}
int main(){cin>>n;eprime(n);//oprime(n);for(int i=0;i<cnt;i++){cout<<prime[i]<<' ';}return 0;
}

以上算法只有两步(已标出)和埃氏筛不同,注意一下即可 

最终效果:zhi数组里面全是质数,vis数组里面为true的都不是质数,既方便取质数,又方便判断质数。

        

        下面是练习题

 题目:质数率

题意:求1~n的质数占比(n<=1e8)

(这道题还是很友好的,直接让你精确,而不是求逆元,哈哈哈哈哈)

#include <bits/stdc++.h>
using namespace std;
const int N=1e8+7;
int zhi[N],cnt,m;
bool vis[N];//千万不要用int来充当bool了,内存直接超256M了!!!
int getzhi(int n){for(int i=2;i<=n;i++){if(!vis[i])zhi[cnt++]=i;    //如果你这里想用++cnt,那么后面的j应该从1开始for(int j=0;zhi[j]*i<=n;j++){vis[zhi[j]*i]=true;if(i%zhi[j]==0)break;}}return cnt;
}
int main(){cin>>m;getzhi(m);printf("%0.3lf\n",(double)cnt/m);
}

      

      

题目:不喜欢的数

我们不喜欢7的倍数;数字的某一位是7,这个数字的倍数我们也不喜欢。给t个数,如果这个数不是喜欢的数就输出下一个喜欢的数

     

思路:

  
注意到一个含7的数的倍数也不行,很明显我们倒着找的话需要找所有的因数来判断,但是t太大了,这样必然超时。只能正着来做!

     
线性筛思想O(n):如果此数喜欢,那就加入数组;否则就把此数的倍数全部筛掉

     
注意到要输出不喜欢数的下一个喜欢的数。

对于这种取一个数的后一个数,那就定义一个链表呗(就是跟踪数组嘛)里面存放下标可以,直接存放那个数也可以,感觉你直接存那个数的话更好!
    

        

#include <bits/stdc++.h>
using namespace std;//如果是喜欢的数,就输出下一个喜欢的数(大于次数的下一个喜欢的数)(t<=2e5    x<=1e7)
const int N=1e7+7;
int t,x,ans[N],nxt[N],cnt;
bool judge[N]={1};
bool check(int x){while(x){if(x%10==7)return true;x/=10;}return false;
}
void getnum(int n){//线性筛思想int cur=1;//cur是上个喜欢的数,此时是第一个喜欢的数for(int i=2;i<=n;i++){if(!judge[i]){//忽略被筛掉的数bool f=check(i);if(!f){//喜欢ans[cnt++]=i;//放入数组,感觉此步骤有点多余nxt[cur]=i;//更新链表,里面存入这个数的下个数cur=i;//更新cur}else{for(int j=i;j<=n;j+=i)//线性倍增的结果都标记一下(都是不喜欢的数)judge[j]=true;}}}
}
int main(){getnum(N);//先对所有范围内的数都打下表格cin>>t;while(t--){cin>>x;if(judge[x]) cout<<-1<<'\n';//不喜欢则直接输出-1else cout<<nxt[x]<<'\n';//喜欢则输出这个数的下一个数}return 0;
}

相关文章:

【算法每日一练]-数论(保姆级教程 篇1 埃氏筛,欧拉筛)

目录 保证给你讲透讲懂 第一种&#xff1a;埃氏筛法 第二种&#xff1a;欧拉筛法 题目&#xff1a;质数率 题目&#xff1a;不喜欢的数 思路&#xff1a; 问题&#xff1a;1~n 中筛选出所有素数&#xff08;质数&#xff09; 有两种经典的时间复杂度较低的筛法&#xff0…...

【剑指offr--C/C++】JZ59 滑动窗口的最大值

一、题目 二、思路及代码 暴力解法是依次往后滑动一位&#xff0c;然后比较窗口内的值。 我这里考虑&#xff1a;窗口每次往后移动一位&#xff0c;那么如果当前窗口的最大值max在窗口内部&#xff0c;那么再滑动到下一个窗口的时候&#xff0c;窗口内只有最新进来的一个元素没…...

RabbitMQ Tutorial

参考API : Overview (RabbitMQ Java Client 5.20.0 API) 参考文档: RabbitMQ: One broker to queue them all | RabbitMQ 目录 结构 Hello World consumer producer 创建连接API解析 创建连接工厂 生产者生产消息 消费者消费消息 队列声明 工作队列Work Queues 公平…...

如何对Webpack进行优化

目录 1.优化-提取css代码 1.1. 插件 mini-css-extract-plugin 1.2. 步骤&#xff1a; 1.3. 注意 1.4. 好处 1.5. 练习 2. 优化-css代码提取后压缩 2.1. 问题引入 2.2. 解决 2.3. 步骤 3. Webpack打包less代码 3.1. 加载器 less-loader 3.2. 步骤 3.3. 注意&#xf…...

nut-ui中的menu 菜单组件的二次封装

这个菜单组件 一般可以直接用到项目里 如果复用性不强的话 直接使用 但是有一个问题 如果很多地方都需要用到这个组件 我们可以把这个组件二次封装一下 <template><div class"cinema-search-filter-component"><nut-menu><template #icon>&…...

python笔记(11)序列

Python中的“序列”是一个广义术语&#xff0c;用于描述一种特定的数据结构&#xff0c;它具备以下共同特征&#xff1a; 有序性&#xff1a;序列中的元素按照特定的顺序排列&#xff0c;每个元素在序列中都有一个确定的位置&#xff0c;即索引。 索引访问&#xff1a;通过索引…...

Rust egui(4) 增加自己的tab页面

如下图&#xff0c;增加一个Sins也面&#xff0c;里面添加一个配置组为Sin Paraemters&#xff0c;里面包含一个nums的参数&#xff0c;范围是1-1024&#xff0c;根据nums的数量&#xff0c;在Panel中画sin函数的line。 demo见&#xff1a;https://crazyskady.github.io/index.…...

小组分享第二部分:Jsoup

1.Jsoup是什么&#xff1a; 是HTML的解析器,可以解析URL地址&#xff0c;HTML的文本内容&#xff0c;可以使用DOM,CSS以及类似Jquery的操作方法来操作数据 2.Jsoup的作用 1.通过URL或者文件或者字符串获取到HTML页面并解析 2.使用DOM或CSS等操作来对数据进行操作 3.可以操作HT…...

C#(winform) 调用MATLAB函数

测试环境 VisualStudio2022 / .NET Framework 4.7.2 Matlab2021b 参考&#xff1a;C# Matlab 相互调用 Matlab 1、编写Matlab函数 可以没有任何参数单纯定义matlab处理的函数&#xff0c;输出的数据都存在TXT中用以后期读取数据 function [result,m,n] TEST(list) % 计算…...

Kubernetes探索-Pod面试(补充)

针对上篇文章"kubernetes探索-Pod面试"做一点点补充... 1. 简述Pod的删除流程 1) kube-apiserver接收到用户的删除指令&#xff0c;默认等待30s(优雅退出时间)&#xff0c;随后认为pod已死亡&#xff0c;将其标记为Terminating状态&#xff1b; 2) kubelet监控到pod…...

深入了解JUnit 5:新一代Java单元测试框架

深入了解JUnit 5&#xff1a;新一代Java单元测试框架 近年来&#xff0c;Java领域的单元测试框架发展迅速&#xff0c;而JUnit 5作为JUnit系列的最新版本&#xff0c;为开发人员提供了更多的功能和灵活性。在本文中&#xff0c;我们将介绍JUnit 5&#xff0c;并探讨其与JUnit 4…...

2024年清明节安装matlab 2024a

下载安装离线支持包SupportSoftwareDownloader_R2024a_win64&#xff0c;地址https://ww2.mathworks.cn/support/install/support-software-downloader.html&#xff0c;运行软件&#xff08;自解压运行&#xff09;&#xff0c;登录账号&#xff08;需要提前在官网注册&#x…...

关于PostgreSQL JDBC中的log输出是怎么回事?

微信公众号:数据库杂记 个人微信: _iihero 我是iihero. 也可以叫我Sean. iihero@CSDN(https://blog.csdn.net/iihero) Sean@墨天轮 (https://www.modb.pro/u/16258) 数据库领域的资深爱好者一枚。SAP数据库技术专家与架构师,PostgreSQL ACE. 水木早期数据库论坛发起人db2@…...

【科研笔记】知识星球不可选择内容爬虫

知识星球不可选择内容爬虫 1 背景2 实现3 拓展遗留问题1 背景 针对与知识星球中,电脑打开网页不可选择复制粘贴的问题,进行爬虫处理,获取网页的内容,并保存在本地 2 实现 需要下载python,和爬虫的第三方库selenium,可以查看博客中有关selenium的内容进行回顾。当前使用…...

[技术闲聊]我对电路设计的理解(二)

第一篇文章 [技术闲聊]我对电路设计的理解(一)&#xff0c;看着是述说着应届生如何对待一份工作&#xff0c;其实也是我在过往以及以目前视野看过往的事情&#xff0c;自己的一种态度。谦虚&#xff0c;是一个不可多得的词汇&#xff0c;因为刚起步&#xff0c;学习的东西很多&…...

【Android、 kotlin】kotlin学习笔记

基本语法 fun main(){val a2var b "Hello"println("$ (a - 1} $b Kotlin!")} Variables 只赋值一次用val read-only variables with val 赋值多次用var mutable variables with var Standard output printin() and print() functions String templ…...

Debian 配置国内软件源

为什么需要&#xff1f; Debian安装好之后默认是没有软件源的&#xff0c;只能通过本身的光盘上的软件进行安装&#xff0c;这样明显是不能够满足我们的需要的&#xff0c;考虑到国内的上网速度以及环境&#xff0c;配置一个国内的阿里镜像源是最好的选择。 使用 sudo vim /…...

选数(dfs,isprime)

题目&#xff1a;P1036 [NOIP2002 普及组] 选数 - 洛谷 | 计算机科学教育新生态 (luogu.com​​​​​​.cn) #include<bits/stdc.h> using namespace std; int n,k; int a[22]; long long ans; bool isprime(int n){for(int i2;i<sqrt(n);i){if(n%i0) return false;…...

RocketMQ(版本4.9.4)+RocketMQ_Dashbord环境搭建(生产者、消费者的前置环境搭建)

一、官方网站下载 RocketMQ源码包 https://rocketmq.apache.org/zh/docs/4.x/introduction/02quickstart 二、把rocketMQ上传到Linux环境下解压&#xff0c;编译&#xff0c;执行以下命令&#xff08;需要提前装jdk和maven并配置好环境变量&#xff09; unzip rocketmq-all-4…...

css隐藏溢出隐藏的滚动条

msOverflowStyle: none: 这个属性用于在 Internet Explorer 浏览器中定义滚动条的样式。将其设置为 none 可以隐藏滚动条。 scrollbarWidth: none: 这个属性用于定义滚动条的宽度。将其设置为 none 可以隐藏滚动条。这个属性在一些新的浏览器中被支持&#xff0c;如 Firefox。…...

scss常用混入(mixin)、@inclue

mixin和inclue的基本使用 mixin混入可以用于定义重复使用的样式&#xff0c;比如下面CSS代码 .header {display: flex;justify-content: center;align-items: center;width: 500px;height: 100px; }.footer {display: flex;justify-content: center;align-items: center;width…...

补代码随想录算法训练营第44天 | 完全背包、518. 零钱兑换 II 、377. 组合总和 Ⅳ

完全背包 视频讲解&#xff1a;带你学透完全背包问题&#xff01; 和 01背包有什么差别&#xff1f;遍历顺序上有什么讲究&#xff1f;_哔哩哔哩_bilibili https://programmercarl.com/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80%E5%AE%8C%E5…...

【Linux】网络基础常识{OSI七层模型/ TCP/IP / 端口号 /各种协议}

文章目录 1.网络常识1.0DHCP协议1. 1IP地址/MAC地址/ARP协议是什么&#xff1f;IP/MACARP&#xff1a;IP ⇒ MAC 1.2手机连接wifi的原理 SSID与BSSID手机连接wifiSSID与BSSID 1.3手机如何通过“数据/流量”上网&#xff1f;1.4电脑连接wifi的原理&#xff1f;电脑通过热点上网…...

python--面向对象编程和类的定义,对象的创建

一、面向对象简介 1、什么是面向对象 面向对象是一种编程思想&#xff0c;把数据和对数据的多个操作方法封装在一起组成类&#xff0c;这样通过这个类创建出来的对象,就可以直接调用这些方法了。 2、面向对象相关的术语 类&#xff1a;用来描述具有相同的属性和方法的对象的…...

nssm 工具把asp.net core mvc变成 windows服务,使用nginx反向代理访问

nssm工具的作用&#xff1a;把项目部署成Windows服务&#xff0c;可以在系统后台运行 1.创建一个asp.net core mvc的项目weblication1 asp.net core mvc项目要成为windows服务需要安装下面的nuget包 <ItemGroup><PackageReference Include"Microsoft.Extension…...

String Encryptor custom Bean not found with name ‘jasyptStringEncryptor‘...

项目采用 spring boot 2.6.13 jasypt-spring-boot-starter 3.0.5 apollo-client 1.6.0 自定义jasyptStringEncryptor&#xff0c;服务器上启动死活报找不到bean jasyptStringEncryptor&#xff0c;采用默认的&#xff0c;密文配置项自然解密失败导致服务无法启动。 经过一…...

FastAPI+React全栈开发14 FastAPI如何开发REST接口

Chapter03 Getting Started with FastAPI 14 How does FastAPI speak REST FastAPIReact全栈开发14 FastAPI如何开发REST接口 Let’s create a minial FastAPI application, a classic Hello World example, and start examining how FastAPI structures the endpoints. I u…...

在 DDD 中,如何处理领域对象的持久化?

在 DDD 中&#xff0c;领域对象的持久化工作通常是通过仓库 Repository 和工厂 Factory 实现的。仓库是一种用于访问领域对象的机制。他负责将领域对象从内存中保存到持久存储&#xff0c;如数据库中&#xff0c;以及从持久存储中检索领域对象。而工厂则负责从持久存储中组装领…...

centos 如何安装nvidia-container-runtime

在CentOS上安装nvidia-container-runtime&#xff0c;首先需要确保你的系统已经安装了NVIDIA的驱动和docker。以下是安装步骤&#xff1a; 确保Docker已安装&#xff1a; sudo yum install -y yum-utils sudo yum-config-manager --add-repo https://download.docker.com/lin…...

非写代码无以致远

标题党一下&#xff0c;本篇文章主要汇总了一些代码题&#xff0c;让大家写一些代码练习一下吧&#xff01; 变种水仙花_牛客题霸_牛客网 (nowcoder.com) #include<stdio.h> int main() {for (int i 10000; i < 99999; i) {int sum 0;for (int j 10; j < 1000…...

wordpress 链接跳转/网站seo分析案例

目录 (?)[] 本文地址&#xff1a;http://blog.csdn.net/spch2008/article/details/9005885 Paste环境准备 1. 下载paste&#xff0c;放于eclipse目录中 paste库&#xff1a;http://download.csdn.net/detail/spch2008/5500979 2.目录结构 现在将之前的程序改写&#xff0c;改…...

有经验的唐山网站建设/网络广告营销的典型案例

终端提示如下&#xff1a; ERROR 1064 (42000): You have an error in your SQL syntax; check the manual that corresponds to your MySQL server version for the right syntax to use near order at line 1 如果用了mysql中的关键字做字段&#xff0c;当查询的时候可以用…...

网站如何设置域名/网络营销有哪些推广方式

数组 数组&#xff1a;是相同类型数据的有序集合&#xff0c;描述的是相同类型的若干个数据&#xff0c;按照一定先后顺序排列组合而成&#xff0c;可以通过下标来访问数组元素&#xff0c;下标从0开始。 声明&#xff1a;dataType[] arrays;或者dataType array[];首选第一种 …...

北京网站建设哪家便宜/郑州百度推广开户

事务管理方式 在Spring中&#xff0c;事务有两种实现方式&#xff0c;分别是编程式事务管理和声明式事务管理两种方式。 编程式事务管理&#xff1a; 编程式事务管理使用TransactionTemplate或者直接使用底层的PlatformTransactionManager。对于编程式事务管理&#xff0c;spr…...

wordpress4.9下载/推广一般收多少钱

1. public interface xxx 定义注解 public interface xxx 定义接口 interface和interface是完全不一样的&#xff0c;两码事 http://bbs.csdn.net/topics/380077509...

wordpress 图片菜单/什么软件可以找客户资源

今天看了七月在线算法课。再一次认识了LCS&#xff0c;现在整理记录&#xff1a; LCS&#xff08;Longest Common Subsequence&#xff09;最长公共子序列。 一个序列S任意删除若干个字符得到新序列T&#xff0c;那么T叫做S的子序列。 两个序列X和Y的公共子序列中&#xff0…...