首页/新闻资讯/正文详情

质数统计优化:线性筛与前缀和算法实践

发布时间:2026/11/2 17:36:30 来源:云帆数科 栏目:资讯中心
质数统计优化:线性筛与前缀和算法实践
1. 题目背景与核心需求解析这道来自洛谷P1865的A % B Problem是GESP C五级认证的典型练习题考察的核心是数论中的质数判断与算法优化技巧。题目要求我们处理n次查询每次给出区间[l,r]需要统计该区间内质数的数量。看似简单的需求背后隐藏着几个关键挑战数据规模极大m可达10^6n最多1000次查询时间效率要求高朴素算法必然超时边界条件复杂需要处理查询越界情况提示在实际编程竞赛中这类区间统计问题非常常见但往往需要巧妙运用预处理和数学优化才能高效解决。2. 算法选型与优化思路2.1 朴素算法的局限性分析最直观的做法是对每个查询区间[l,r]内的每个数进行质数判断。使用试除法判断质数的时间复杂度是O(√x)对于最大10^6的区间单次查询就需要约10^6×10^310^9次操作显然无法在合理时间内完成。// 低效的朴素解法示例仅作反面教材 bool isPrime(int x) { if(x 2) return false; for(int i2; i*ix; i) if(x%i 0) return false; return true; }2.2 线性筛欧拉筛算法详解线性筛法可以在O(m)时间内预处理出1~m的所有质数其核心思想是让每个合数只被它的最小质因子筛除。我们使用一个标记数组prime_ary[]其中prime_ary[i]1表示i是质数。算法流程初始化标记数组假设所有数都是质数从2开始遍历遇到质数就加入质数列表用当前数与已知质数的乘积标记合数关键优化当i能被当前质数整除时立即终止内层循环int prime_ary[1000005]; // 标记数组 vectorint primes; // 质数容器 void linearSieve(int m) { fill(prime_ary2, prime_arym1, 1); for(int i2; im; i) { if(prime_ary[i]) primes.push_back(i); for(int p : primes) { if(p*i m) break; prime_ary[p*i] 0; if(i%p 0) break; // 关键优化点 } } }2.3 前缀和优化查询效率即使有了质数标记数组每次查询仍需要遍历区间统计质数个数最坏情况下仍是O(m)时间复杂度。这时可以引入前缀和数组prime_pre[]其中prime_pre[i]表示[1,i]区间内质数的总数。前缀和数组的构建prime_pre[0] 0; for(int i1; im; i) prime_pre[i] prime_pre[i-1] prime_ary[i];查询优化原理 对于查询[l,r]质数数量 prime_pre[r] - prime_pre[l-1] 这使得单次查询时间复杂度降至O(1)3. 完整实现与代码解析3.1 输入输出处理题目输入格式要求第一行n(查询次数)和m(最大右端点)接下来n行每行l和r表示查询区间输出要求区间合法时输出质数数量区间越界时输出Crossing the line3.2 边界条件处理需要特别检查两种情况r ml 1这两种情况都视为查询越界需要输出特定提示。3.3 完整代码实现#include iostream #include vector #include algorithm using namespace std; const int MAX_M 1e65; int prime_ary[MAX_M]; // 质数标记数组 int prime_pre[MAX_M]; // 前缀和数组 vectorint primes; // 质数容器 void init(int m) { fill(prime_ary2, prime_arym1, 1); for(int i2; im; i) { if(prime_ary[i]) primes.push_back(i); for(int p : primes) { if(p*i m) break; prime_ary[p*i] 0; if(i%p 0) break; } } for(int i1; im; i) prime_pre[i] prime_pre[i-1] prime_ary[i]; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; init(m); while(n--) { int l, r; cin l r; if(rm || l1) { cout Crossing the line\n; continue; } cout prime_pre[r] - prime_pre[l-1] \n; } return 0; }4. 算法复杂度分析预处理阶段线性筛O(m)前缀和计算O(m)查询阶段每次查询O(1)n次查询O(n)总时间复杂度O(m n)完全满足题目要求。5. 常见问题与调试技巧5.1 内存分配问题当m1e6时数组大小需要略大于1e6以避免越界。建议const int MAX_M 1e65; // 多分配一些空间5.2 输入输出优化对于大规模数据建议关闭同步流加速IOios::sync_with_stdio(false); cin.tie(nullptr);5.3 特殊边界测试用例测试时应特别注意以下情况l1的查询rm的查询包含2的区间最小的质数大范围查询如[1,1e6]非法查询如[0,10]或[5,1e61]5.4 欧拉筛常见错误新手容易犯的错误忘记初始化标记数组内层循环缺少break条件质数判断错误地将1视为质数数组大小设置不足导致越界6. 算法扩展与变种思考6.1 支持更大范围的查询如果m扩大到1e8甚至更大可以考虑分段筛法使用bitset压缩存储空间多线程并行处理6.2 统计其他数论函数类似思路可用于统计区间内素数幂次的数量区间内特定形式的素数如孪生素数区间内数的最大/最小质因子6.3 在线算法优化如果查询区间可能超出预处理范围可以考虑Miller-Rabin素性测试概率性算法预先计算质数密度近似值在实际编程竞赛训练中我发现这类数论问题最关键的突破点往往在于识别出问题可以转化为前缀和差分的形式。预处理的思想在算法竞赛中极为常见掌握好线性筛这类基础算法能为解决更复杂的问题打下坚实基础。

相关推荐

CTF网络流量分析:中间人攻击与密码破解实战
CTF网络流量分析:中间人攻击与密码破解实战

1. 题目背景与基本概念"john-in-the-middle"是BUUCTF平台Misc(杂项)类别中的一道CTF题目。这道题目属于网络流量分析类题型,主要考察参赛者对网络协议、中间人攻击原理以及相关工具使用的掌握程度。在CTF比赛中,Miscell… · 2026/11/2 17:36:30

AI写3D游戏实测:Step 5、DeepSeek与GLM5.3横评及vLLM部署
AI写3D游戏实测:Step 5、DeepSeek与GLM5.3横评及vLLM部署

我平时主要做游戏工程化和 AI 应用落地,日常免不了拿各种模型写代码。最近看到新一代模型讨论很多,有人问 Step 5 Preview、DeepSeek V4 Pro、GLM5.3 这种模型到底能不能真的“做游戏”。我干脆做了一次横评:同一份 3D 游戏需求,分… · 2026/11/2 17:35:29

AMBA ACE缓存一致性详解:侦听通道、事务类型与五态模型
AMBA ACE缓存一致性详解:侦听通道、事务类型与五态模型

多核系统里最让人头大的一类bug,是那种"代码逻辑看起来毫无问题、单核跑得好好的、一上多核就偶发读到旧值"的问题。我见过最典型的一次是某开发者在调试一个共享缓冲区场景:DMA侧明明已经写完并且置了标志位,CPU侧读到的却还是上一… · 2026/11/2 17:35:29

深入理解try-catch异常处理机制与最佳实践
深入理解try-catch异常处理机制与最佳实践

1. 异常处理机制的本质与价值在编程实践中,错误和异常无处不在。从文件读取失败到网络请求超时,从空指针引用到数组越界,这些意外情况随时可能中断程序的正常执行流程。异常处理机制正是为了解决这类问题而诞生的编程范式,它允许开… · 2026/11/3 3:44:37

水电站数字化改造:振动声纹与多物理场分析提升5%发电效率
水电站数字化改造:振动声纹与多物理场分析提升5%发电效率

1. 老旧电站的"盲维"困境:看不见的5%收益去哪了?在电力行业摸爬滚打十几年,我发现一个有趣的现象——许多运行超过15年的老电站,明明设备没坏、发电量报表也正常,但实际收益总比设计值低5%左右。这个数字就像… · 2026/11/3 3:44:37

风暴事件影像数据集拆解:多源数据清洗与防泄漏划分
风暴事件影像数据集拆解:多源数据清洗与防泄漏划分

做极端天气相关影像任务的人,往往栽在第一步:拿到一份 Storm Event Imagery Dataset,看它有分类目录、有标签文件,直接套一个现成的骨干网络跑训练,验证集准确率九十几,交差时信心满满,一上真实… · 2026/11/3 3:44:37

LeetCode Hot100打卡:算法刷题技巧与实战经验
LeetCode Hot100打卡:算法刷题技巧与实战经验

1. 项目概述"hot100打卡——day10"这个标题看似简单,却蕴含着程序员群体中一个非常流行的学习方式——算法刷题打卡。作为一名经历过校招和跳槽的老程序员,我深知坚持刷题的重要性,也明白大多数人最难的就是保持每日练习的节奏。ho… · 2026/11/3 3:44:37

大模型微调必备:Conda虚拟环境搭建与管理指南
大模型微调必备:Conda虚拟环境搭建与管理指南

1. 虚拟环境:大模型微调的第一道防线在开始大模型微调之前,环境隔离是每个开发者必须重视的基础工作。我见过太多因为环境冲突导致项目失败的案例——某个依赖库版本不兼容,或者系统Python环境被污染,都可能让后续的微调工作功亏一… · 2026/11/3 3:44:37

DeepSeek本地部署:Ollama+ChatBox跑通7B模型
DeepSeek本地部署:Ollama+ChatBox跑通7B模型

简介:这是一份面向 DeepSeek 使用者的本地部署教程文档,适合对在线服务稳定性不满、重视隐私与响应延迟的爱好者及有一定操作经验的人士,用于在网络拥堵或服务不可用时保障研究和工作连续进行,并兼顾个人隐私保护与本地响应速度。… · 2026/11/3 3:43:37

双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/2 13:10:28

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/2 4:42:45

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/2 5:17:18

STM32F411RE与MAX14431实现SPI隔离:工业现场抗共模干扰实战
STM32F411RE与MAX14431实现SPI隔离:工业现场抗共模干扰实战

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/3 1:01:59

ESP32+大模型AI硬件开发:从Demo到产品的8个工程问题
ESP32+大模型AI硬件开发:从Demo到产品的8个工程问题

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/3 1:01:59

基于MAX14431BAEE+与PIC18F85J10的SPI隔离方案设计与实践
基于MAX14431BAEE+与PIC18F85J10的SPI隔离方案设计与实践

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/3 1:01:59

双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/2 13:10:28

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/2 4:42:45

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/2 5:17:18

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码