素数筛
素数筛是一种用于找出一定范围内所有素数的算法。
试除法
试除法是一种用于判断一个数是否为素数以及分解质因数的基本方法。
判断素数基本思想：对于给定的正整数 n，从 2 开始，依次用每个小于等于 $sqrt{n}$ 的正整数 i 去除 n，如果 n 能被 i 整除，那么 n 就不是素数；如果 n 不能被任何小于等于 $\sqrt{n}$ 的正整数整除，那么 n 就是素数。
1
2
3
4
5
6
7
8
9
10
11
12
vector<int> isPrime(n + 1, true);
bool isPrime_func(int num){
if(num < 2){
return false;
}
for(int i = 2; i * i <= num; i++){
if(num % i == 0){
return false;
}
}
return true;
}
埃氏筛
埃氏筛（埃拉托斯特尼筛法，Sieve of Eratosthenes）是一种用于找出一定范围内所有素数的经典算法。
埃氏筛的时间复杂度为 $O(n log log n)$，空间复杂度为 $O(n)$。这种算法通过避免对每个数都进行试除，大大提高了查找素数的效率。
使用埃氏筛前，要先初始化一个大小为 n+1 的数组 isPrime，并将其全部设置为 true。
1
2
3
4
5
6
7
8
9
10
11
vector<bool> isPrime(n + 1, true);
void getPrimes(int n){
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;
}
}
}
}
欧拉筛
欧拉筛是一种线性筛法，它是基于埃氏筛的改进。
