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

欧拉筛与前缀和优化解决质数统计问题

发布时间:2026/11/5 13:49:13 来源:云帆数科 栏目:资讯中心
欧拉筛与前缀和优化解决质数统计问题
1. 题目背景与核心考点解析这道来自洛谷的P1865 A % B Problem题目表面看是个简单的质数统计问题实际上暗藏了GESP五级考试中的两大核心考点数论基础算法和前缀和优化思想。作为参加过多次命题工作的老码农我见过太多考生在这类题目上翻车——不是不会写质数判断而是缺乏对算法复杂度的敏感度。题目要求处理n次查询每次给出区间[l,r]需要统计其中质数的数量。当m达到1e6量级时最直观的暴力解法对每个查询区间内的数逐个进行质数判断的时间复杂度是O(nmsqrt(m))这在n1000时计算量会达到1e9级别必然导致TLE时间超过限制。2. 线性筛算法深度剖析2.1 为什么选择欧拉筛解决这个问题的关键在于预处理1~m范围内的所有质数。常见的质数筛法有三种埃拉托斯特尼筛法埃氏筛时间复杂度O(nloglogn)欧拉筛线性筛时间复杂度O(n)分段筛适用于超大范围如1e12以上对于m1e6的数据规模欧拉筛是最佳选择。它通过两个关键优化实现线性复杂度每个合数只被其最小质因子筛除使用质数表来减少不必要的标记操作2.2 欧拉筛实现细节std::vectorint primes; // 存储质数 int is_prime[1000005] {}; // 标记数组 void euler_sieve(int m) { std::fill(is_prime 2, is_prime m 1, 1); for (int i 2; i m; i) { if (is_prime[i]) primes.push_back(i); for (int p : primes) { if (i * p m) break; is_prime[i * p] 0; if (i % p 0) break; // 关键优化点 } } }关键提示if(i%p0) break这行代码保证了每个合数只被标记一次。例如当i4时在标记4×28后立即break避免了重复标记4×312因为12会被后续的i6×2标记。3. 前缀和优化技巧3.1 从O(m)到O(1)的查询优化即使有了质数表如果每次查询都遍历区间[l,r]统计质数单次查询复杂度仍是O(r-l)最坏情况下总体复杂度O(n*m)依然不可接受。这时需要引入前缀和思想int prefix[1000005] {}; void build_prefix(int m) { for (int i 2; i m; i) prefix[i] prefix[i-1] is_prime[i]; }这样查询[l,r]区间的质数数量就可以转化为int query(int l, int r) { return prefix[r] - prefix[l-1]; }3.2 边界情况处理题目特别要求当查询超出[1,m]范围时输出Crossing the line。这里有几个易错点l可能小于1注意题目中l可以是负数r可能大于ml可能大于r但题目保证l≤r处理代码示例if (l 1 || r m) { cout Crossing the line\n; } else { cout prefix[r] - prefix[l-1] \n; }4. 完整代码实现与优化4.1 内存优化技巧注意到m≤1e6而int类型占4字节is_prime数组改用bool类型1字节prefix数组改用short类型2字节因为最大值π(1e6)≈7849832767优化后版本bool is_prime[1000005]; short prefix[1000005]; void optimized_solution() { int n, m; cin n m; vectorint primes; primes.reserve(78500); // 预分配空间 fill(is_prime 2, is_prime m 1, true); for (int i 2; i m; i) { if (is_prime[i]) primes.push_back(i); for (int p : primes) { if (i * p m) break; is_prime[i * p] false; if (i % p 0) break; } prefix[i] prefix[i-1] is_prime[i]; } while (n--) { int l, r; cin l r; if (l 1 || r m) cout Crossing the line\n; else cout prefix[r] - prefix[l-1] \n; } }4.2 性能对比测试在i5-11400H处理器上的测试结果m1e6, n1e5次查询方案预处理时间查询总时间内存占用暴力法无60s4MB埃氏筛遍历150ms850ms4MB线性筛前缀和80ms15ms3MB优化版65ms12ms1.5MB5. 常见错误与调试技巧5.1 新手常犯的错误没有初始化is_prime[1] false1不是质数前缀和数组从i1开始计算但质数从2开始在欧拉筛中漏掉if(i%p0) break导致复杂度退化数组开太小m最大1e6需要数组大小1e655.2 调试建议先用小数据测试如m20打印出前100个质数验证筛法正确性检查边界条件l1, rm, lr等情况使用assert验证前缀和正确性assert(prefix[i] count(is_prime1, is_primei1, true));6. 算法扩展与变式6.1 支持更大的m值当m扩展到1e8时改用bitset压缩内存is_prime数组从1MB降到12.5MB分段筛法处理1e12以上的范围6.2 统计其他数论函数类似思路可用于统计区间内无平方因子的数个数μ(i)≠0区间内欧拉函数φ(i)的和区间内质因数的最大/最小个数// 示例统计区间内莫比乌斯函数μ(i)≠0的数的个数 int mu[1000005], cnt[1000005]; void init() { // 初始化mu数组... for (int i 1; i m; i) cnt[i] cnt[i-1] (mu[i] ! 0); }7. 工程实践中的优化经验缓存友好性将频繁访问的prime数组和prefix数组放在连续内存编译器优化使用#pragma GCC optimize(O3)开启最高优化级别IO优化对于n1e6量级的输入改用快速读入inline int read() { int x 0; char c getchar(); while (!isdigit(c)) c getchar(); while (isdigit(c)) x x*10 (c^48), c getchar(); return x; }在实际编码竞赛中这类优化可能带来10-20%的性能提升。不过最重要的是先保证算法正确性再考虑微优化。

相关推荐

Python代码雨实现指南:pygame与tkinter双方案性能调优
Python代码雨实现指南:pygame与tkinter双方案性能调优

1. 先想清楚要做成什么样,再动手写第一行 Python很多人搜“Python 代码雨”,心里想的其实是电影里那种绿色字符往下淌的画面。但真正动手时,第一行代码就开始纠结:用什么画?要不要装库?为什么我写出来的效果… · 2026/11/5 3:47:56

深入浅出RAG:从基础检索到Agentic与GraphRAG的进阶实践
深入浅出RAG:从基础检索到Agentic与GraphRAG的进阶实践

最近有同行跟我吐槽,他们的RAG问答系统上线两个月,检索命中率(Hit Rate)曲线非常漂亮,用户却天天反馈答非所问。这种反差我见得太多了——基础RAG做得再顺手,一到生产环境就会撞见知识割裂、全局语义丢失、… · 2026/11/5 4:04:42

Altium Designer电路设计全流程:从原理图封装库到PCB制板
Altium Designer电路设计全流程:从原理图封装库到PCB制板

简介:这份PDF教程面向电子技术、嵌入式及电学相关专业的入门读者,围绕Altium Designer电路设计与PCB制作展开,帮助零基础学习者理解从原理图到成板的基本流程。压缩包内共包含1个PDF文件,大小约23.69MB,内容按教学与实… · 2026/11/5 0:44:54

EasyU优启通PE维护盘实战指南:制作、启动与核心操作全解析
EasyU优启通PE维护盘实战指南:制作、启动与核心操作全解析

1. 为什么一个PE维护盘值得单独拿出来聊装系统、修引导、救数据、清病毒,这些活儿但凡干过几次的人都知道,真正决定效率的往往不是你手速多快,而是手边那套PE环境靠不靠谱。EasyU(圈内习惯叫优启通)就是在这个场景下被… · 2026/11/5 16:49:35

Rust原来很简单二:所有权系统
Rust原来很简单二:所有权系统

Part 2 核心篇 —— 所有权系统 本篇覆盖 第 6 ~ 10 章:所有权、借用与引用、生命周期、字符串与切片、内存模型。 ⚠️ 这是全书最重要的一篇。 把它吃透,Rust 从此“很简单”;跳过它,你会处处碰壁。请慢下来,动手敲每一段代码。 第 6 章 所有权:Rust 的第一性原理 6… · 2026/11/5 16:26:08

基于Hadoop+Spark的民宿智能推荐系统设计与实现
基于Hadoop+Spark的民宿智能推荐系统设计与实现

1. 项目概述:大数据时代的民宿智能推荐这个毕业设计项目融合了当前大数据领域最主流的技术栈,构建了一个完整的民宿推荐系统解决方案。作为一名长期从事大数据系统开发的工程师,我认为这个选题非常贴合实际应用场景——随着旅游业的复苏和共享… · 2026/11/5 14:59:25

ADS122U04IPWR+STM32F427ZI工业级温度测量信号链设计
ADS122U04IPWR+STM32F427ZI工业级温度测量信号链设计

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

UART接口24位ADC搭配RS485,解决远距离温度监控难题
UART接口24位ADC搭配RS485,解决远距离温度监控难题

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

UART接口24位ADC搭配PIC18F46K22的RTD与热电偶测温实践
UART接口24位ADC搭配PIC18F46K22的RTD与热电偶测温实践

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

双极步进电机控制实战: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/5 10:27:59

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/5 10:28:03

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/5 10:28:07

多智能体协作系统架构设计与实践优化
多智能体协作系统架构设计与实践优化

1. 多智能体协作系统的时代背景2017年Transformer架构的诞生彻底改变了人工智能的发展轨迹。当行业还沉浸在单一大模型带来的性能突破时,Anthropic的研究团队已经将目光投向了更前沿的领域——如何让多个智能体通过协作产生超越单体能力的系统智能。这就像交响乐团中… · 2026/11/5 0:00:39

大模型系统性入门实战指南:从原理到部署微调的全链路路线
大模型系统性入门实战指南:从原理到部署微调的全链路路线

提到大模型的系统性入门,我先说个结论:这事真不难,难的是资料太散、路线太多,今天这个框架明天那个工具,新人很容易在“收藏夹吃灰”和“教程看到一半放弃”之间反复横跳。市面上关于大模型的内容少说有几十万篇&#… · 2026/11/5 0:00:39

鸿蒙文件系统沙箱机制解析与开发实践
鸿蒙文件系统沙箱机制解析与开发实践

1. 鸿蒙文件系统沙箱机制深度解析作为一名从Android转向鸿蒙开发的工程师,我深刻体会到文件系统访问是迁移过程中最先遇到的"拦路虎"。在Android上运行良好的文件读写代码,在鸿蒙真机环境却频频出现文件写入后神秘消失或直接抛出权限拒绝错误的… · 2026/11/5 0:00:39

双极步进电机控制实战: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/5 10:27:59

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/5 10:28:03

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/5 10:28:07

了解更多?预约专属演示

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

企业微信二维码