模板 - 线性筛-白红宇

模板 - 线性筛

阅读量：4681 次

发布时间：2019-06-09

本文共 1265 字，大约阅读时间需要 4 分钟。

质数筛

const int MAXN = 1e7;int p[MAXN], ptop;void sieve(int n) {    for(int i = 2; i <= n; i++) {        if(!p[i])            p[++ptop] = i;        for(int j = 1, t; j <= ptop && (t = i * p[j]) <= n; j++) {            p[t] = 1;            if(i % p[j])                ;            else                break;        }    }}

欧拉函数筛

其实判断!phi[i]就足够了，不过这样写统一一些。

const int MAXN = 1e7;int phi[MAXN];int p[MAXN], ptop;void sieve(int n) {    phi[1] = 1;    for(int i = 2; i <= n; ++i) {        if(!p[i])            p[++ptop] = i, phi[i] = i - 1;        for(int j = 1, t; j <= ptop && (t = i * p[j]) <= n; ++j) {            p[t] = 1;            if(i % p[j])                phi[t] = phi[i] * (p[j] - 1);            else {                phi[t] = phi[i] * p[j];                break;            }        }    }}

莫比乌斯函数筛

const int MAXN = 1e7;int mu[MAXN];int p[MAXN], ptop;void sieve(int n) {    mu[1] = 1;    for(int i = 2; i <= n; i++) {        if(!p[i])            p[++ptop] = i, mu[i] =  - 1;        for(int j = 1, t; j <= ptop && (t = i * p[j]) <= n; j++) {            p[t] = 1;            if(i % p[j])                mu[t] = -mu[i];            else {                mu[t] = 0;                break;            }        }    }}

转载于:https://www.cnblogs.com/Yinku/p/11450617.html

你可能感兴趣的文章