avatar

素数筛法学习笔记

素数筛法学习笔记

定义

  • 快速求出 1 n1 ~ n 中所有素数的方法。

埃氏筛

1
2
3
4
5
6
7
8

bool not_prime[1005];
memset(not_prime, 0, sizeof(not_prime));
not_prime[1] = true;
for(int i = 2; i <= n; i++)
if(!not_prime[i])
for(int j = i + i; j <= n; j += i)
not_prime[j] = true;

枚举每一个质数的倍数,并将其打上标记,时间复杂度为 OnloglognO{nloglogn}

欧拉筛

为了达到线性筛 O(n)O(n) 的复杂度,每个数都只能被筛掉一次。

xx 质因数分解,写为 x=p1r1p2r2pkrkx = p_1^{r_1} \cdot p_2^{r_2} \cdots p_k^{r_k} ,假设 p1<p2<<pkp_1 < p_2 < \cdots < p_k ,需要每个数都只被其最小的质因子 p1p_1 筛掉。

将已经筛出来的质数存在质数表里,对于一个数 ii ,从指数表逐一取出质数 pjp_j ,将 iipjp_j 倍筛去,直至 iipjp_j 的倍数或筛完质数表内的所有质数倍。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int prime[1005], pcnt;
bool not_prime[10005];
void euler(int n) {
not_prime[1] = true;
for(int i = 1; i <= n; i++) {
if(!not_prime[i]) prime[++pcnt] = i;
for(int j = 1; j <= pcnt; j++) {
int v = i * prime[j];
if(v > n) break;
not_prime[v] = true;
if(i % prime[j] == 0) break;
}
}
}

这样就保证了每一个数都只被最小的质因子晒掉,时间复杂度为 O(n)O(n)

文章作者: Ender
文章链接: https://www.ender.xin/post/aaa07adf.html
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Ender's blog
打赏
  • 微信和支付宝
    微信和支付宝

评论