【数学】线性筛

(i) 的最小质因数 (pm[i]) 。
(i) 的最大的最小质因数的幂 (pk[i]) 。

判断 (i) 是不是质数的充要条件为 (i>1 ; and ; pm[i]=i)

const int MAXN = 1e6 + 10;
int p[MAXN], ptop;
int pm[MAXN], pk[MAXN];

void sieve(int n) {
    memset(pm, 0, sizeof(pm[0]) * (n + 1));
    ptop = 0, pm[1] = 1, pk[1] = 1;
    for(int i = 2; i <= n; ++i) {
        if(!pm[i])
            p[++ptop] = i, pm[i] = i, pk[i] = i;
        for(int j = 1, t; j <= ptop && (t = i * p[j]) <= n; ++j) {
            pm[t] = p[j];
            if(i % p[j])
                pk[t] = pk[p[j]];
            else {
                pk[t] = pk[i] * p[j];
                break;
            }
        }
    }
}

数论函数

除数函数 (sigma_k(n)) ： (n) 的因子的 (k) 次方和，当 (k=0) 时，为 (n) 的因数个数 (d(n)) 。

(i) 的因数个数 (pd[i])。
(i) 的最大的最小质因数的幂 (pk[i]) 。

const int MAXN = 1e6 + 10;
int p[MAXN], ptop;
int pm[MAXN], pk[MAXN], pd[MAXN];

void sieve(int n) {
    memset(pm, 0, sizeof(pm[0]) * (n + 1));
    ptop = 0, pm[1] = 1, pk[1] = 1, pd[1] = 1;
    for(int i = 2; i <= n; ++i) {
        if(!pm[i]) {
            p[++ptop] = i, pm[i] = i;
            pk[i] = i, pd[i] = 2;
        }
        for(int j = 1, t; j <= ptop && (t = i * p[j]) <= n; ++j) {
            pm[t] = p[j];
            if(i % p[j]) {
                pk[t] = pk[p[j]];
                pd[t] = pd[i] * pd[p[j]];
            } else {
                pk[t] = pk[i] * p[j];
                pd[t] = (pk[t] == t) ? pd[t / p[j]] + 1 : pd[t / pk[t]] * pd[pk[t]];
                break;
            }
        }
    }
}

Euler函数：

const int MAXN = 1e6 + 10;
int p[MAXN], ptop;
int pm[MAXN], pk[MAXN], phi[MAXN];

void sieve(int n) {
    memset(pm, 0, sizeof(pm[0]) * (n + 1));
    ptop = 0, pm[1] = 1, pk[1] = 1, phi[1] = 1;
    for(int i = 2; i <= n; ++i) {
        if(!pm[i]) {
            p[++ptop] = i, pm[i] = i;
            pk[i] = i, phi[i] = i - 1;
        }
        for(int j = 1, t; j <= ptop && (t = i * p[j]) <= n; ++j) {
            pm[t] = p[j];
            if(i % p[j]) {
                pk[t] = pk[p[j]];
                phi[t] = phi[i] * phi[p[j]];
            } else {
                pk[t] = pk[i] * p[j];
                phi[t] = (pk[t] == t) ? t - t / p[j] : phi[t / pk[t]] * phi[pk[t]];
                break;
            }
        }
    }
}

Mobius函数

const int MAXN = 1e6 + 10;
int p[MAXN], ptop;
int pm[MAXN], pk[MAXN], mu[MAXN];

void sieve(int n) {
    memset(pm, 0, sizeof(pm[0]) * (n + 1));
    ptop = 0, pm[1] = 1, pk[1] = 1, mu[1] = 1;
    for(int i = 2; i <= n; ++i) {
        if(!pm[i]) {
            p[++ptop] = i, pm[i] = i;
            pk[i] = i, mu[i] = -1;
        }
        for(int j = 1, t; j <= ptop && (t = i * p[j]) <= n; ++j) {
            pm[t] = p[j];
            if(i % p[j]) {
                pk[t] = pk[p[j]];
                mu[t] = mu[i] * mu[p[j]];
            } else {
                pk[t] = pk[i] * p[j];
                mu[t] = (pk[t] == t) ? 0 : mu[t / pk[t]] * mu[pk[t]];
                break;
            }
        }
    }
}

任意的积性函数

分为1，质数，质数的幂三种不同情形，其他的用积性函数的性质得到。

const int MAXN = 1e6 + 10;
int p[MAXN], ptop;
int pm[MAXN], pk[MAXN], f[MAXN];

void sieve(int n) {
    memset(pm, 0, sizeof(pm[0]) * (n + 1));
    ptop = 0, pm[1] = 1, pk[1] = 1, f[1] = getF1();
    for(int i = 2; i <= n; ++i) {
        if(!pm[i]) {
            p[++ptop] = i, pm[i] = i;
            pk[i] = i, f[i] = getFp(i);
        }
        for(int j = 1, t; j <= ptop && (t = i * p[j]) <= n; ++j) {
            pm[t] = p[j];
            if(i % p[j]) {
                pk[t] = pk[p[j]];
                f[t] = f[i] * f[p[j]];
            } else {
                pk[t] = pk[i] * p[j];
                f[t] = (pk[t] == t) ? getFpk(t, p[j]) : f[t / pk[t]] * f[pk[t]];
                break;
            }
        }
    }
}