1. 从一道经典面试题说起为什么“数素数”不简单“请写一个函数输入整数n返回1到n之间素数的个数。”这大概是每个学过C/C的程序员在算法入门或面试准备时都绕不开的一道题。乍一看问题描述清晰得不能再清晰了似乎一个简单的循环加判断就能搞定。我第一次接触时也是这么想的结果写出来的代码在小数据量下跑得飞快一旦n超过10万程序就开始“思考人生”等到n是百万级别直接卡到让人怀疑人生。这让我意识到“数数”这个看似简单的动作在计算机科学里尤其是在处理“素数”这种具有特殊数学性质的序列时背后效率的差异可以是天壤之别。为什么判断一个数是不是素数这么“费劲”因为素数的定义决定了我们无法用简单的公式直接生成或批量验证。最朴素的想法是对于每个待判定的数m用2到sqrt(m)之间的所有整数去试除。只要有一个能整除m就不是素数。这个方法本身没问题但它的时间复杂度是O(n√n)。当n很大时这个开销是难以承受的。这就引出了我们今天要讨论的核心如何用更聪明、更高效的方法来“数”出这个范围内的素数个数而不是一个个笨拙地去“判断”。本文将带你深入探讨几种在C/C中求解1~n内素数个数的经典方法从最直观的暴力法到里程碑式的埃拉托色尼筛法简称埃氏筛再到其极致优化的产物——欧拉筛线性筛。我们不止步于给出代码更会拆解每一种方法背后的设计思想、时间与空间的权衡以及在实际编码中那些容易踩坑的细节。无论你是正在刷题巩固基础的学生还是需要在项目中处理数论相关问题的开发者相信这篇融合了原理与实战经验的总结都能给你带来收获。2. 方法一暴力试除法及其优化边界我们先从最直接的方法开始这能帮助我们建立基准并理解后续高级算法优化的必要性。2.1 基础暴力法的实现与性能瓶颈最直接的思路就是遍历2到n的每一个数i然后判断i是否为素数。判断素数isPrime(i)的函数则用2到sqrt(i)之间的整数去试除。#include stdio.h #include math.h #include stdbool.h bool isPrime(int num) { if (num 1) return false; int limit (int)sqrt(num); for (int i 2; i limit; i) { if (num % i 0) { return false; } } return true; } int countPrimes_bruteforce(int n) { int count 0; for (int i 2; i n; i) { if (isPrime(i)) { count; } } return count; }为什么试除的上界是sqrt(num)这是这个方法里第一个关键点。如果num是一个合数那么它一定可以表示为两个因子a * b的形式并且至少有一个因子小于或等于sqrt(num)。反证法如果两个因子都大于sqrt(num)那么它们的乘积必然大于num这与假设矛盾。因此我们只需要检查到平方根就足够了这能将判断单个数的复杂度从O(n)降到O(√n)。即便如此整个算法的复杂度依然是O(n√n)。我们可以简单估算一下当n1,000,000时最内层循环试除循环的执行次数大致是 n * √n 的数量级即约10^6 * 10^3 10^9次运算。在现代CPU上这也是一个需要数秒才能完成的任务显然无法接受。2.2 优化尝试跳过偶数与更精细的步长在进入“筛法”之前我们可以在暴力法上做一些显而易见的优化这些优化思想在后续筛法中也会用到。优化1跳过偶数。除了2以外所有偶数都不是素数。因此我们可以在外层循环中直接从3开始每次步进2i 2。同时在isPrime函数内部我们也可以只用奇数去试除因为偶数肯定不能整除奇数可以从3开始步进2。bool isPrime_opt(int num) { if (num 1) return false; if (num 2) return true; if (num % 2 0) return false; // 排除偶数 int limit (int)sqrt(num); for (int i 3; i limit; i 2) { // 只用奇数试除 if (num % i 0) { return false; } } return true; } int countPrimes_bruteforce_opt(int n) { if (n 2) return 0; int count 1; // 先把素数2算上 for (int i 3; i n; i 2) { // 只遍历奇数 if (isPrime_opt(i)) { count; } } return count; }这个优化大约能将速度提升一倍因为我们将需要判断的数字和试除的因子都减少了一半。但它的时间复杂度阶数依然是O(n√n)只是常数项变小了。对于百万级的n它仍然很慢。优化2使用6k±1规律。观察素数分布可以发现所有大于3的素数都位于6的倍数两侧即形式为6k-1或6k1。因为所有整数可以表示为6k, 6k±1, 6k±2, 6k±3其中6k, 6k±2, 6k±3都能被2或3整除只有6k±1可能是素数。我们可以利用这个规律进一步减少需要判断的数字和试除的因子。bool isPrime_opt2(int num) { if (num 1) return false; if (num 3) return true; if (num % 2 0 || num % 3 0) return false; int limit (int)sqrt(num); // 试除因子从5开始步长为6检查 i 和 i2 for (int i 5; i limit; i 6) { if (num % i 0 || num % (i 2) 0) { return false; } } return true; }这个优化能将效率再提升一些但代码复杂度增加了且依然没有改变O(n√n)的渐进复杂度。这些优化告诉我们一个道理在算法领域优化常数因子让程序快几倍是有用的但改变时间复杂度阶数让程序快几个数量级才是质变。暴力法的天花板就在这里要突破它我们必须换一种思路——筛法。注意在实际面试或编程中如果n非常小比如n10000这种优化后的暴力法完全够用且代码简单不易出错。但对于算法题常见的数据范围n up to 10^6, 10^7甚至更大我们必须掌握筛法。3. 方法二埃拉托色尼筛法——空间换时间的典范埃拉托色尼筛法Sieve of Eratosthenes是一种古老而优美的算法其核心思想不是去“判断”每个数而是主动“标记”出合数剩下的就是素数。这是一种典型的空间换时间的策略。3.1 算法原理与标准实现算法的过程就像过筛子假设我们要找出不超过n的所有素数。创建一个大小为n1的布尔数组isPrime[]初始化所有元素为true表示目前所有数都先认为是素数。从最小的素数2开始将其倍数4, 6, 8, ...在isPrime数组中标记为false即合数。然后找到下一个未被标记为false的数此时是3它一定是素数因为所有小于它的数的倍数都已经筛过了。重复步骤3标记3的所有倍数。如此反复直到我们处理的数p的平方大于n为止原因同暴力法中的sqrt边界。此时数组中所有仍为true的下标就是素数。#include stdio.h #include stdbool.h #include string.h // for memset int countPrimes_eratosthenes(int n) { if (n 2) return 0; bool isPrime[n 1]; // 初始化数组假设所有数都是素数 memset(isPrime, true, sizeof(isPrime)); isPrime[0] isPrime[1] false; // 0和1不是素数 // 核心筛法过程 for (int p 2; p * p n; p) { // 如果p是素数未被标记为合数 if (isPrime[p]) { // 从p*p开始标记p的倍数 for (int multiple p * p; multiple n; multiple p) { isPrime[multiple] false; } } } // 统计素数个数 int count 0; for (int i 2; i n; i) { if (isPrime[i]) { count; } } return count; }关键细节解读外层循环条件p * p n这是效率的关键。如果一个数x是合数那么它一定有一个不大于sqrt(x)的质因子。当我们用所有小于等于sqrt(n)的素数去筛过后所有不超过n的合数都已经被标记了。继续用大于sqrt(n)的素数去筛它的第一个倍数p*p已经大于n了所以循环不会执行因此可以提前结束。内层循环起始点multiple p * p为什么不是从2*p开始因为2*p, 3*p, ..., (p-1)*p这些数已经被比p更小的素数比如2, 3, ...筛过了。从p*p开始标记避免了重复工作。例如当p5时10(2*5)已经被p2筛过15(3*5)已经被p3筛过所以我们直接从25(5*5)开始筛。3.2 时间复杂度、空间复杂度与常见陷阱埃氏筛的时间复杂度是O(n log log n)。这个复杂度远优于O(n√n)。log log n是一个增长极其缓慢的函数当n10^9时log log n大约为3。因此埃氏筛在处理数千万甚至数亿级别的n时依然具有可行性。空间复杂度是O(n)因为我们需要一个大小为n1的布尔数组。对于C/Cbool或_Bool类型通常占用1字节。当n很大时例如10^8这需要大约100MB的内存这在许多竞赛环境或内存受限的场景下可能是个问题。一种常见的优化是使用位图bitset用1个比特位来表示一个数的状态这样可以将内存消耗降低到原来的1/8。在C中可以使用std::vectorbool或std::bitset在C中则需要手动进行位操作。常见陷阱与实操心得数组越界这是最易犯的错误。创建数组时大小是n1那么有效索引范围是0到n。在内层循环multiple p时必须确保multiple不会超过n循环条件multiple n保证了这一点。整数溢出外层循环条件p * p n。当n很大接近INT_MAX时p*p可能会溢出导致循环提前或不正确地终止。一个安全的写法是使用p n / p作为条件。for (int p 2; p n / p; p) { // 更安全的写法避免p*p溢出 if (isPrime[p]) { for (int multiple p * p; multiple n; multiple p) { isPrime[multiple] false; } } }忽略0和1一定要记得将isPrime[0]和isPrime[1]显式设置为false。性能热点对于非常大的n内层循环for (int multiple p * p; multiple n; multiple p)是绝对的性能热点。循环变量multiple和步长p都是整数CPU的整数运算单元可以高效处理。但访存模式对isPrime数组的写操作可能是随机的特别是当p较大时。不过由于我们总是顺序遍历multipleCPU缓存预取机制仍然能发挥不错的效果。埃氏筛已经非常高效但它仍然存在一个可以优化的地方重复标记。比如数字30它会被素数2、3、5各标记一次。当n极大时这些重复标记会带来额外的开销。能否让每个合数只被标记一次呢这就是欧拉筛要解决的问题。4. 方法三欧拉筛——线性复杂度的极致追求欧拉筛Euler‘s Sieve也称为线性筛它的目标是在O(n)的时间复杂度内完成筛选并且保证每个合数只被其最小的质因子筛掉一次。这是对埃氏筛的终极优化。4.1 核心思想用最小质因子筛除合数欧拉筛的精妙之处在于它维护了一个素数列表primes[]并始终确保用当前数字i和已知素数列表中的素数primes[j]的乘积来标记合数且必须在i % primes[j] 0时停止。算法步骤初始化一个布尔数组isPrime[]大小为n1全为true和一个空数组primes[]用于存放找到的素数。从2开始遍历到n记当前数字为i。如果isPrime[i]为true则将i加入primes列表。无论i是否为素数都遍历当前的素数列表primes记遍历到的素数为primes[j]。计算合数composite i * primes[j]。如果composite n则跳出内层循环。将isPrime[composite]标记为false。关键步骤如果i % primes[j] 0则跳出内层循环。遍历结束后isPrime[]中为true的下标即为素数primes[]列表本身也包含了所有素数。#include stdio.h #include stdbool.h #include string.h int countPrimes_euler(int n) { if (n 2) return 0; bool isPrime[n 1]; int primes[n 1]; // 足够存放所有素数 int primeCount 0; memset(isPrime, true, sizeof(isPrime)); isPrime[0] isPrime[1] false; for (int i 2; i n; i) { if (isPrime[i]) { primes[primeCount] i; // 将素数i加入列表 } // 遍历当前已找到的素数列表 for (int j 0; j primeCount; j) { long long composite (long long)i * primes[j]; // 防止溢出 if (composite n) { break; } isPrime[composite] false; // 核心如果i能被当前素数primes[j]整除则跳出循环 if (i % primes[j] 0) { break; } } } // 此时primeCount就是素数的个数 // 如果需要也可以遍历isPrime数组统计 return primeCount; }4.2 为什么是线性复杂度i % primes[j] 0的奥秘这是理解欧拉筛最核心也是最难的部分。为什么那个break如此重要它如何保证每个合数只被筛一次1. 核心定理每个合数x都有且仅有一个最小的质因子记为minPrimeFactor(x)。欧拉筛的目标就是让x在枚举到i x / minPrimeFactor(x)时被minPrimeFactor(x)这个素数筛掉。2. 内层循环的使命对于当前外层循环的i内层循环用i乘以素数列表primes[]中的每一个素数p去标记合数i*p。它试图让p成为合数i*p的最小质因子。3.break条件的作用当i % p 0时意味着p整除i。设i p * k。 * 此时我们正在标记合数i * p p * k * p p^2 * k。 * 对于这个合数i*p它的最小质因子是p吗是的因为i里已经包含了一个p。 * 如果我们不break继续用下一个更大的素数qq p去标记合数i * q p * k * q。对于这个合数i*q它的最小质因子是p因为i里包含p而不是q如果我们用q把它筛掉了那么未来当外层循环i等于(i*q)/p k*q时本应用最小质因子p来筛它却发现它已经被筛过了这就造成了重复筛选。 * 因此必须在i % p 0时break以保证每个合数i*p都是在i不包含比p更小的质因子时即p是i*p的最小质因子被p筛掉的。当i包含了pi*p的最小质因子就是p我们此刻已经完成了它的“唯一标记任务”后续更大的素数q不应该再插手。举例说明假设n20。当i2素数列表为[2]。标记2*24。i%20break。当i3素数列表为[2,3]。标记3*263*39。标记9后i%30break。当i4素数列表为[2,3]。标记4*28。此时i%20break。注意我们没有标记4*312。为什么因为12的最小质因子是2。它应该在未来i6时被p2筛掉6*212。如果现在用p3筛了12就重复了。当i5素数列表为[2,3,5]。标记5*2105*3155*52520跳出。i%50break。当i6素数列表为[2,3,5]。标记6*212。此时i%20break。我们没有标记6*318它的最小质因子是2应在i9时被p2筛掉等等9*218正确。通过这个机制每个合数x都只在i x / minPrimeFactor(x)且p minPrimeFactor(x)时被标记一次。外层循环i从2到n每个i的内层循环次数与i的质因子个数有关但均摊下来每个数无论是合数还是素数只被访问常数次因此总时间复杂度是O(n)。4.3 欧拉筛的优缺点与适用场景优点理论复杂度最优O(n)的线性时间复杂度当n极大时如10^7以上相比埃氏筛有显著优势。无重复标记每个合数只被筛一次减少了不必要的操作。副产品丰富在筛选过程中我们可以很容易地记录每个数的最小质因子这在解决许多数论问题如质因数分解、求欧拉函数时非常有用。缺点与注意事项代码复杂度高逻辑比埃氏筛复杂尤其是break条件的理解容易写错。空间开销略大除了isPrime数组还需要一个primes数组来存储素数列表。不过primes数组最大长度约为n / log(n)空间复杂度仍是O(n)。常数因子可能更大虽然复杂度是线性的但由于内层循环包含取模运算i % primes[j]而埃氏筛的内层循环只有简单的加法所以在n不是特别大比如n 10^6的时候经过良好优化的埃氏筛如使用位图、分段筛的实际运行速度可能更快因为它的操作更简单对CPU缓存更友好。整数溢出风险计算i * primes[j]时即使i和primes[j]都是int乘积也可能超过int范围。必须使用long long来存储中间结果并在判断composite n时使用long long比较。适用场景建议当问题不仅要求素数个数还要求每个数的最小质因子或者需要快速质因数分解时欧拉筛是首选。在算法竞赛中如果题目数据范围明确n很大如5e6以上且时间卡得很紧欧拉筛的线性优势更能体现。如果只是单纯求素数个数且n在1e7以下编写正确、高效的埃氏筛通常更简单、更不容易出错实际速度差异可能并不明显。5. 实战对比与进阶优化思路纸上得来终觉浅我们通过一个具体的例子并引入一些进阶技巧来看看这些方法在实战中如何选择。5.1 性能实测与数据对比假设我们分别用优化后的暴力法、埃氏筛、欧拉筛来求1到10,000,000一千万以内素数的个数。我们可以预期结果如下实际运行时间会因机器和实现细节而异方法时间复杂度预计时间 (n10^7)特点优化暴力法O(n√n)数分钟甚至更长完全不可行仅用于理解。埃拉托色尼筛法O(n log log n)~0.1 - 0.3秒实现简单内存访问模式规律易于优化。欧拉筛O(n)~0.05 - 0.15秒理论最快但代码稍复杂常数因子可能略高。实测心得在我的开发环境普通台式机上对于n10^7一个未经特殊优化的埃氏筛使用bool数组大约需要0.25秒。欧拉筛大约需要0.15秒。两者的差距在0.1秒左右。对于一次性的计算这个差距微不足道。但在一些在线判题系统中如果时间限制是1秒且有多个测试用例这0.1秒的优化可能就是通过与否的关键。5.2 埃氏筛的进阶优化位图与分段筛1. 位图优化如前所述用1个比特代替1个字节可以节省87.5%的内存。这对于处理超大范围的n例如10^8至关重要能让你在有限的内存下解决问题。C实现示例利用vectorbool的特化它通常是位实现的#include vector int countPrimes_eratosthenes_bitset(int n) { if (n 2) return 0; std::vectorbool isPrime(n 1, true); isPrime[0] isPrime[1] false; for (long long p 2; p * p n; p) { if (isPrime[p]) { for (long long multiple p * p; multiple n; multiple p) { isPrime[multiple] false; } } } return std::count(isPrime.begin(), isPrime.end(), true); }在C语言中需要手动操作位代码会复杂一些但原理相同。2. 分段筛Segmented Sieve当n大到无法在内存中同时容纳整个isPrime数组时比如n10^12分段筛就派上用场了。其思想是我们仍然需要sqrt(n)以内的素数表这个表很小然后将区间[2, n]分成若干个小段每次只将一个小段加载到内存中用已知的小素数去筛这个小区间。处理完一段再处理下一段。这样内存消耗只取决于段的大小而与n无关。分段筛的实现是埃氏筛思想的延伸代码更复杂但它突破了内存的限制是处理超大范围素数问题的利器。5.3 欧拉筛的细节陷阱与正确性验证在实现欧拉筛时以下几个细节必须注意溢出处理i * primes[j]必须用long long计算和比较。这是新手最容易忽略导致WAWrong Answer的地方。数组大小primes数组需要开多大素数定理指出不超过n的素数个数约为n / ln(n)。对于n10^7素数个数约62万所以开n1大小的数组是安全的虽然有点浪费。更精确的做法是估算大小例如int primes[(int)(1.2 * n / log(n)) 10]。正确性验证编写完欧拉筛后如何验证一个简单的方法是同时运行埃氏筛和欧拉筛对小数据如n1000比较结果是否一致。对于大数据可以输出第k个素数或素数个数与已知的素数表如查询网络进行对比。一个实用的调试技巧在欧拉筛的内层循环中可以打印出i,primes[j],composite观察每个合数是在哪一步被筛掉的特别是关注break发生时的状态这有助于理解算法的运作流程。6. 总结与选择建议回顾这几种方法它们体现了算法设计中典型的思维演进从直接模拟暴力法到利用规律批量处理埃氏筛再到追求极致效率、避免冗余欧拉筛。暴力法是理解的起点其优化跳过偶数、6k±1体现了基本的常数优化思想。仅适用于教学或极小数据范围n10,000。埃拉托色尼筛法是解决此类问题的主力军。它思想直观实现简单效率很高且易于进行位图、分段等高级优化以应对各种约束条件。在绝大多数需要求素数个数或素数表的场景下埃氏筛是你的首选。它的O(n log log n)复杂度在实践和理论之间取得了很好的平衡。欧拉筛是算法竞赛爱好者和对性能有极致要求场景下的利器。它提供了线性的理论复杂度并且能顺带求出最小质因子功能更强。但代码复杂度更高容易写错且在数据范围不是极大时其优势可能被更大的常数因子抵消。给开发者的最终建议面试与笔试如果只考素数计数通常期望你写出埃氏筛。如果能写出欧拉筛并讲清楚原理绝对是加分项。务必讲清楚sqrt优化和p*p起始点的原理。日常项目与算法竞赛如果只是单次、数据范围不大的计算写一个正确的埃氏筛就够了。如果数据范围很大n 10^7或者内存紧张优先考虑用位图优化的埃氏筛。如果问题需要频繁查询每个数的质因数相关信息或者在时间限制极其严格的竞赛中处理超大n那么欧拉筛是更好的选择。终极验证无论实现哪种算法一定要用边界值n0, 1, 2, 小数字和较大数字比如n1e6进行测试并与可靠来源的结果对比。对于欧拉筛要特别注意int溢出的问题。最后理解这些算法背后的数学思想——比如为什么用sqrt作为边界、为什么埃氏筛从p*p开始、欧拉筛如何保证唯一性——远比记住代码更重要。这些思想在解决其他问题时也许会给你带来意想不到的启发。