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

质数距离 - 如何在较合理的时间复杂度内求2e9范围内的质数

求l、r之间的质数,范围在2e9,但l、r的差值不大,在1e6范围内

先求出\sqrt{2e9} 内的质数,然后拿这个指数去筛[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之间的质数&#xff0c;范围在2e9&#xff0c;但l、r的差值不大&#xff0c;在1e6范围内 先求出 内的质数&#xff0c;然后拿这个指数去筛[l, r]范围内的即可 #include<bits/stdc.h> #define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define endl \…...

八、3d场景的区域光墙

在遇到区域展示的时候我们就能看到炫酷的区域选中效果&#xff0c;那么代码是怎么编辑的呢&#xff0c;今天咱们就好好说说&#xff0c;下面看实现效果。 思路&#xff1a; 首先&#xff0c;光墙肯定有多个&#xff0c;那么必须要创建一个新的js文件来作为他的原型对象。这个光…...

深入探讨 Presto 中的缓存

【squids.cn】 全网zui低价RDS&#xff0c;免费的迁移工具DBMotion、数据库备份工具DBTwin、SQL开发工具等 Presto是一种流行的开源分布式SQL引擎&#xff0c;使组织能够在多个数据源上大规模运行交互式分析查询。缓存是一种典型的提高 Presto 查询性能的优化技术。它为 Prest…...

3.物联网射频识别,(高频)RFID应用ISO14443-2协议,(校园卡)Mifare S50卡

一。ISO14443-2协议简介 1.ISO14443协议组成及部分缩略语 &#xff08;1&#xff09;14443协议组成&#xff08;下面的协议简介会详细介绍&#xff09; 14443-1 物理特性 14443-2 射频功率和信号接口 14443-3 初始化和防冲突 &#xff08;分为Type A、Type B两种接口&…...

【IDEA】IDEA 单行注释开头添加空格

操作 打开 IDEA 的 Settings 对话框&#xff08;快捷键为CtrlAltS&#xff09;&#xff1b;在左侧面板中选择Editor -> Code Style -> Java&#xff1b;在右侧面板中选择Code Generation选项卡&#xff1b;将Line comment at first column选项设置为false使注释加在行开…...

三等分功分器[波导]设计详细教程

想必大家通过阅读相关文献可以发现三等分实现可以有很多不同的方法&#xff0c;这里采用的是先不等分再等分的方式&#xff0c;仅供参考。 主要指标 中心频率为280GHz&#xff0c;采用WR-3频段的标准波导&#xff0c;将2:1不等功率分配耦合器与3dB等功率分配耦合器级联&#…...

Mysql分库分表

1.原理 2.Sharding JDBC 官网https://shardingsphere.apache.org/ 2.1 水平拆分 创建一个新的springboot项目 导入依赖,直接将原本的dependencies给覆盖掉 <dependencies><!-- ShardingJDBC依赖 --><dependency><groupId>org.apache.shardings…...

【算法学习】-【双指针】-【复写零】

LeetCode原题链接&#xff1a;1089. 复写零 下面是题目描述&#xff1a; 给你一个长度固定的整数数组 arr &#xff0c;请你将该数组中出现的每个零都复写一遍&#xff0c;并将其余的元素向右平移。 注意&#xff1a;请不要在超过该数组长度的位置写入元素。请对输入的数组 …...

【算法优选】双指针专题——叁

文章目录 &#x1f60e;前言&#x1f333;[两数之和](https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/)&#x1f6a9;题目描述&#xff1a;&#x1f6a9;算法思路&#xff1a;&#x1f6a9;算法流程&#xff1a;&#x1f6a9;代码实现 &#x1f384;[三数之和]…...

Java栈的压入、弹出序列(详解)

目录 1.题目描述 2.题解 方法1 方法2 1.题目描述 输入两个整数序列&#xff0c;第一个序列表示栈的压入顺序&#xff0c;请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序&#xff0c;序列4,5,3,2,1是该压栈序…...

RabbitMQ学习笔记(消息发布确认,死信队列,集群,交换机,持久化,生产者、消费者)

MQ&#xff08;message queue&#xff09;&#xff1a;本质上是个队列&#xff0c;遵循FIFO原则&#xff0c;队列中存放的是message&#xff0c;是一种跨进程的通信机制&#xff0c;用于上下游传递消息。MQ提供“逻辑解耦物理解耦”的消息通信服务。使用了MQ之后消息发送上游只…...

PyTorch - 模型训练损失 (Loss) NaN 问题的解决方案

欢迎关注我的CSDN&#xff1a;https://spike.blog.csdn.net/ 本文地址&#xff1a;https://spike.blog.csdn.net/article/details/133378367 在模型训练中&#xff0c;如果出现 NaN 的问题&#xff0c;严重影响 Loss 的反传过程&#xff0c;因此&#xff0c;需要加入一些微小值…...

8、Nacos服务注册服务端源码分析(七)

本文收录于专栏 Nacos 中 。 文章目录 前言确定前端路由CatalogController.listDetail()ServiceManager总结 前言 前文我们分析了Nacos中客户端注册时数据分发的设计链路&#xff0c;本文根据Nacos前端页面请求&#xff0c;看下前端页面中的服务列表的数据源于哪里。 确定前端…...

MySQL使用Xtrabackup在线做主从

1、主库上操作 1.1前提 172.16.11.2&#xff08;主库&#xff09; 172.16.11.4&#xff08;从库&#xff09; 在执行备份之前&#xff0c;确保数据库没有锁定&#xff0c;以避免备份期间的任何写操作。 确保主库上的 MySQL 服务器正在运行&#xff0c;以便备份数据的一致性。…...

scala基础入门

一、Scala安装 下载网址&#xff1a;Install | The Scala Programming Language ideal安装 &#xff08;1&#xff09;下载安装Scala plugins &#xff08;2&#xff09;统一JDK环境&#xff0c;统一为8 &#xff08;3&#xff09;加载Scala &#xff08;4&#xff09;创建工…...

【Java-LangChain:面向开发者的提示工程-5】推断

第五章 推断 推断任务可以看作是模型接收文本作为输入&#xff0c;并执行某种分析的过程。其中涉及提取标签、提取实体、理解文本情感等等。如果你想要从一段文本中提取正面或负面情感&#xff0c;在传统的机器学习工作流程中&#xff0c;需要收集标签数据集、训练模型、确定如…...

【C++】手撕vector(vector的模拟实现)

手撕vector目录&#xff1a; 一、基本实现思路方针 二、vector的构造函数剖析&#xff08;构造歧义拷贝构造&#xff09; 2.1构造函数使用的歧义问题 2.2 vector的拷贝构造和赋值重载&#xff08;赋值重载不是构造哦&#xff0c;为了方便写在一起&#xff09; 三、vector的…...

智能指针那些事

​《Effective Modern C》学习笔记之条款二十一&#xff1a;优先选用std::make_unique和std::make_shared,而非直接new - 知乎...

Fiddler抓取手机https包的步骤

做接口测试时&#xff0c;有时我们需要使用fiddler进行抓包分析&#xff0c;那么如何抓取https包。主要分为以下七步&#xff1a; 1.设置fiddler选项&#xff1a;Tools->Options,按如下图勾选 2.下载并安装Fiddler证书生成器 下载地址&#xff1a;http://www.telerik.com/…...

idea没有maven工具栏解决方法

背景&#xff1a;接手的一些旧项目&#xff0c;有pom文件&#xff0c;但是用idea打开的时候&#xff0c;没有认为是maven文件&#xff0c;所以没有maven工具栏&#xff0c;不能进行重新加载pom文件中的依赖。 解决方法&#xff1a;选中pom.xml文件&#xff0c;右键 选择添加为…...

AI Agent在智能风控中的实战:多智能体欺诈检测与预警

AI Agent在智能风控中的实战:多智能体欺诈检测与预警 你有没有过明明是正常交易却被银行冻结账户的糟糕体验?或是听说过某电商平台上线新活动首日就被黑产团伙薅走数千万补贴的新闻?随着黑产欺诈向团伙化、专业化、动态化演进,传统依赖规则引擎、单模型机器学习的风控体系已…...

别再死记硬背了!用Multisim仿真+图解,5分钟搞懂三极管共射放大电路工作原理

用Multisim仿真图解5分钟掌握三极管共射放大电路三极管共射放大电路是电子技术中最基础也最关键的电路之一&#xff0c;但传统教材中复杂的公式推导和静态图解往往让初学者望而生畏。本文将带你用Multisim仿真软件&#xff0c;通过可视化的方式直观理解电路工作原理&#xff0c…...

用Python+OpenCV手把手实现Prewitt边缘检测(附完整代码与效果对比图)

用PythonOpenCV手把手实现Prewitt边缘检测&#xff08;附完整代码与效果对比图&#xff09; 边缘检测是计算机视觉中最基础也最关键的预处理步骤之一。想象一下&#xff0c;当你需要让计算机"看清"一张照片中的物体轮廓时&#xff0c;边缘检测算法就是它的"视觉…...

ParaView时间戳设置全攻略:从基础标注到自定义格式(5.8.0实测)

ParaView时间戳设置全攻略&#xff1a;从基础标注到自定义格式&#xff08;5.8.0实测&#xff09; 在科学可视化领域&#xff0c;时间戳不仅是数据演变的见证者&#xff0c;更是研究成果呈现的专业语言。ParaView作为开源可视化工具链的标杆&#xff0c;其时间标注功能在学术论…...

从Gamma函数到泊松分布:一个概率论中的含参量积分实用案例解析

Gamma函数与泊松分布&#xff1a;概率论中的数学之美 在数据科学和机器学习的实践中&#xff0c;概率分布构成了建模的基石。当我们深入探究这些分布背后的数学原理时&#xff0c;Gamma函数以其优雅的性质和广泛的应用脱颖而出。它不仅连接了离散与连续概率世界&#xff0c;更在…...

Python PIL 画矩形框

基础代码 from PIL import Image, ImageDraw# 打开图片 img Image.open(your_image.jpg)# 创建绘图对象 draw ImageDraw.Draw(img)# 矩形坐标 (x1, y1, x2, y2) coords (23, 21, 69, 76)# 画矩形框&#xff08;红色&#xff0c;线宽2&#xff09; draw.rectangle(coords, ou…...

机器学习驱动储氢材料发现:从特征工程到DFT/MD验证的完整指南

1. 项目概述与核心思路氢能被视为未来清洁能源体系的关键一环&#xff0c;但如何安全、高效、经济地储存氢气&#xff0c;一直是制约其大规模应用的瓶颈。在众多储氢技术路线中&#xff0c;固态储氢&#xff0c;特别是基于金属氢化物的储氢材料&#xff0c;因其高体积储氢密度和…...

脉冲神经网络加速器设计与边缘计算优化

1. 脉冲神经网络加速器的设计挑战与突破在边缘计算领域&#xff0c;脉冲神经网络(SNN)正以其独特的生物启发特性引发新一轮技术变革。与传统人工神经网络(ANN)相比&#xff0c;SNN通过离散的脉冲信号传递信息&#xff0c;模拟生物神经元的工作机制&#xff0c;理论上可实现超低…...

OmenSuperHub:基于WMI BIOS控制的高性能笔记本硬件管理方案

OmenSuperHub&#xff1a;基于WMI BIOS控制的高性能笔记本硬件管理方案 【免费下载链接】OmenSuperHub Control Omen laptop performance, fan speeds, and keyboard lighting, and unlock power limits. 项目地址: https://gitcode.com/gh_mirrors/om/OmenSuperHub 在惠…...

集成Taotoken为OpenClaw工作流提供持久化模型支持

&#x1f680; 告别海外账号与网络限制&#xff01;稳定直连全球优质大模型&#xff0c;限时半价接入中。 &#x1f449; 点击领取海量免费额度 集成Taotoken为OpenClaw工作流提供持久化模型支持 在构建基于OpenClaw的自动化Agent工作流时&#xff0c;一个稳定且可灵活切换的模…...