信息学奥赛实战：高效求解素数个数的两种经典算法
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。这时候可以考虑使用位运算来压缩存储空间或者分段处理。
相关新闻
2026/6/30 10:18:58
从炼铁到金融：8个真实案例拆解假设检验的核心步骤与决策逻辑
1. 假设检验的实战价值：从质量控制到金融决策 假设检验听起来很学术，但它的应用场景远比我们想象的广泛。我在工业生产线和金融风控部门都工作过，发现这套方法论简直是跨行业的"通用语言"。举个例子，炼铁厂要判断铁水含…
阅读更多
2026/6/30 10:18:58
质检复核电脑怎么审计？从报告附件、网页后台和远程协助看电脑监控软件
质检复核电脑经常打开检测报告、客户图片、质检系统、设备后台、导出表格和远程维护工具。问题出现时，单看业务系统状态往往不够，还要知道本地附件被怎样处理、网页后台是否被访问、是否有人远程介入。企业使用电脑监控软件前，应先把合法合规…
阅读更多
2026/6/30 10:13:58
终极QMK Toolbox指南：免费开源的机械键盘固件刷写神器
终极QMK Toolbox指南：免费开源的机械键盘固件刷写神器 【免费下载链接】qmk_toolbox A Toolbox companion for QMK Firmware 项目地址: https://gitcode.com/gh_mirrors/qm/qmk_toolbox QMK Toolbox是一款专为机械键盘爱好者设计的免费开源工具，它…
阅读更多
2026/6/30 11:49:10
nvm安装node没有自带npm如何解决
使用 nvm 安装 Node.js 后没有自带 npm，通常是因为网络问题导致 npm 包下载失败，或者环境变量配置不正确。 配置镜像源并重新安装 由于 npm 默认从国外服务器下载，极易因网络超时导致安装不完整。建议先配置国内镜像（如 npmmirr…
阅读更多
2026/6/30 11:49:10
畅玩3A大作游戏本排行！五款实力派机型横向深度对比
原创干货｜本文为个人实测客观观点，仅供购机参考。全文所有机型参数、实测数据、售价及售后政策，均来源于各品牌官方公开信息，无任何商业恰饭与利益关联，专门为刚需3A大作、纠结选机的玩家，整理出一份精准实…
阅读更多
2026/6/30 11:49:10
抖音无水印下载神器：douyin-downloader让你轻松保存任何视频
抖音无水印下载神器：douyin-downloader让你轻松保存任何视频 【免费下载链接】douyin-downloader A practical Douyin downloader for both single-item and profile batch downloads, with progress display, retries, SQLite deduplication, and browser fallback…
阅读更多
2026/6/30 11:49:10
3分钟掌握视频PPT提取：extract-video-ppt终极使用教程
3分钟掌握视频PPT提取：extract-video-ppt终极使用教程 【免费下载链接】extract-video-ppt extract the ppt in the video 项目地址: https://gitcode.com/gh_mirrors/ex/extract-video-ppt 你是否厌倦了从视频中手动截取PPT页面的繁琐过程？extra…
阅读更多
2026/6/30 11:49:10
北京海牙认证需要什么材料？北京海牙认证办理周期多久？
本文针对人在异地、身处境外或是没时间跑线下窗口的人群，详细拆解北京海牙认证的完整办理逻辑，从基础概念、适用场景，到所需材料、办理周期与费用明细，再到线下自办和线上小程序办理的两种实操路径，都做了清晰梳理。同…
阅读更多
2026/6/30 11:44:08
AMD Ryzen处理器终极调试工具：ZenStatesDebugTool完全指南
AMD Ryzen处理器终极调试工具：ZenStatesDebugTool完全指南 【免费下载链接】SMUDebugTool A dedicated tool to help write/read various parameters of Ryzen-based systems, such as manual overclock, SMU, PCI, CPUID, MSR and Power Table. 项目地址: https:…
阅读更多
2026/6/29 9:10:41
AI Coding 六个月真实ROI账本：产品经理的血泪教训，研发的冷静忠告
6个月前的2025年12月，Boris Cherny 公开宣布自己卸载了 IDE。一时间，Vibe Coding 成了全行业最热的话题。6个月后，当我们回过头来拉一份真实账本，发现事情远没有"一句话生成一个App"那么浪漫。本文从产品经理和研发两个…
阅读更多
2026/6/29 0:37:38
审计来了，数据权限全开——审计走了，怎么确保权限全部关掉？
引言：审计结束三个月了，审计员的权限还没关某城商行每年按照监管要求开展至少一次数据安全审计。审计期间，内审部门需要抽样检查各类业务数据——交易流水、客户信息、员工操作日志、权限配置记录。这些数据分布在不同系统中，审计…
阅读更多
2026/6/30 0:02:27
ChatGPT到底该选哪个版本？Plus够用还是Team更划算？资深架构师用18项硬指标告诉你真相
更多请点击： https://codechina.net 第一章：ChatGPT套餐选型的终极认知误区 许多技术决策者将 ChatGPT 套餐选型简化为“预算 vs. 用量”的线性权衡，却忽视了底层能力断层、上下文行为差异与 API 兼容性陷阱。这种思维定式导致大量团队在迁移…
阅读更多
2026/6/30 0:02:27
ChatGPT Plus取消订阅全流程实录（含截图级避坑手册）：从网页端/APP/iOS订阅管理入口→确认弹窗陷阱→Apple/Google Billing二次验证→到账时间追踪
更多请点击： https://kaifayun.com 第一章：ChatGPT Plus取消订阅的底层逻辑与风险全景图 ChatGPT Plus 的订阅机制并非简单的“开关式”服务绑定，而是深度耦合于 OpenAI 的账户生命周期管理、支付网关策略与 API 访问权限分级体系。取消订阅…
阅读更多
2026/6/30 0:02:27
NS-USBLoader：Switch玩家的终极游戏管理神器，3步搞定所有操作难题
NS-USBLoader：Switch玩家的终极游戏管理神器，3步搞定所有操作难题 【免费下载链接】ns-usbloader Awoo Installer and GoldLeaf uploader of the NSPs (and other files), RCM payload injector, application for split/merge files. 项目地址: https:…
阅读更多