信息学奥赛实战:高效求解素数个数的两种经典算法
1. 素数问题在信息学奥赛中的重要性素数判断与统计一直是信息学奥赛中的经典题型。这类题目看似简单但考察的是选手对算法效率的深刻理解。记得我第一次参加省赛时就遇到了一道需要统计10^6以内素数个数的题目。当时用最朴素的试除法结果程序运行超时惨痛教训让我意识到算法选择的重要性。素数在计算机科学中有着广泛的应用场景。从密码学中的RSA加密算法到哈希表的设计再到分布式系统中的一致性哈希素数的身影无处不在。在竞赛中常见的素数相关题目包括判断单个数是否为素数、统计区间内素数个数、寻找相邻素数对等。其中统计素数个数是最基础的题型也是其他复杂问题的基础。这类题目的难点在于如何在时间限制内完成大规模数据的处理。比如给定n10^6需要统计从2到n之间有多少个素数。直接使用试除法的话时间复杂度是O(n√n)在n较大时必然超时。这时候就需要更高效的筛法来解决。2. 试除法最直观的素数判断方法2.1 算法原理与实现试除法是最容易理解的素数判断算法。它的核心思想是如果一个数n不能被2到√n之间的任何整数整除那么它就是素数。这个结论基于一个简单的数学事实如果n有大于√n的因数那么它必然对应一个小于√n的因数。我们来看一个典型的实现代码bool isPrime(int n) { if(n 2) return false; for(int i 2; i sqrt(n); i) if(n % i 0) return false; return true; }这段代码有几个优化点值得注意只需要检查到√n而不是n-1先处理n2的特殊情况使用sqrt(n)作为循环终止条件而不是i*in这样可避免整数溢出2.2 性能分析与适用场景试除法的时间复杂度是O(√n)每次判断。当需要统计从2到n的所有素数时总时间复杂度为O(n√n)。这在n较小时比如n≤10^4表现尚可但当n增大到10^5甚至10^6时效率就会明显不足。我曾在一次模拟赛中做过测试在n10^5时试除法耗时约0.5秒而n10^6时耗时超过5秒这在竞赛中是无法接受的。因此试除法更适合以下场景只需要判断少量数字是否为素数题目给定的n较小通常n≤10^4作为更复杂算法的组成部分3. 筛法高效统计素数个数的利器3.1 埃拉托斯特尼筛法详解筛法Sieve是更高效的素数统计方法其中最经典的是埃拉托斯特尼筛法。它的基本思路是从2开始将每个素数的倍数都标记为合数这样剩下的就是素数。实现代码如下int countPrimes(int n) { vectorbool isPrime(n1, true); isPrime[0] isPrime[1] false; for(int i 2; i n; i) { if(isPrime[i]) { for(int j i*2; j n; j i) isPrime[j] false; } } int count 0; for(int i 2; i n; i) if(isPrime[i]) count; return count; }这个算法有几个关键优化点外层循环只需要到√n因为更大的数的倍数已经被更小的素数标记过了内层循环可以从ii开始而不是i2因为更小的倍数已经被处理过使用布尔数组而不是整数数组可以节省空间3.2 线性筛法及其优化埃氏筛法的时间复杂度是O(nloglogn)已经比试除法快很多。但还有一种更高效的欧拉筛法线性筛时间复杂度可以达到O(n)。线性筛法的核心思想是确保每个合数只被它的最小质因数筛掉一次。实现代码如下int countPrimes(int n) { vectorint primes; vectorbool isPrime(n1, true); for(int i 2; i n; i) { if(isPrime[i]) primes.push_back(i); for(int j 0; j primes.size() i*primes[j] n; j) { isPrime[i*primes[j]] false; if(i % primes[j] 0) break; } } return primes.size(); }这种算法特别适合需要同时获取素数表和统计素数个数的场景。在我的实际使用中当n10^7时埃氏筛法耗时约0.5秒而线性筛仅需0.2秒左右。4. 算法对比与实战选择4.1 时间复杂度与空间复杂度分析让我们用表格对比三种算法的性能算法时间复杂度空间复杂度适用场景试除法O(n√n)O(1)小规模数据(n≤10^4)埃氏筛O(nloglogn)O(n)中等规模(n≤10^7)线性筛O(n)O(n)大规模数据(n10^7)在实际比赛中还需要考虑代码实现的复杂度和调试难度。埃氏筛虽然理论复杂度不如线性筛但实现简单不易出错在大多数情况下已经足够。4.2 竞赛中的实战建议根据我的参赛经验给出以下建议对于n≤10^4的题目两种方法都可以试除法代码更简单对于10^4n≤10^7的题目优先选择埃氏筛对于n10^7的题目考虑使用线性筛如果题目需要频繁查询素数可以预处理素数表一个常见的优化技巧是预处理素数表。比如在程序开始时先用筛法生成素数表之后的所有查询都可以在O(1)时间内完成。这在需要多次查询的题目中特别有用。另外要注意内存限制。当n非常大时比如10^8布尔数组可能会占用较多内存约100MB。这时候可以考虑使用位运算来压缩存储空间或者分段处理。

相关新闻

思源宋体TTF:5个简单步骤掌握免费专业中文字体

思源宋体TTF:5个简单步骤掌握免费专业中文字体

思源宋体TTF:5个简单步骤掌握免费专业中文字体 【免费下载链接】source-han-serif-ttf Source Han Serif TTF 项目地址: https://gitcode.com/gh_mirrors/so/source-han-serif-ttf 还在寻找既美观又完全免费的中文字体吗?思源宋体TTF格式作为Adob…

2026/6/30 10:13:50阅读更多 →
React微前端构建实战:Node V8内存溢出排查与增量编译优化

React微前端构建实战:Node V8内存溢出排查与增量编译优化

1. 微前端架构下的React项目构建困境 最近在负责一个大型React微前端项目时,遇到了一个让人头疼的问题。项目采用阿里飞冰的icestark微前端解决方案,将系统拆分成多个独立模块。每个微模块单独开发、构建,最后集成到主应用中。这种架构带来了…

2026/6/30 10:13:50阅读更多 →
python爬虫实战项目|第86篇:爬虫系统日志与追踪

python爬虫实战项目|第86篇:爬虫系统日志与追踪

概述 日志和追踪是爬虫系统运维和调试的核心能力。一个完善的日志系统可以帮助开发者快速定位问题、分析性能瓶颈,而分布式追踪则可以追踪请求在多个服务间的流转。本篇文章将详细介绍爬虫系统的日志架构、日志级别管理、结构化日志、以及分布式追踪系统的设计与实现。 1. 日…

2026/6/30 10:13:50阅读更多 →
从零搭建ObjectARX开发环境:SDK与Wizards实战配置指南

从零搭建ObjectARX开发环境:SDK与Wizards实战配置指南

1. 环境准备:从零认识ObjectARX开发 第一次接触CAD二次开发的朋友可能会被ObjectARX这个名词吓到,其实它就像乐高积木里的专用连接件。想象一下,AutoCAD本身是个功能强大的玩具箱,而ObjectARX就是让你能够自己制作新零件的工具包。…

2026/6/30 11:24:24阅读更多 →
从零到一:在uni-app项目中优雅集成Pinia状态管理

从零到一:在uni-app项目中优雅集成Pinia状态管理

1. 为什么要在uni-app中使用Pinia? 第一次接触uni-app的状态管理时,你可能会有这样的疑问:既然uni-app已经内置了Vuex,为什么还要用Pinia?我刚开始也有同样的困惑,直到在实际项目中踩了几个坑才明白两者的区…

2026/6/30 11:24:24阅读更多 →
PG 日报|PG 排序性能优化,新增 UUID 聚合函数

PG 日报|PG 排序性能优化,新增 UUID 聚合函数

🔔 关注【IvorySQL开源数据库社区】即可获取 PostgreSQL 一手干货与最新动态⚙️ PostgreSQL技术文章 🧩 在满足欧盟数据主权要求的同时加快创新步伐2026年6月,欧盟委员会发布European Tech Sovereignty一揽子政策,将数据主权提升…

2026/6/30 11:24:24阅读更多 →
Borderless Gaming终极指南:三步实现游戏无边框窗口化的完美解决方案

Borderless Gaming终极指南:三步实现游戏无边框窗口化的完美解决方案

Borderless Gaming终极指南:三步实现游戏无边框窗口化的完美解决方案 【免费下载链接】Borderless-Gaming Play your favorite games in a borderless window; no more time consuming alt-tabs. 项目地址: https://gitcode.com/gh_mirrors/bo/Borderless-Gaming…

2026/6/30 11:24:24阅读更多 →
5分钟免费为Windows换上macOS鼠标指针:终极美化指南

5分钟免费为Windows换上macOS鼠标指针:终极美化指南

5分钟免费为Windows换上macOS鼠标指针:终极美化指南 【免费下载链接】macOS-cursors-for-Windows Tested in Windows 10 & 11, 4K (125%, 150%, 200%). With 2 versions, 2 types and 3 different sizes! 项目地址: https://gitcode.com/gh_mirrors/ma/macOS-…

2026/6/30 11:24:24阅读更多 →
服装零售数字化下半场:为什么你的收银系统需要一次“AI进化”?

服装零售数字化下半场:为什么你的收银系统需要一次“AI进化”?

阅读提示:本文从技术代际差角度,拆解当前服装收银系统的两大流派。如果你正在寻找真正能拉动增长的服装收银系统推荐,这篇文章会帮你建立一个清晰的“避坑”框架。一、你的收银系统是“成本中心”还是“利润中心”?中国服装零售已…

2026/6/30 11:19:24阅读更多 →
AI Coding 六个月真实ROI账本:产品经理的血泪教训,研发的冷静忠告

AI Coding 六个月真实ROI账本:产品经理的血泪教训,研发的冷静忠告

6个月前的2025年12月,Boris Cherny 公开宣布自己卸载了 IDE。一时间,Vibe Coding 成了全行业最热的话题。6个月后,当我们回过头来拉一份真实账本,发现事情远没有"一句话生成一个App"那么浪漫。本文从产品经理和研发两个…

2026/6/30 4:03:30阅读更多 →
审计来了,数据权限全开——审计走了,怎么确保权限全部关掉?

审计来了,数据权限全开——审计走了,怎么确保权限全部关掉?

引言:审计结束三个月了,审计员的权限还没关某城商行每年按照监管要求开展至少一次数据安全审计。审计期间,内审部门需要抽样检查各类业务数据——交易流水、客户信息、员工操作日志、权限配置记录。这些数据分布在不同系统中,审计…

2026/6/30 4:36:27阅读更多 →
为什么你需要Destiny 2 Solo Enabler:技术原理与实战指南

为什么你需要Destiny 2 Solo Enabler:技术原理与实战指南

为什么你需要Destiny 2 Solo Enabler:技术原理与实战指南 【免费下载链接】Destiny-2-Solo-Enabler Repo containing the C# and XAML code for the D2SE program. Included is also the dependency for the program, and image asset. 项目地址: https://gitcode…

2026/6/30 0:02:58阅读更多 →
第六章:PowerPoint 2010 核心功能与实战应用 —— 从入门到精通

第六章:PowerPoint 2010 核心功能与实战应用 —— 从入门到精通

1. PowerPoint 2010基础操作全攻略 刚接触PowerPoint 2010时,很多人会被它复杂的界面吓到。其实只要掌握几个核心区域,就能快速上手。我最开始用PPT时,经常找不到功能按钮在哪,后来发现主要操作都集中在顶部功能区。 工作窗口主要…

2026/6/30 0:02:58阅读更多 →
XGBoost超参数实战:从理论到调优策略

XGBoost超参数实战:从理论到调优策略

1. XGBoost超参数基础认知 第一次接触XGBoost时,我被它那密密麻麻的参数列表吓到了。这感觉就像面对一架波音747的驾驶舱——每个按钮都可能有神奇的效果,但按错了就可能坠机。经过多年实战,我发现其实掌握十几个核心参数就能解决90%的问题。…

2026/6/30 0:02:59阅读更多 →