任何一个数都可拆成质数的幂的乘积形式

质因数相关公式

1(母问题).
$N = \prod_{i = 1}^{k} p_{i}^{a_{i}} = p_{1}^{a_{1}} \cdot p_{2}^{a_{2}} \cdots p_{k}^{a_{k}}$

2(子问题1).
$\text{约数个数：} \prod_{i = 1}^{k} (a_{i}+ 1)=(a_{1}+ 1)(a_{2}+ 1)\cdots(a_{k}+ 1)$

3(子问题2).
$\text{约数之和：} \prod_{i = 1}^{k} \sum_{j = 0}^{a_{i}} p_{i}^{j}=\prod_{i = 1}^{k}(p_{i}^{0}+p_{i}^{1}+\cdots + p_{i}^{a_{i}})$
$=(p_{1}^{0}+p_{1}^{1}+\cdots + p_{1}^{a_{1}})(p_{2}^{0}+p_{2}^{1}+\cdots + p_{2}^{a_{2}})\cdots(p_{k}^{0}+p_{k}^{1}+\cdots + p_{k}^{a_{k}})$

母问题：分解质因数(求数N的每个质因数及其指数)

acwing 867.分解质因数

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n ;
    cin >> n ;
    while (n --)
    {
        int x ;
        cin >> x ;
        map<int,int> h ;
        for (int i = 2 ; i <= x / i ; i ++)
        {
            while (x % i == 0)//执行while的i一定是质因数，不可能是合数
            {
                h[i] ++;
                x /= i ;//除尽质因数
            }
        }

        if (x > 1) h[x] ++ ; //特判一下

        for (auto [p , x] : h)
        {
            cout << p << ' ' << x << endl ;
        }
        cout << endl ;
    }
    return 0 ;
}

子问题1：约数个数(即每个(质因数的指数+1)的乘积)

acwing：3377.约数个数

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n ;
    cin >> n ;
    while (n --)
    {
        int x ;
        cin >> x ;

        unordered_map<int,int> h ;
        for (int i = 2 ; i * i <= x ; i ++)
        {
            while (x % i == 0) // 执行while的i一定是质因数
            {
                h[i] ++ ;
                x /= i ;//除尽质因数
            }
        }

        if (x > 1) h[x] ++ ;

        int res = 1 ;

        for (auto [v , c] : h)
            res *= (c + 1);

        cout << res << endl;
    }

    return 0;
}

子问题2：约数之和(每个(质因数前指数项等比求和后)的乘积)

acwing：871.约数之和

[分析]：
等比数列求和控制精度

long long t = 1 ;
while (x --)  t = (t*q+1)%MOD;//其中q为底数，x为最高次指数，MOD应该是一个取模的常量，用于在计算过程中避免数值过大，保证结果在一定范围内

1. 初始值：设初始时(x = n)

2. 第一次循环：
   当(x = n)时，
   $$t_1 = 1\times q + 1$$

3. 第二次循环：
   当(x = n - 1)时，
   $$t_2=(1\times q + 1)\times q + 1=1\times q^{2}+q + 1$$

4. 第三次循环：
   当(x = n - 2)时，
   $$t_3=(1\times q^{2}+q + 1)\times q + 1=1\times q^{3}+q^{2}+q + 1$$

5. 第四次循环：
   当(x = n - 3)时，
   $$t_4=(1\times q^{3}+q^{2}+q + 1)\times q + 1=1\times q^{4}+q^{3}+q^{2}+q + 1$$

6. 一般形式：
   经过(k)次循环（(k)从(0)到(x)），公式为
   $$t=\sum_{i = 0}^{k}q^{i}$$

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1e9 + 7 ;

int main()
{
    int n ;
    cin >> n ;

    unordered_map<int,int> h;
    while (n --)
    {
        int x ;
        cin >> x ;

        for (int i = 2 ; i <= x / i ; i ++)
        {
            while (x % i == 0)
            {
                h[i] ++ ;
                x /= i ;
            }
        }

        if (x > 1) h[x] ++;
    }

    long long res = 1 ;
    for (auto [q , x] : h)
    {
        long long t = 1 ;
        while (x --)  t = (t * q + 1) % MOD ;//底数为q , 最高次指数为x的等比求和
        res *= t ;
        res %= MOD ;
    }

    cout << res << endl;

    return 0 ;
}

筛质数：

acwing：868.筛质数（线性筛质数）

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6+10;

int primes[N] , cnt ; //primes存储质数，cnt记录质数个数
bool st[N];

void get_primes(int n)
{
    for (int i = 2 ; i <= n ; i ++)
    {
        if (!st[i]) primes[cnt ++] = i ;
        for (int j = 0 ; primes[j] * i <= n ; j ++)
        {
            st[primes[j] * i] = true; //用最小质因子筛选
            if (i % primes[j] == 0) break; //已找到i的最小质因子，不用再重复筛选
        }

    }
}

int main()
{
    int n ;
    cin >> n ;
    get_primes(n);
    cout << cnt << endl; 
    return 0 ;
}

acwing：866.试除法筛质数

#include <bits/stdc++.h>

using namespace std;

void is_div(int n)
{   
    if (n < 2) 
    {
        cout << "No" << endl;
        return ;
    }

    for (int i = 2 ; i <= n / i ; i ++)
    {
        if (n % i == 0) 
        {
            cout << "No" << endl;
            return ;
        }
    }

    cout << "Yes" << endl;
    return ;
}

int main()
{
    int n ;
    cin >> n ;
    while (n --)
    {
        int x ;
        cin >> x ;

        is_div(x);
    }

    return 0 ;
}