埃氏筛法能否成？

📘 埃氏筛法（Eratosthenes Sieve）算法笔记 ✨ 目标与背景 我们希望高效求出小于等于 n 的所有质数（素数）。 相比朴素判断法（每个数都除一遍），埃氏筛法大大提高了效率，时间复杂度为 O(n log log n)，非常适合处理范围较大的质数筛选问题。 ✅ 核心思想 筛掉合数，留下质数。 从 2 开始，标记其为质数。 把所有 2 的倍数都标记为 非质数。 找下一个未被标记的数（如 3），认为它是质数，然后再标记它的倍数。 重复直到 √n。 📌 关键实现代码 vector<int> getPrimes(int n) { vector<bool> isPrime(n + 1, true); // 标记数组 vector<int> primes; isPrime[0] = isPrime[1] = false; // 0 和 1 不是质数 for (int i = 2; i <= n; i++) { if (isPrime[i]) { primes.push_back(i); // i 是质数 if ((long long)i * i <= n) { for (int j = i * i; j <= n; j += i) { isPrime[j] = false; // 标记 i 的倍数为合数 } } } } return primes; } 🧠 优化细节说明 ✅ for (int j = i * i; j <= n; j += i) 直接从 i² 开始标记，因为比 i² 小的倍数已经被更小的质数筛掉了。 如 2 的倍数 4, 6, 8... 从 2² 开始即可；而 6 = 2*3 已被 2 标记过。 ✅ (long long)i * i <= n 避免 int 类型乘法溢出，尤其是当 n 较大时。 🧪 示例：n = 10 初始： [T, T, T, T, T, T, T, T, T, T, T] // 0~10 变成： [F, F, T, T, F, T, F, T, F, F, F] 最终质数：2, 3, 5, 7 💡 时间与空间复杂度 时间复杂度： O(n log log n) 空间复杂度： O(n)（主要用于布尔标记数组） 对比朴素方法（每个数都除一遍），效率提升巨大。可以轻松处理 n ≈ 10^6。 📌 应用场景 筛选范围内所有质数（如欧拉函数、区间素数） 快速构造素数表用于后续操作（如试除法、分解因子） 作为“预处理”模块在很多算法题中非常实用 📝 心得体会 ✅ 筛法比起朴素判断法更高效、更优雅，是解决与质数有关问题的标配工具。 ✅ 优化起始点到 i*i 是算法的核心思想之一，也是避免冗余标记的关键。 ❗ 初次实现要注意防止溢出，建议用 long long 做乘法判断。 ✅ 延伸学习方向 欧拉筛（线性筛）：进一步优化到 O(n) 级别。 区间筛法：在大范围中筛选 [L, R] 区间的质数。