质数判断与埃拉托斯特尼筛法（算法入门笔记）
在做算法题时，经常会遇到这样的问题：
- 判断一个数是不是质数
- 统计某个区间内有多少个质数
- 找出 1～n 的所有质数
这时常见的两种方法是：
- 逐个判断质数
- 埃拉托斯特尼筛法（质数筛）
本文介绍它们的原理、代码以及适用场景。
一、什么是质数（素数）
质数（Prime Number) 定义：
大于 1 且只能被 1 和它本身整除的整数。
例如：
2 3 5 7 11 13 17 19 ...例如：
- 7 只能被 1 和 7 整除 → 是质数
- 8 可以被 2、4 整除 → 不是质数
不是质数的数称为 合数（Composite Number）。
特殊情况：
1 既不是质数，也不是合数二、判断单个数是否为质数
最简单的方法是：
从 2 到 √n 检查是否能整除。
为什么只需要检查到 √n？
因为如果：
n = a × b那么：
a ≤ √n 或 b ≤ √n所以只要找到一个小于等于 √n 的因子即可。
C++实现
bool isPrime(int n){
if(n < 2) return false;
for(int i = 2; i * i <= n; i++){
if(n % i == 0)
return false;
}
return true;
}时间复杂度
O(√n)例如：
n = 1000000
√n ≈ 1000最多需要循环 1000次。
三、当需要判断很多数字
如果我们需要：
判断 1 ~ 1000000 的所有质数如果使用 isPrime()：
1000000 × 1000 ≈ 10^9 次运算可能会 超时。
这时就需要使用 筛法。
四、埃拉托斯特尼筛法
埃拉托斯特尼筛法（Sieve of Eratosthenes）的核心思想：
如果一个数是质数，那么它的所有倍数一定不是质数。
例如：
找 1～20 的质数。
初始：
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20第一步
2 是质数。
划掉所有 2 的倍数：
4 6 8 10 12 14 16 18 20第二步
3 没被划掉 → 是质数。
划掉：
6 9 12 15 18第三步
4 已经被划掉 → 跳过。
第四步
5 是质数。
划掉：
10 15 20最后剩下：
2 3 5 7 11 13 17 19这些就是质数。
五、筛法 C++ 实现
const int N = 1000000 + 5;
bool isComposite[N];
for(int i = 2; i * i < N; i++){
if(!isComposite[i]){
for(int j = i * i; j < N; j += i)
isComposite[j] = true;
}
}说明：
isComposite[i] = true
表示 i 是合数如果：
isComposite[i] = false则：
i 是质数六、统计区间质数数量
很多题目会问：
[a,b] 区间有多少个质数可以使用 前缀和。
定义：
sum[i] = 1~i 的质数数量构建：
for(int i = 1; i < N; i++){
sum[i] = sum[i-1];
if(i >= 2 && !isComposite[i])
sum[i]++;
}查询：
[a,b] 的质数数量只需要：
sum[b] - sum[a-1]时间复杂度：
O(1)七、完整代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1000000 + 5;
bool isComposite[N];
int sum[N];
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
for(int i = 2; i * i < N; i++){
if(!isComposite[i]){
for(int j = i * i; j < N; j += i)
isComposite[j] = true;
}
}
for(int i = 1; i < N; i++){
sum[i] = sum[i-1];
if(i >= 2 && !isComposite[i])
sum[i]++;
}
int a,b;
while(cin >> a >> b){
cout << sum[b] - sum[a-1] << "\n";
}
}八、两种方法对比
| 方法 | 时间复杂度 | 适用场景 |
|---|---|---|
| 判断单个数 | O(√n) | 判断少量数字 |
| 筛法 | O(n log log n) | 判断大量数字 |
简单记忆：
判断一个数 → 试除法
判断很多数 → 筛法九、算法思想
筛法体现了一个非常重要的算法思想：
预处理（Precompute）先花时间计算出结果。
之后查询：
O(1)在算法竞赛中，这是一种非常常见的优化方法。
十、总结
质数问题在算法题中非常常见，通常有三种基本技巧：
1 判断质数（试除法）
2 质数筛（埃氏筛）
3 区间统计（前缀和）掌握这三个技巧，可以解决绝大多数基础质数问题。
版权所有
版权归属：PushTracer