素数筛法

文章目录
  1. 1. Eratosthenes筛法:
  2. 2. Euler筛法

Eratosthenes筛法:

先用第一个质数2去筛,2留下,把2的倍数剔除掉。再用下一个素数,也就是3筛,把3留下,把3的倍数剔除掉。接下去用下一个素数5筛,把5留下,把5的倍数剔除掉。不断重复下去,最后剩下来的都是质数。

1
2
3
4
5
6
7
8
9
10
11
12
13
//判断前N个质数  
bool isPrime[N];
int prime[N/2], tot = 0;
memset(isPrime, true, sizeof(isPrime));
for (int i = 2; i <= N; i++) {
if (isPrime[i]) {
prime[tot++] = i;
// 把 i 的倍数都筛掉
for (int j = i*2; j <= N; j += i) {
isPrime[j] = false;
}
}
}

时间复杂度:$\mathcal{O}(nloglogn)$

但是Eratosthenes筛法存在一个问题,就是一个合数有可能会被多个质因子筛去。比如15,既会被3筛一遍,又会被5筛一遍,所以该算法还有进一步的提升空间。


Euler筛法

欧拉筛法是一种线性算法,保证每一个合数只被筛一次。比如15,现在只会被3筛掉,而不会被5再筛一遍。原因在于欧拉筛法只让每个合数被它最小的质因数筛掉。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool isPrime[N];
int prime[N/2], tot = 0;
memset(isPrime, true, sizeof(isPrime));
for (int i = 2; i <= N; i++) {
if (isPrime[i]) prime[tot++] = i;
for (int j = 0; j < tot; j++) {
//超过最大范围,跳出
if (i * prime[j] > N) break;
//将倍数筛除
isPrime[i * prime[j]] = false;
//保证只筛到以prime[j]为最小质因数的数
if (i % prime[j] == 0) break;
}
}

接下来做两点说明:

  • 保证每个合数都会被筛掉

    不妨将合数$x$做质因数分解,得到$x = p_{1}^{k1}p_{2}^{k2}\dots p_{m}^{km}$,其中$p_{i}$都是质数,并按从小到大排列。

    则合数$x$必然在 for循环枚举到 $i = p_{1}^{k1-1}p_{2}^{k2}\dots p_{m}^{km}$的时候,被质数$prime[j] = p_{1}$筛掉。

  • 保证每个合数只被筛一次

    假设存在另一个质因数$p_t$$(t\neq1)$也筛掉了$n$,那么此时$i$就应该等于$p_{1}^{k1}p_{2}^{k2}\dots p_{t}^{kt-1}\dots p_{m}^{km}$。

    但注意到,$i$也被$p_1$整除,那么在内层for循环枚举$j$,当枚举到$prime[j] = p_1$时,便根据语句i % prime[j] == 0跳出内层循环,根本枚举不到$prime[j] = p_t$,让$p_t$筛掉$n$。

时间复杂度:$\mathcal{O}(n)$

分享到 评论