整除问题：

1. 3的倍数：各个位上数字之和能被3整除
2. 2，5的倍数：个位数字能被2，5整除
3. 4的倍数：后两位能被4整除
4. 8的倍数：后三位能被8整除
5. 11的倍数：奇数位与偶数位的和之差能被11整除
6. 7，11，13的倍数：ABCDEFG -> ABCD ，EFG分别能被7，11，13整除

试除法判定质数 ~ O( sqrt(n) )

bool is_prime(int n)
{
    if (n < 2) return false;
    for (int i = 2; i <= n / i; i ++ ) // 注意用 i <= n / i;
        if (n % i == 0)
            return false;
    return true;
}

试除法分解质因数——底数，指数 ~ O( sqrt(n) )

void divide(int n)
{
    for (int i = 2; i <= n / i; i ++ )
        if (n % i == 0)
        {
            int s = 0;
            while (n % i == 0) {
                n /= i;
                s ++ ;
            }
            cout << i << ' ' << s << endl;  // i为质因数的底数，s为质因数的指数
        }
    if (n > 1) cout << n << ' ' << 1 << endl; // x最后大于1，剩下的是x中大于sqrt(x)的质因子
}

朴素筛法 / 埃式筛法 ~ O(nlog(logn))

在朴素筛法的过程中只用质数项去筛

int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (st[i]) continue;
        primes[cnt ++ ] = i;
        // 每次筛去所有质数的倍数，所有留下来的是质数
        for (int j = i + i; j <= n; j += i)
            st[j] = true;  // 重复标记，可以优化
    }
}

线性筛法

核心：1～n内的合数 pp 只会被其最小质因子筛掉.
原理：1～n 之内的任何一个合数一定会被筛掉，而且筛的时候只用最小质因子来筛，然后每一个数都只有一个最小质因子，因此每个数都只会被筛一次，因此线性筛法是线性的.

int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        // 如果不是质数加入到数表当中
        if (!st[i]) primes[cnt ++ ] = i;
        // 从小到大枚举所有的质数
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
           // 筛掉 primes[j] * i 这个合数
            st[primes[j] * i] = true; // primes[j] 一定小于i的所有质因子
            if (i % primes[j] == 0) break; //第一个出现break, primes[j] 是 i 的最小质因子(j从小到大枚举质数)
            //primes[j]一定是primes[j] * i的最小质因子
        }
    }
}

试除法求所有约数

vector<int> get_divisors(int n)
{
    vector<int> res;
    for (int i = 1; i <= n / i; i ++ )
        if (n % i == 0)
        {
            res.push_back(i);
            if (i != n / i) res.push_back(n / i); // 两个数不能相同
        }
    sort(res.begin(), res.end());
    return res;
}

约数个数 / 约数之和

如果 N = p1^c1 * p2^c2 * ... *pk^ck
约数个数： (c1 + 1) * (c2 + 1) * ... * (ck + 1)
约数之和： (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)

unordered_map<int, int> primes;
first存储底数，second存储指数

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

    for (int i = 2; i <= x / i; i ++ )
        while (x % i == 0)
        {
            x /= i;
            primes[i] ++ ; // 指数增加, 注意为 primes[i]
        }

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

// 输出约数个数
for ( auto prime : primes ) res = res * ( prime.second + 1 ) % N;
cout << res;



LL res = 1; // 存储约数之和
for (auto p : primes)
{
    LL a = p.first, b = p.second;
    LL t = 1;
    while (b -- )
        t = (t * a + 1) % mod;
    res = res * t % mod;
}
/*
t = t ∗ p + 1
t = 1
t = p + 1
t = p^2  + p + 1
……
t = p^b + p^(b-1) + … + 1
*/