1. 筛法基础与质数判定
在计算机科学和数学领域,筛法是一种用于快速找出一定范围内所有质数的高效算法。质数(素数)是指大于1的自然数,除了1和它本身外没有其他正因数。理解质数的性质对于密码学、数据加密和算法优化等领域至关重要。
最基础的质数判定方法是试除法:对于一个数n,检查从2到√n的所有整数是否能整除n。这种方法的时间复杂度为O(√n),对于单个小数字尚可接受,但当需要处理大量数字或大范围时效率极低。
cpp复制bool isPrime(int n) {
if (n <= 1) return false;
for (int i = 2; i*i <= n; i++) {
if (n % i == 0) return false;
}
return true;
}
试除法的主要问题在于重复计算。例如,判断100是否为质数时,我们会检查2、4、5、10等因数,但实际上一旦发现2是因数(100÷2=50),就可以立即判定它不是质数,无需继续检查其他数。这种冗余计算在大规模问题中会显著降低效率。
提示:在实际编程中,对于n≤1的特殊情况需要单独处理,因为它们不符合质数的定义。同时,循环条件设为i*i≤n而非i≤√n,可以避免浮点数运算带来的精度问题。
需要模型API调用? 免费领10W Token,多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 埃拉托斯特尼筛法(埃筛)原理与实现
埃拉托斯特尼筛法(简称埃筛)是古希腊数学家埃拉托斯特尼提出的一种筛选质数的算法。其核心思想是从小到大遍历数字,每当遇到一个未被标记为非质数的数,就认定它是质数,并标记它的所有倍数为非质数。
算法步骤如下:
- 初始化一个布尔数组isPrime[0..n],初始时所有元素设为true
- 将isPrime[0]和isPrime[1]设为false(0和1不是质数)
- 从p=2开始遍历到√n:
- 如果isPrime[p]为true,则p是质数
- 将p的所有倍数(从p²开始)标记为false
- 最后,所有isPrime[i]为true的i都是质数
cpp复制void eratosthenesSieve(int n) {
vector<bool> isPrime(n+1, true);
isPrime[0] = isPrime[1] = false;
for (int p = 2; p*p <= n; p++) {
if (isPrime[p]) {
for (int i = p*p; i <= n; i += p) {
isPrime[i] = false;
}
}
}
// 输出质数
for (int i = 2; i <= n; i++) {
if (isPrime[i]) cout << i << " ";
}
}
埃筛的时间复杂度为O(n log log n),空间复杂度为O(n)。虽然比试除法高效很多,但它仍然存在一些效率问题:
- 同一个合数可能被多个质数标记为非质数(如6会被2和3都标记)
- 内存访问模式不连续,对缓存不友好
- 对于极大范围的n(如1e9以上),空间消耗成为瓶颈
注意:在实现埃筛时,内层循环可以从p²开始而非2p,因为更小的倍数已经被更小的质数标记过了。例如,当p=5时,10(5×2)已经被p=2标记过,15(5×3)已经被p=3标记过,所以直接从25(5×5)开始即可。
3. 欧拉筛(线性筛)的优化原理
欧拉筛(又称线性筛)是对埃筛的改进,确保每个合数只被它的最小质因数筛除一次,
