质数距离 - 如何在较合理的时间复杂度内求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文件,右键 选择添加为…...
IDEA运行Tomcat出现乱码问题解决汇总
最近正值期末周,有很多同学在写期末Java web作业时,运行tomcat出现乱码问题,经过多次解决与研究,我做了如下整理: 原因: IDEA本身编码与tomcat的编码与Windows编码不同导致,Windows 系统控制台…...
测试微信模版消息推送
进入“开发接口管理”--“公众平台测试账号”,无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息: 关注测试号:扫二维码关注测试号。 发送模版消息: import requests da…...
云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?
大家好,欢迎来到《云原生核心技术》系列的第七篇! 在上一篇,我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在,我们就像一个拥有了一块崭新数字土地的农场主,是时…...
蓝桥杯 2024 15届国赛 A组 儿童节快乐
P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡,轻快的音乐在耳边持续回荡,小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下,六一来了。 今天是六一儿童节,小蓝老师为了让大家在节…...
抖音增长新引擎:品融电商,一站式全案代运营领跑者
抖音增长新引擎:品融电商,一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中,品牌如何破浪前行?自建团队成本高、效果难控;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...
将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?
Otsu 是一种自动阈值化方法,用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理,能够自动确定一个阈值,将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...
ElasticSearch搜索引擎之倒排索引及其底层算法
文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...
算法岗面试经验分享-大模型篇
文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer (1)资源 论文&a…...
mac 安装homebrew (nvm 及git)
mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用: 方法一:使用 Homebrew 安装 Git(推荐) 步骤如下:打开终端(Terminal.app) 1.安装 Homebrew…...
关于uniapp展示PDF的解决方案
在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项: 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库: npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...
