质数筛选法
文章目录
前言
当需要大范围内的素数时,例如
1
e
6
1e6
1e6以内时，我们就需要优秀的筛选法，如果是枚举(1 ~ n)数做朴素的判断x是否能被 2 ~
x
\sqrt{x}
x
中的数整除，x 从 2 ~ n, 复杂度就太高了,估算约
O
(
2
+
3
+
.
.
.
+
n
−
1
+
n
)
O(\sqrt{2} + \sqrt{3} + ... + \sqrt{n-1} + \sqrt{n})
O(2
+3
+...+n−1
+n
)
势必超时，但早在几百多年前就有两位伟大的数学家发明出了埃氏筛
O
(
n
l
o
g
l
o
g
n
)
O(nloglogn)
O(nloglogn)和欧拉筛
O
(
n
)
O(n)
O(n)
两者在
1
e
6
1e6
1e6范围内效果相当,但到了
1
e
7
1e7
1e7上埃氏筛就显得乏力了。
预备知识 : 算数基本定理
简单的说一个大于1的数一定可以由若干个质数相乘得到例如：
8
=
2
∗
2
∗
2
8 = 2 * 2 * 2
8=2∗2∗2
一、埃氏筛 O ( n l o g l o g n ) O(nloglogn) O(nloglogn)
//利用2 3 5 7 11 13...这些质数筛掉(2x, 3x, 5x, 7x, 11x, 13x, ...)剩下的便是合数
const int N = 1e6 + 10;
bool prime[N];
void prepare(int n)
{
prime[0] = prime[1] = true; //0和1都不是质数
for(int i = 2; i <= n; ++i)
{
//prime[i] = flase 代表i是质数
if(!prime[i])
{
//将i的倍数都标记为合数,从两倍开始
for(int j = i << 1; j <= n; j += i)
{
//prime[i] = true 代表j是合数
prime[j] = true;
}
}
}
}
总结：埃氏筛存在的缺点是一个合数可能会被多次筛选例如6会被2和3同时筛选（数据范围不超过 1 e 6 1e6 1e6影响不大），所以下面引出欧拉筛（线性筛选）
二、欧拉筛 O ( n ) O(n) O(n)
const int N = 1e6 + 10;
int cnt;
int primes[N]; //从小到大存下每个质数
bool st[N]; //false为质数,true为合数
void get_primes(int n)
{
for(int i = 2; i <= n; ++i)
{
//将质数加入质数表
if(!st[i]) primes[cnt++] = i;
//利用最小质因子来给合数打标记,必须保证每个合数都是利用最小质因子筛选一次
for(int j = 0; primes[j] <= n / i; ++j)
{
st[i * primes[j]] = true; //primes[j]为构成i * primes[j] 的最小质因子
if(i % primes[j] == 0)
break;
//这段很关键,为什么要break掉,因为 i % primes[j] == 0
//说明 primes[j]是 i 的最小质因子, 令 i = k * primes[j]
//同时也是(i * primes[j+1]) 的最小质因子
//如果继续执行下层循环primes[i * primes[j+1]] = true; 就说明筛选必定重复
//因为 i * primes[j+1] = (k * primes[j]) * primes[j+1];
//i * primes[j] 在i = (k * primes[j+1]) 时会被筛选
}
}
}
总结
我对素数筛选法的理解大概是这样，只是欧拉筛确实还是有点难以理解，欧拉筛这里的内层循环判断结束也很有趣，可以分三种情况。
- primes[j] * i > n 说明范围内的素数已经被筛过，无需筛
- i % primes[j] == 0 break 分两种
-1. i 是合数, primes[j] 一定是小于i的最小质因数,
-2. i 是质数, primes[j] 为当前质数表里的最后一个质数且等于i，这里保证了 j 不会大于 cnt, 不会发生质数表越界