质数距离 - 如何在较合理的时间复杂度内求2e9范围内的质数
求l、r之间的质数,范围在2e9,但l、r的差值不大,在1e6范围内

先求出 内的质数,然后拿这个指数去筛[l, r]范围内的即可
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef pair<int, int> PII;
typedef long long ll;
typedef long double ld;const int N = 50010, M = 1000010;int primes[N], cnt;
bool st[M];
int p[M];void init()
{for(int i = 2; i < N; i ++){if(!st[i])primes[cnt ++] = i;for(int j = 0; primes[j] * i < N; j ++){st[primes[j] * i] = true;if(i % primes[j] == 0)break;}}
}int main()
{IOSinit();int cnt_tmp = cnt;ll l, r;while(cin >> l >> r){if(l == 1)l = 2;memset(st, false, sizeof st);cnt = cnt_tmp;for(int i = 0; i < cnt; i ++){ll start = max((ll)primes[i] * 2, (l + primes[i] - 1) / primes[i] * primes[i]);for(ll j = start; j <= r; j += primes[i]){st[j - l] = true;}}cnt = 0;for(int i = 0; i <= r - l; i ++){if(!st[i])p[cnt ++] = i;}if(cnt < 2){cout << "There are no adjacent primes." << endl;continue;}int min1 = 0, min2 = 2e9, max1 = 0, max2 = 0;for(int i = 0; i < cnt - 1; i ++){if(p[i + 1] - p[i] < min2 - min1){min1 = p[i];min2 = p[i + 1];}if(p[i + 1] - p[i] > max2 - max1){max1 = p[i];max2 = p[i + 1];}}cout << min1+l << "," << min2+l << " are closest, " << max1+l << "," << max2+l << " are most distant." << endl;}return 0;
}
要注意的几个点:
1.对于每次筛最少要从primes[i] * 2开始,不能筛到质数
2.在start计算过程中和j+的过程中很容易爆int,注意这部分开ll
3.求大于等于l的第一个p的倍数:(l + p - 1) / p * p
相关文章:
质数距离 - 如何在较合理的时间复杂度内求2e9范围内的质数
求l、r之间的质数,范围在2e9,但l、r的差值不大,在1e6范围内 先求出 内的质数,然后拿这个指数去筛[l, r]范围内的即可 #include<bits/stdc.h> #define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define endl \…...
八、3d场景的区域光墙
在遇到区域展示的时候我们就能看到炫酷的区域选中效果,那么代码是怎么编辑的呢,今天咱们就好好说说,下面看实现效果。 思路: 首先,光墙肯定有多个,那么必须要创建一个新的js文件来作为他的原型对象。这个光…...
深入探讨 Presto 中的缓存
【squids.cn】 全网zui低价RDS,免费的迁移工具DBMotion、数据库备份工具DBTwin、SQL开发工具等 Presto是一种流行的开源分布式SQL引擎,使组织能够在多个数据源上大规模运行交互式分析查询。缓存是一种典型的提高 Presto 查询性能的优化技术。它为 Prest…...
3.物联网射频识别,(高频)RFID应用ISO14443-2协议,(校园卡)Mifare S50卡
一。ISO14443-2协议简介 1.ISO14443协议组成及部分缩略语 (1)14443协议组成(下面的协议简介会详细介绍) 14443-1 物理特性 14443-2 射频功率和信号接口 14443-3 初始化和防冲突 (分为Type A、Type B两种接口&…...
【IDEA】IDEA 单行注释开头添加空格
操作 打开 IDEA 的 Settings 对话框(快捷键为CtrlAltS);在左侧面板中选择Editor -> Code Style -> Java;在右侧面板中选择Code Generation选项卡;将Line comment at first column选项设置为false使注释加在行开…...
三等分功分器[波导]设计详细教程
想必大家通过阅读相关文献可以发现三等分实现可以有很多不同的方法,这里采用的是先不等分再等分的方式,仅供参考。 主要指标 中心频率为280GHz,采用WR-3频段的标准波导,将2:1不等功率分配耦合器与3dB等功率分配耦合器级联&#…...
Mysql分库分表
1.原理 2.Sharding JDBC 官网https://shardingsphere.apache.org/ 2.1 水平拆分 创建一个新的springboot项目 导入依赖,直接将原本的dependencies给覆盖掉 <dependencies><!-- ShardingJDBC依赖 --><dependency><groupId>org.apache.shardings…...
【算法学习】-【双指针】-【复写零】
LeetCode原题链接:1089. 复写零 下面是题目描述: 给你一个长度固定的整数数组 arr ,请你将该数组中出现的每个零都复写一遍,并将其余的元素向右平移。 注意:请不要在超过该数组长度的位置写入元素。请对输入的数组 …...
【算法优选】双指针专题——叁
文章目录 😎前言🌳[两数之和](https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/)🚩题目描述:🚩算法思路:🚩算法流程:🚩代码实现 🎄[三数之和]…...
Java栈的压入、弹出序列(详解)
目录 1.题目描述 2.题解 方法1 方法2 1.题目描述 输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序…...
RabbitMQ学习笔记(消息发布确认,死信队列,集群,交换机,持久化,生产者、消费者)
MQ(message queue):本质上是个队列,遵循FIFO原则,队列中存放的是message,是一种跨进程的通信机制,用于上下游传递消息。MQ提供“逻辑解耦物理解耦”的消息通信服务。使用了MQ之后消息发送上游只…...
PyTorch - 模型训练损失 (Loss) NaN 问题的解决方案
欢迎关注我的CSDN:https://spike.blog.csdn.net/ 本文地址:https://spike.blog.csdn.net/article/details/133378367 在模型训练中,如果出现 NaN 的问题,严重影响 Loss 的反传过程,因此,需要加入一些微小值…...
8、Nacos服务注册服务端源码分析(七)
本文收录于专栏 Nacos 中 。 文章目录 前言确定前端路由CatalogController.listDetail()ServiceManager总结 前言 前文我们分析了Nacos中客户端注册时数据分发的设计链路,本文根据Nacos前端页面请求,看下前端页面中的服务列表的数据源于哪里。 确定前端…...
MySQL使用Xtrabackup在线做主从
1、主库上操作 1.1前提 172.16.11.2(主库) 172.16.11.4(从库) 在执行备份之前,确保数据库没有锁定,以避免备份期间的任何写操作。 确保主库上的 MySQL 服务器正在运行,以便备份数据的一致性。…...
scala基础入门
一、Scala安装 下载网址:Install | The Scala Programming Language ideal安装 (1)下载安装Scala plugins (2)统一JDK环境,统一为8 (3)加载Scala (4)创建工…...
【Java-LangChain:面向开发者的提示工程-5】推断
第五章 推断 推断任务可以看作是模型接收文本作为输入,并执行某种分析的过程。其中涉及提取标签、提取实体、理解文本情感等等。如果你想要从一段文本中提取正面或负面情感,在传统的机器学习工作流程中,需要收集标签数据集、训练模型、确定如…...
【C++】手撕vector(vector的模拟实现)
手撕vector目录: 一、基本实现思路方针 二、vector的构造函数剖析(构造歧义拷贝构造) 2.1构造函数使用的歧义问题 2.2 vector的拷贝构造和赋值重载(赋值重载不是构造哦,为了方便写在一起) 三、vector的…...
智能指针那些事
《Effective Modern C》学习笔记之条款二十一:优先选用std::make_unique和std::make_shared,而非直接new - 知乎...
Fiddler抓取手机https包的步骤
做接口测试时,有时我们需要使用fiddler进行抓包分析,那么如何抓取https包。主要分为以下七步: 1.设置fiddler选项:Tools->Options,按如下图勾选 2.下载并安装Fiddler证书生成器 下载地址:http://www.telerik.com/…...
idea没有maven工具栏解决方法
背景:接手的一些旧项目,有pom文件,但是用idea打开的时候,没有认为是maven文件,所以没有maven工具栏,不能进行重新加载pom文件中的依赖。 解决方法:选中pom.xml文件,右键 选择添加为…...
癫痫手术精准定位:基于脑电信号昼夜节律与多生物标志物的机器学习分析框架
1. 项目概述:当机器学习遇见脑电信号,如何让癫痫手术更精准?作为一名长期耕耘在生物医学信号处理与机器学习交叉领域的工程师,我常常思考如何将算法模型从实验室的“玩具”变成临床医生手中可靠的“手术刀”。癫痫,这个…...
自制射频功率计:基于AD8317芯片,成本43欧元实现1MHz-10GHz测量
1. 项目概述:为什么我要亲手打造一台射频功率计在无人机和模型飞行器的圈子里,尤其是在我们荷兰FMS Spaarnwoude俱乐部,合规飞行是头等大事。我给我的八轴飞行器加装了云台相机和图传系统,工作在5.8GHz频段。根据本地法规…...
2026智慧校园规划必读:如何在预算吃紧下选到高性价比方案
✅作者简介:合肥自友科技 📌核心产品:智慧校园平台(包括教工管理、学工管理、教务管理、考务管理、后勤管理、德育管理、资产管理、公寓管理、实习管理、就业管理、离校管理、科研平台、档案管理、学生平台等26个子平台) 。公司所有人员均有多…...
SMUDebugTool终极指南:如何深度掌控AMD Ryzen处理器的隐藏性能
SMUDebugTool终极指南:如何深度掌控AMD Ryzen处理器的隐藏性能 【免费下载链接】SMUDebugTool A dedicated tool to help write/read various parameters of Ryzen-based systems, such as manual overclock, SMU, PCI, CPUID, MSR and Power Table. 项目地址: ht…...
科华UPS电源全品类汇总:选型与场景适配指南
科华UPS电源作为国内智慧电能领域的主流产品,覆盖家用、办公、机房、工业等全场景,产品系列丰富、规格齐全,但多数用户在选型时,常因分不清系列差异、功率适配、架构类型而踩坑。本文系统汇总科华UPS电源的核心分类、主流系列、核…...
简单学习 --> SSE
我们使用AI时,AI对我们说的话不会一次性把全部内容弹出来,而是会像流水一样,一点点吐出来,那么这种丝滑的交互体验,背后的核心就是 SSE (Server-Sent Events)。 什么是 SSE? SSE(Server-Sent …...
SpeakingURL版本升级指南:从旧版本迁移到最新版本的完整教程
SpeakingURL版本升级指南:从旧版本迁移到最新版本的完整教程 【免费下载链接】speakingurl Generate a slug – transliteration with a lot of options 项目地址: https://gitcode.com/gh_mirrors/sp/speakingurl SpeakingURL是一款强大的URL友好化工具&…...
【C++】零基础入门 · 第 5 节:函数基础
前面四节我们写的代码都集中在 main 函数里。随着程序变复杂,所有逻辑堆在一起会越来越难维护。函数就是用来解决这个问题的——它把一段代码「打包」起来,取个名字,需要的时候调用就行。 1. 为什么需要函数 假设你需要在程序的不同地方打印一行分隔线: cout << &…...
基于ISDN信令的来电语音播报系统:从原理到树莓派实现
1. 项目概述:一个基于ISDN的来电语音播报系统如果你家里或办公室里还有一台老式的ISDN路由器,别急着把它当电子垃圾处理掉。我最近就利用手头一台闲置的ISDN路由器,折腾出了一个挺有意思的小玩意儿:一个能自动识别来电号码&#x…...
自动加字幕软件推荐:口播视频如何批量加字幕过
口播视频加字幕,为什么越做越累?一位知识类博主连续两周日更3条口播视频,每条12–18分钟,需手动校对字幕、拆分金句切片、补气口停顿、匹配背景音乐——最后一条视频发布时,字幕错漏率达17%,平台审核未过。…...
