当前位置: 首页 > 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;右键 选择添加为…...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

Java 语言特性(面试系列1)

一、面向对象编程 1. 封装&#xff08;Encapsulation&#xff09; 定义&#xff1a;将数据&#xff08;属性&#xff09;和操作数据的方法绑定在一起&#xff0c;通过访问控制符&#xff08;private、protected、public&#xff09;隐藏内部实现细节。示例&#xff1a; public …...

《Playwright:微软的自动化测试工具详解》

Playwright 简介:声明内容来自网络&#xff0c;将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具&#xff0c;支持 Chrome、Firefox、Safari 等主流浏览器&#xff0c;提供多语言 API&#xff08;Python、JavaScript、Java、.NET&#xff09;。它的特点包括&a…...

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

SpringTask-03.入门案例

一.入门案例 启动类&#xff1a; package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文全面剖析RNN核心原理&#xff0c;深入讲解梯度消失/爆炸问题&#xff0c;并通过LSTM/GRU结构实现解决方案&#xff0c;提供时间序列预测和文本生成…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)

在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马&#xff08;服务器方面的&#xff09;的原理&#xff0c;连接&#xff0c;以及各种木马及连接工具的分享 文件木马&#xff1a;https://w…...

动态 Web 开发技术入门篇

一、HTTP 协议核心 1.1 HTTP 基础 协议全称 &#xff1a;HyperText Transfer Protocol&#xff08;超文本传输协议&#xff09; 默认端口 &#xff1a;HTTP 使用 80 端口&#xff0c;HTTPS 使用 443 端口。 请求方法 &#xff1a; GET &#xff1a;用于获取资源&#xff0c;…...

AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机

这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机&#xff0c;因为在使用过程中发现 Airsim 对外部监控相机的描述模糊&#xff0c;而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置&#xff0c;最后在源码示例中找到了&#xff0c;所以感…...