当前位置: 首页 > 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 事…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

MongoDB学习和应用(高效的非关系型数据库)

一丶 MongoDB简介 对于社交类软件的功能&#xff0c;我们需要对它的功能特点进行分析&#xff1a; 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具&#xff1a; mysql&#xff1a;关系型数据库&am…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

【Go语言基础【12】】指针:声明、取地址、解引用

文章目录 零、概述&#xff1a;指针 vs. 引用&#xff08;类比其他语言&#xff09;一、指针基础概念二、指针声明与初始化三、指针操作符1. &&#xff1a;取地址&#xff08;拿到内存地址&#xff09;2. *&#xff1a;解引用&#xff08;拿到值&#xff09; 四、空指针&am…...

招商蛇口 | 执笔CID,启幕低密生活新境

作为中国城市生长的力量&#xff0c;招商蛇口以“美好生活承载者”为使命&#xff0c;深耕全球111座城市&#xff0c;以央企担当匠造时代理想人居。从深圳湾的开拓基因到西安高新CID的战略落子&#xff0c;招商蛇口始终与城市发展同频共振&#xff0c;以建筑诠释对土地与生活的…...

接口自动化测试:HttpRunner基础

相关文档 HttpRunner V3.x中文文档 HttpRunner 用户指南 使用HttpRunner 3.x实现接口自动化测试 HttpRunner介绍 HttpRunner 是一个开源的 API 测试工具&#xff0c;支持 HTTP(S)/HTTP2/WebSocket/RPC 等网络协议&#xff0c;涵盖接口测试、性能测试、数字体验监测等测试类型…...

GO协程(Goroutine)问题总结

在使用Go语言来编写代码时&#xff0c;遇到的一些问题总结一下 [参考文档]&#xff1a;https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现&#xff1a; 今天在看到这个教程的时候&#xff0c;在自己的电…...

代码规范和架构【立芯理论一】(2025.06.08)

1、代码规范的目标 代码简洁精炼、美观&#xff0c;可持续性好高效率高复用&#xff0c;可移植性好高内聚&#xff0c;低耦合没有冗余规范性&#xff0c;代码有规可循&#xff0c;可以看出自己当时的思考过程特殊排版&#xff0c;特殊语法&#xff0c;特殊指令&#xff0c;必须…...

高防服务器价格高原因分析

高防服务器的价格较高&#xff0c;主要是由于其特殊的防御机制、硬件配置、运营维护等多方面的综合成本。以下从技术、资源和服务三个维度详细解析高防服务器昂贵的原因&#xff1a; 一、硬件与技术投入 大带宽需求 DDoS攻击通过占用大量带宽资源瘫痪目标服务器&#xff0c;因此…...