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

素数相关(结合回文数,合数)线性筛素数(欧拉筛法)Euler【算法模板笔记】

一、朴素筛法(埃拉托斯特尼筛法)
  • Eratosthenes 筛法(埃拉托斯特尼筛法,简称埃氏筛法)

  • 时间复杂度是O(nloglogn)

不常用,被欧拉筛代替,略

二、线性筛素数(欧拉筛法)
  • 简介

  • 线性筛法 也称为 Euler 筛法(欧拉筛法)

  • 对比

  • 普通的筛法就是1到n的倍数来筛,线性筛就是 用1到n中的素数的倍数来筛

  • 时间复杂度 O(n)

  • buff

  • 筛法求素数的同时也得到了每个数的最小质因子。

  • 原理

  • 中心思想:每个数只能被自己的最小质因子筛掉一次

  • 算法原理解释

  • 原理:对于任意合数,必定可以有最小质因子乘以最大因子的分解方式。因此,对于每个合数,只要用最大因子筛一遍,枚举时只要枚举最小质因子即可。由于每个合数都只被标记一次,达到了线性

  • // 任意合数,必定可以有最小质因子乘以最大因子的分解方式。

  • // 所以我们只要保证每个合数都由最小质因子筛掉就行了

  • //用两层循环枚举最小质因子和最大因子。i是最大因子,prime[j]是最小质因子

  • break整除中断原因

  • 解释1

  • // 这里为什么要break

  • // 因为如果不break

  • // i * p[j + 1] 的最小质因子就不是p[j + 1] 了

  • // 而是 i 的最小质因子 p[j]。

  • 解释2

  • //这个break发生时,这个primes[j]的值,是i的最小质因子

  • //保证合数只被最小质因子划掉一次

  • //如果i是质数,则最多枚举到自身中断

  • //如果i是合数,则最多枚举到自身的最小质数中断

  • 文章

  • 【算法/数论】欧拉筛法详解:过程详述、正确性证明、复杂度证明_CSDN博客_欧拉筛

  • 例题

  • P3383 【模板】线性筛素数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

  • Sherlock and his girlfriend - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

三、与回文数结合
  • 回文数

  • 判断回文数

  • 构造回文数

  • 回文质数

  • 偶数肯定不是质数。这样至少排除一半多的数据量

  • 知识点: “偶数长度的回文数”中只有11是素数,其他的都可以被11整除。

  • 偶数位数回文数(除11)必定不是质数

  • 例题

  • 回文素数 - 回文素数 - 力扣(LeetCode)

  • P1217 [USACO1.5]回文质数 Prime Palindromes - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

四、与合数结合
  • 方法

  • 用欧拉筛反向筛出合数

  • 合数相关理论

  • 例题

  • P1835 素数密度 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

模板
/*prime_nums_Euler*/
#include<bits/stdc++.h>
#define MAXN 100000005
using namespace std;//P3383 【模板】线性筛素数bool isprime[MAXN]; // isprime[i]表示i是不是素数
int prime[MAXN]; // 现在已经筛出的素数列表
int nums = 0; // 已经筛出的素数个数void euler_old(int n){memset(isprime, true, sizeof(isprime)); // 先全部标记为素数isprime[1] = false; // 1不是素数for(int i = 2; i <= n; ++i){ // i从2循环到n(外层循环)if(isprime[i]) prime[++nums] = i;// 如果i没有被前面的数筛掉,则i是素数for(int j = 1; j <= nums && prime[j] <= n/i; ++j){//枚举已经记录的质数(内层循环)//i * prime[j] <= n:由于题目只求小于n的数是否是质数,所以大于n的就不管了【越界中断】isprime[i * prime[j]] = false;// 倍数标记为合数,也就是i用prime[j]把i * prime[j]筛掉了if(i % prime[j] == 0) break;//【整除中断】}}
}//以下是acwing的模板int primes[MAXN], cnt;  // primes[]存储所有素数
bool st[MAXN];  // st[x]存储x是否被筛掉:true表示要被筛掉(没有处理1的特判)void get_primes(int n){for(int i = 2; i <= n; i++){if(!st[i]) primes[cnt++] = i;  //如果没有被筛掉,直接录入,并且cnt++for(int j = 0; primes[j] <= n/i; j++){  //从小到大枚举所有质数st[primes[j] * i] = 1;  //筛掉质数的倍数的数if (i % primes[j] == 0) break;  //【精髓:整除中断】//这个break发生时,这个primes[j]的值,是i的最小质因子}}
}int main(){int n; // 上限,即筛出<=n的素数scanf("%d", &n);get_primes(n);int q,k;//q次询问第 k 小的素数scanf("%d", &q);while(q--){scanf("%d", &k);printf("%d\n", primes[k-1]);}// for(int i = 2; i<=n; i++) if(isprime[i]) printf("%d ", i);// for(int i = 2; i<=n; i++) if(!st[i]) printf("%d ", i);return 0;
}

相关文章:

素数相关(结合回文数,合数)线性筛素数(欧拉筛法)Euler【算法模板笔记】

一、朴素筛法&#xff08;埃拉托斯特尼筛法&#xff09;Eratosthenes 筛法&#xff08;埃拉托斯特尼筛法&#xff0c;简称埃氏筛法&#xff09;时间复杂度是O(nloglogn)不常用&#xff0c;被欧拉筛代替&#xff0c;略二、线性筛素数&#xff08;欧拉筛法&#xff09;简介线性筛…...

1.7配置OSPF手动汇总

实验7:配置OSPF手动汇总 实验目的实现OSPF路由汇总的配置阐明OSPF引入的外部路由时进行路由汇总的方法实验拓扑配置OSPF手动汇总实验拓扑如图1-17所示。 图1-17 配置OSPF手动汇总 实验步骤配置IP地址,配置OSPF(和实验6一致,此处略)在…...

多线程下载工具axel的安装和使用

多线程下载工具axel的安装和使用 Axel是一个轻量级下载程序&#xff0c;它和其他加速器一样&#xff0c;对同一个文件建立多个连接&#xff0c;每个连接下载单独的文件片段以更快地完成下载。 Axel 支持 HTTP、HTTPS、FTP 和 FTPS 协议。它也可以使用多个镜像站点下载单个文件…...

大数据专业职业前景如何

大数据专业毕业生未来的岗位选择空间比较大&#xff0c;有三大类岗位可选择分别是大数据开发岗位、大数据分析岗位和大数据运维岗位&#xff0c;在不同的行业和技术体系结构下这些岗位也包含很多细分的岗位。 大数据开发岗位分为平台研发岗位和行业场景开发岗位两大类&#xf…...

拉格朗日乘数法在原材料选择问题上的具体应用

问题需求&#xff1a; 输入待制作的材料&#xff1a;(材料长&#xff0c;材料数量) 分别为(5401&#xff0c;124)、&#xff08;200&#xff0c;135&#xff09;、&#xff08;1350&#xff0c;45&#xff09;&#xff0c; 输入原材料长度最大值6500&#xff0c;最小值3500&…...

零信任-腾讯零信任iOA介绍(4)

​腾讯零信任介绍 腾讯零信任是一种信息安全架构&#xff0c;旨在通过限制对计算设备、数据和应用程序的访问来保护敏感信息。腾讯零信任的主要思想是&#xff0c;任何计算设备、数据或应用程序都不应被自动信任&#xff0c;并需要经过授权后才能访问敏感信息。 腾讯零信任的…...

标准的maven依赖包应该包含哪些东西?

背景在阅读源码的时候&#xff0c;发现有一些maven依赖包里面没有包含pom文件&#xff0c;一些maven依赖包包含&#xff0c;而且除此之外还有一些细微的差异。今天就来聊一下关于一个标准的依赖包应该是什么样子的。一个标准的Maven依赖包通常包含以下文件&#xff1a;Java类文…...

网络安全-Nmap

网络安全-Nmap Nmap-号称诸神之眼 这个呢就是用来扫描网络端口的 Namp的工作原理很像一个雷达 做任何攻击之前&#xff0c;得先知道怎么去找破绽&#xff0c;而不是钢铁洪流&#xff0c;那个是不叫渗透了&#xff0c;叫硬钢。 咋用呢&#xff1f; 很简单 直接 nmap 后面跟网址…...

【物联网】mqtt初体验

文章目录安装EMQXjava集成添加依赖mqtt配置参数发布组件订阅组件测试接口接口测试最近在了解物联网云平台方面的知识&#xff0c;解除了mqtt协议&#xff0c;只看书籍难免有些枯燥&#xff0c;所以直接试验一下&#xff0c;便于巩固理论知识。 broker服务器操作系统&#xff1a…...

2023年阿里云活动有哪些实例规格的云服务器?如何选择这些实例规格

2023年阿里云活动有哪些实例规格的云服务器&#xff1f;新手用户通过阿里云活动选购阿里云服务器的时候实例规格应该怎么选&#xff0c;因为同配置的云服务器往往有多种不同是规格的云服务器可供选择&#xff0c;而且不同实例规格的云服务器之间价格差别还比较大&#xff0c;因…...

深入理解 Handler(java 层 + native 层)

文章目录回顾线程消息队列时怎样实现的消息是怎么传递的&#xff1f;Handle 的延迟消息是怎么处理的&#xff1f;IdleHandler 的原理主线程进入了 Looper 循环为什么没有 ANR&#xff1f;消息屏障是什么&#xff1f;回顾 之前学习过Handler相关的基础知识&#xff0c;今天再学…...

初步认识操作系统(Operator System)

操作系统一&#xff0c;冯诺依曼体系结构内存的重要作用二&#xff0c;操作系统的概念三&#xff0c;设计操作系统的目的三&#xff0c;操作系统在计算机体系中的定位四&#xff0c;操作系统是如何进行管理的一&#xff0c;冯诺依曼体系结构 在众多计算机相关的书籍中&#xff…...

Android—HTTPS部署自签名证书

一、生成自签名私有证书单向认证&#xff08;只需要服务端证书&#xff09; 生成server_ks.jks服务端密钥配置到服务端生成server.cer服务端证书配置到客户端 双向认证&#xff08;还需要客户端证书&#xff0c;和信任证书&#xff09; 生成client_ks.jks客户端密钥配置到客户…...

java基于springboot+vue微信小程序的学生健康管理

任何系统都要遵循系统设计的基本流程,本系统也不例外,同样需要经过市场调研,需求分析,概要设计,详细设计,编码,测试这些步骤,基于Java语言、微信小程序技术设计并实现了学生健康管理小程序。系统主要包括系统首页、个人中心、学生管理、健康档案管理、体检报告管理、健康评估管…...

金三银四丨黑蛋老师带你剖析-漏洞岗

作者丨黑蛋病毒岗之前我们简单看了看二进制逆向岗位和漏洞岗&#xff0c;今天我们来看一看病毒岗位&#xff0c;就单纯看二进制病毒岗位和漏洞岗位&#xff0c;其所需要的基础知识是差不多的&#xff0c;在Windows平台上&#xff0c;无非就是汇编&#xff0c;C语言&#xff0c;…...

pinia实战 购物车(自定义插件实现pinia持久化)

目录 一、实例 二、需求 三. 代码解析 shop.vue shop.ts 四、持久化插件 插件介绍 持久化实现思路 一、实例 二、需求 单选全选功能&#xff0c;并且可以互相联动 小计功能 总计功能 商品加减&#xff0c;数量为零时不能在减 三. 代码解析 shop.vue 1.获取shop模块实…...

idea使用本地代码远程调试线上运行代码---linux环境

场景&#xff1a; 之前介绍过windows环境上&#xff0c;用idea进行远程调试那么在linux环境下实战一下 环境&#xff1a; linux 测试应用&#xff1a;使用docker部署的platform-multiappcenter-base-app-1.0.0-SNAPSHOT.jar 应用 测试应用端口&#xff1a;19001 测试工具&…...

Java 基础面试题——集合

目录1.Java 有哪些常用容器&#xff08;集合&#xff09;&#xff1f;2.Collection 和 Collections 有什么区别&#xff1f;3.List、Set、Map 之间的区别是什么&#xff1f;4.HashMap 的长度为什么是 2 的 N 次方&#xff1f;源码中是如何保证的&#xff1f;5.HashMap 和 Hasht…...

编程思想、方法论和架构模式的应用

概要编程思想是指在编写代码时所采用的基本思维方式和方法论。分类编程思想分类&#xff1a;面向对象编程&#xff08;Object-Oriented Programming&#xff0c;简称OOP&#xff09;&#xff1a;把数据和对数据的操作封装在一起&#xff0c;通过类和对象的概念实现模块化、可重…...

Vue|事件处理

事件处理1. 事件使用1.1 事件绑定1.2 事件参数2. 事件修饰符2.1 阻止默认事件2.2 阻止事件冒泡2.3 事件只允许触发一次2.4 事件捕获2.5 操作当前元素2.6 行为立即执行无需等待回调3. 键盘事件4. 本章小结4.1 事件使用小结4.2 事件修饰符小结4.3 键盘事件小结1. 事件使用 1.1 事…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

国防科技大学计算机基础课程笔记02信息编码

1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制&#xff0c;因此这个了16进制的数据既可以翻译成为这个机器码&#xff0c;也可以翻译成为这个国标码&#xff0c;所以这个时候很容易会出现这个歧义的情况&#xff1b; 因此&#xff0c;我们的这个国…...

Spark 之 入门讲解详细版(1)

1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室&#xff08;Algorithms, Machines, and People Lab&#xff09;开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目&#xff0c;8个月后成为Apache顶级项目&#xff0c;速度之快足见过人之处&…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

聊一聊接口测试的意义有哪些?

目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开&#xff0c;首…...

C/C++ 中附加包含目录、附加库目录与附加依赖项详解

在 C/C 编程的编译和链接过程中&#xff0c;附加包含目录、附加库目录和附加依赖项是三个至关重要的设置&#xff0c;它们相互配合&#xff0c;确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中&#xff0c;这些概念容易让人混淆&#xff0c;但深入理解它们的作用和联…...

JavaScript 数据类型详解

JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型&#xff08;Primitive&#xff09; 和 对象类型&#xff08;Object&#xff09; 两大类&#xff0c;共 8 种&#xff08;ES11&#xff09;&#xff1a; 一、原始类型&#xff08;7种&#xff09; 1. undefined 定…...