质数

// 原理 每个合数都是由其最小质数所筛去
vector<int> euler_sieve(int n) {  // 求n及以内的质数
    vector<int> p;                // 质数集合
    vector<int> cp(n + 1);        // cp[i] i为合数
    for (int i = 2; i <= n; i++) {
        if (cp[i] == 0)
            p.push_back(i);
        for (int j = 0; 1LL * p[j] * i <= n; j++) {
            cp[p[j] * i] = 1;
            if (i % p[j] == 0)
                break;
        }
    }
    for (int i : p) {
        cout << i << " ";
    }
    cout << "\\n";
    return p;
}

对于每个数$i$，我们遍历不超过$i$的最小质因子的质数$p_j$，显然$p_ji$的最小质因子就是$p_j$，我们将$p_ji$标记和合数，那么所有的合数标记的次数是$O(n)$的

最小质因子

vector<int> least_prime_factor(int n) {  // 求n及以内的所有数的最小质因子
    vector<int> p;                       // 质数集合
    vector<int> lpf(n + 1);              // lpf[i] i的最小质因子
    for (int i = 2; i <= n; i++) {
        if (lpf[i] == 0) {
            p.push_back(i);
            lpf[i] = i;
        }
        for (int j = 0; 1LL * p[j] * i <= n; j++) {
            lpf[p[j] * i] = p[j];
            if (i % p[j] == 0)
                break;
        }
    }
    lpf[1] = 1;
    for (int i = 1; i <= n; i++) {
        // cout << i << " " << lpf[i] << endl;
        cout << lpf[i] << " ";
    }
    cout << "\\n";
    return lpf;
}

显然$p_ji$的最小质因子就是$p_j$，所以$lpf[p_ji] = p_j$

欧拉函数

欧拉函数φ(n)是小于或等于n的正整数中与n互质的数的数目，$\phi(n) = n \times \prod \limits_{i=1}^{s}\frac{p_i-1}{p_i}$，$p_i$是$n$的质因子

vector<int> euler_phi(int n) {  // 求n及以内的欧拉函数
    vector<int> p;              // 质数集合
    vector<int> phi(n + 1);
    for (int i = 2; i <= n; i++) {
        if (phi[i] == 0) {
            p.push_back(i);
            phi[i] = i - 1;
        }
        for (int j = 0; 1LL * p[j] * i <= n; j++) {
            phi[p[j] * i] = (p[j] - 1) * phi[i];
            if (i % p[j] == 0) {
                phi[p[j] * i] = p[j] * phi[i];  // i 的最小质因子是p[j]
                break;
            }
        }
    }
    phi[1] = 1;
    for (int i = 1; i <= n; i++) {
        // cout << i << " " << phi[i] << endl;
        cout << phi[i] << " ";
    }
    cout << "\\n";
    return phi;
}

莫比乌斯函数

$\mu(i) = \left \{ \begin{array}{ll} 1 & i = 0 \\ 0 & i中含重复质因子\\ (-1)^k & k为i的不同质因子个数 \end{array} \right.$

vector<int> mobius(int n) {  // 求n及以内的莫比乌斯函数
    vector<int> p;           // 质数集合
    vector<int> cp(n + 1);   // cp[i] i为合数
    vector<int> mu(n + 1);
    for (int i = 2; i <= n; i++) {
        if (cp[i] == 0) {
            mu[i] = -1;
            p.push_back(i);
        }
        for (int j = 0; 1LL * p[j] * i <= n; j++) {
            cp[p[j] * i] = 1;
            mu[p[j] * i] = -mu[i];
            if (i % p[j] == 0) {
                mu[p[j] * i] = 0;
                break;
            }
        }
    }
    mu[1] = 1;
    for (int i = 1; i <= n; i++) {
        // cout << i << " " << mu[i] << endl;
        cout << mu[i] << " ";
    }
    cout << "\\n";
    return mu;
}

约数个数

$d(n) = \prod \limits_{i=1}^{s}(p_i+1)$

vector<int> cnt_divisor(int n) {  // 求1到n的每个数各自的约数个数
    vector<int> p;                // 质数集合
    vector<int> cp(n + 1);        // cp[i] i为合数
    vector<int> lpf_cnt(n + 1);   // lpf_cnt[i] i的最小质因数的个数
    vector<int> div(n + 1);       // div[i] i的约数个数
    for (int i = 2; i <= n; i++) {
        if (cp[i] == 0) {
            p.push_back(i);
            lpf_cnt[i] = 1;
            div[i] = 2;
        }

        for (int j = 0; 1LL * p[j] * i <= n; j++) {
            cp[p[j] * i] = 1;
            // i不含质因子p[j]，所以p[j]*i的最小质因子个数为1
            lpf_cnt[p[j] * i] = 1;
            // 新增一个从未出现的质数p[j]，之前的因数都可以乘以p[j]产生新的因子
            div[p[j] * i] = div[i] * 2;
            if (i % p[j] == 0) {
                lpf_cnt[p[j] * i] = lpf_cnt[i] + 1;
                // div[p[j]*i] = div[i] / (lpf_cnt[i]+1) * (lpf_cnt[i]+2)
                div[p[j] * i] =
                    div[i] / lpf_cnt[p[j] * i] * (lpf_cnt[p[j] * i] + 1);
                break;
            }
        }
    }
    div[1] = 1;
    for (int i = 1; i <= n; i++) {
        // cout << i << ' ' << div[i] << "\\n";
        cout << div[i] << " ";
    }
    cout << "\\n";
    return div;
}

约数的和

设n的质因子分解是$\prod \limits_{i=1}^{s}p_i^{\alpha_i}$，$a(n) = \prod \limits_{i=1}^{d}\sum \limits_{j=0}^{\alpha_i}p_i^{j}$

vector<ll> sum_divisor(int n) {  // 求1到n的每个数各自的约数的和
    vector<int> p;               // 质数集合
    vector<int> cp(n + 1);       // cp[i] i为合数
    // i的最小质因子为p，p的个数为s，则g[i] = p^0+p^1+p^2+...+p^s
    vector<ll> g(n + 1);
    vector<ll> div(n + 1);  // div[i] i的所有因子的和
    for (int i = 2; i <= n; i++) {
        if (cp[i] == 0) {
            p.push_back(i);
            g[i] = 1 + i;
            div[i] = 1 + i;
        }
        for (int j = 0; 1LL * p[j] * i <= n; j++) {
            cp[p[j] * i] = 1;
            g[p[j] * i] = p[j] + 1;
            div[p[j] * i] = div[i] * (p[j] + 1);
            if (i % p[j] == 0) {
                // p[j] 是i的最小质因子，若i有s个p[j]，现在有s+1个
                // g[i]*p[j]+1 = (p[j]^0+p[j]^1+...+p[j]^s)p[j]+1 = g[p[j]*i]
                g[p[j] * i] = g[i] * p[j] + 1;
                div[p[j] * i] = div[i] / g[i] * g[p[j] * i];
                break;
            }
        }
    }
    div[1] = 1;
    for (int i = 1; i <= n; i++) {
        // cout << i << ' ' << div[i] << "\\n";
        cout << div[i] << " ";
    }
    cout << "\\n";
    return div;
}