欧拉筛素数及积性函数

欧拉筛素数

int Prime[N], tot;
bool Not[N];//true 则 i 不是素数
void GetPrime(const int& n = N - 1) {
    Not[1] = true;
    for (int i = 2; i <= n; ++i) {
        if (!Not[i]) Prime[++tot] = i;
        for (int j = 1; j <= tot && i * Prime[j] <= n; ++j) {
            Not[i * Prime[j]] = true;
            if (i % Prime[j] == 0) break;
        }
    }
}

常见的积性函数

/*
 *@  Prime[i]   : 第i个素数
 *@  mv[i]      : i的最小质因子
 *@  f[i]       : 积性函数
质数的最小质因子为它本身
*/
int Prime[N], mv[N], tot;
void GetPrime(const int& n = N - 1) {
    // f[1]=1;
    for (int i = 2; i <= n; ++i) {
        if (!mv[i]) {
            Prime[++tot] = i;
            mv[i] = i;
            // f[i]=...;
        }
        for (int j = 1; j <= tot && i * Prime[j] <= n; ++j) {
            mv[i * Prime[j]] = Prime[j];
            if (i % Prime[j] == 0) {
                // f[Prime[j]*i]=...;
                break;
            }
            //f[i * Prime[j]] = f[i] * f[Prime[j]];
        }
    }
}

常见的积性函数全家桶

/*
 *@ Prime[i]     :第i个素数
 *@ mv[i]        :i的最小质因子(判断是否为素数)
 *@ sigma0[i]    :i的约数个数和
 *@ sigma1[i]    :i的约数的和
 *@ phi[i]       :欧拉函数[1,i]中与i互质的数的个数
 *@ mobius[i]    :i的莫比乌斯函数
 */
constexpr int M = static_cast<int>(1e7 + 5);
int Prime[M], sigma0[M], sigma1[M], mv[M], mobius[M], phi[M], tot;
void GetPrimeAll(const int& n = M - 1) {
    sigma0[1] = sigma1[1] = phi[1] = mobius[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (!mv[i]) {
            Prime[++tot] = i;
            mv[i] = i;
            sigma0[i] = 2;
            sigma1[i] = i + 1;
            phi[i] = i - 1;
            mobius[i] = -1;
        }
        for (int j = 1; j <= tot && i * Prime[j] <= n; ++j) {
            mv[i * Prime[j]] = Prime[j];
            if (i % Prime[j] == 0) {
                sigma0[i * Prime[j]] = sigma0[i] * 2 - sigma0[i / Prime[j]];
                sigma1[i * Prime[j]] = sigma1[i] * (Prime[j] + 1) - Prime[j] * sigma1[i / Prime[j]];
                phi[i * Prime[j]] = phi[i] * Prime[j];
                mobius[i * Prime[j]] = 0;
                break;
            }
            sigma0[i * Prime[j]] = sigma0[i] * sigma0[Prime[j]];
            sigma1[i * Prime[j]] = sigma1[i] * sigma1[Prime[j]];
            phi[i * Prime[j]] = phi[i] * phi[Prime[j]];
            mobius[i * Prime[j]] = mobius[i] * mobius[Prime[j]];
        }
    }
}

普遍的积性函数

/*
 *@  Prime[i]   : 第i个素数
 *@  low[i]   : i的最小质因子的幂次值
 *@  mv[i]     : i的最小质因子
 *@  f[i]       : 积性函数
质数的最小质因子是它本身,即mv[i]=i
*/
int Prime[N], mv[N], low[N], tot = 0;
long long f[N];
void GetPrime(const int& n = N - 1) {
    f[1] = low[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (!mv[i]) mv[i] = i, Prime[++tot] = i, low[i] = i, f[i] = /*do something*/;  //质数处理
        for (int j = 1; j <= tot && i * Prime[j] <= n; ++j) {
            mv[i * Prime[j]] = Prime[j];
            if (i % Prime[j] == 0) {
                low[i * Prime[j]] = low[i] * Prime[j];
                f[i * Prime[j]] = low[i] == i ? /*do something*/ : f[i / low[i]] * f[low[i] * Prime[j]];
                //递推处理(找规律)
                break;
            }
            low[i * Prime[j]] = Prime[j];
            f[i * Prime[j]] = f[i] * f[Prime[j]];
        }
    }
}