1. 素数筛法入门:从暴力判断到高效筛选
在编程竞赛和算法学习中,素数筛法是一个绕不开的重要话题。我第一次接触筛法时,完全无法理解为什么需要这么"复杂"的方法来判断素数——毕竟用简单的除法判断看起来已经足够简单了。直到遇到需要处理十万甚至百万级别数据的问题时,我才真正体会到筛法的威力。
1.1 为什么需要筛法?
传统判断素数的方法是对每个数字n,检查2到√n之间是否有其因数。这种方法的时间复杂度是O(n√n),当n=10^6时,计算量将达到10^9级别,这在竞赛中绝对会超时。
而埃氏筛法的时间复杂度是O(nloglogn),线性筛更是达到了惊人的O(n)。举个例子,当n=10^6时:
- 暴力方法:约10^9次操作
- 埃氏筛:约3×10^6次操作
- 线性筛:约10^6次操作
这种效率差距在实际应用中意味着"能解"与"不能解"的区别。
1.2 埃氏筛的基本原理
埃氏筛(埃拉托斯特尼筛法)的核心思想是"标记非素数":
- 初始化一个布尔数组isPrime[],假设所有数都是素数
- 从2开始,如果当前数是素数,则标记它的所有倍数为非素数
- 重复这个过程直到√n,剩下的未标记数就是素数
关键优化点:
- 从i*i开始标记,因为更小的倍数已经被更小的素数标记过了
- 外层循环只需到√n,因为更大的数的倍数会超出n的范围
cpp复制// 典型埃氏筛实现
const int N = 1e6 + 10;
bool isPrime[N];
void eratosthenes(int n) {
fill(isPrime, isPrime + n + 1, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i <= n; ++i) {
if (isPrime[i]) {
for (int j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}
}
需要模型API调用? 免费领10W Token,多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 线性筛:更高效的素数筛选算法
2.1 线性筛的优势
埃氏筛虽然高效,但它有个明显的缺点
