1、什么是质数？质数是正整数并且大于1，中不能被1和本身以外的数整除的数。
2、如何判定质数？

从定义出发
bool is_prime (int n) {
    if (n < 2) return false;
    for (int i = 2; i < n; i ++)
        if (n % i == 0) return false;
    return true;
}
时间复杂度：O(n);
如何进行优化？因为因数是成双成对的出现的，所以我们可以枚举到d<=sqrt(n)就可以了。如果存在一个能够整除数n，那么就满足n是合数的性质，否则是质数。
bool is_prime (int n) {
    if (n < 2) return false;
    for (int i = 2; i <= n / i; i ++)//注意这里如果写成i*i，会有溢出的风险，写成sqrt(n)太慢。
        if (n % i == 0) return false;
    return true;
}
时间复杂度:O(sqrt(n)),注意这里一定是O(sqrt(n))，而不是最坏情况是O(sqrt(n));

2、分解质因数
暴力做法

暴力做法
for (int i = 2; i <= n; i ++)
    if (n % i == 0) {
        int s = 0;//s为i的次数
        while (n % i == 0) {
            n /= i;
            s ++;
        }
    }
分解得到的数一定是质数吗？一定是，当我们枚举到i的时候，就因为着我们已经把所有2~i-1的因子除完了。当我们枚举到i的时候，就意味着n已经在2~i-1没有质因子了，因此当前i一定是质数。因为前面已经没有因子了，那么只有质数是不可分解的，所以可以成为这个数。
如何优化？n当中最多只包含一个大于sqrt(n)的质因子。因为如果有两个，那么两个质因子相称就会大于n
因此我们可以先枚举出[2, sqrt(n)]的质因子。
然后再特判n是否大于1
for (int i = 2; i <= n / i; i ++) 
    if (n % i == 0) {
        int s = 0;
        while (n % i == 0) {
            n /= i;
             s ++;
        }
    }
    if (n > 1).... 
算法复杂度:O(sqrt(n)),但是实际上最好情况可以达到logn,最坏情况是O(sqrt(n)), 时间复杂度是介于这两个之间的。

3、质数筛：如果在筛完后，p存在，那么p一定是质数。为什么？因为p没有被筛掉，就意味着2~p-1没有p的约数，所以p一定是质数

朴素筛
bool st[N];
int primes[N], n, cnt;

for (int i = 2; i <= n ;i ++) 
    if (!st[i])
        primes[ccnt ++] = n;
    for (int int j = i + i; j <= n; j += i) st[j] = true;//

时间复杂度:O(nlogn);    n / 2 + n / 4 + n / + ... = n (lnn)
如何优化？埃氏筛法
我们只要判断2~p - 1中的质数是否是p的质数就行了，如果存在质数是倍数，则筛掉，这里是最小质因子的原理
for (int i = 2; i <= n ;i ++) 
    if (!st[i])
        primes[ccnt ++] = n;
         for (int int j = i + i; j <= n; j += i) st[j] = true;
质数定理：[1, n]中有n / lnn个质数。
时间复杂度：n*(调和级数) = n*ln(n) / ln(n) 约等于O(N);初略估计
准确的O(nloglogN);

如何优化称线性筛？
for (int i = 2; i <= n ;i ++) 
    if (!st[i]) primes[ccnt ++] = n;
    for (int j = 0; primes[j] <= n / i; j  ++) 
        st[primes[j] * i] = true;
        if (i % primes[j] == 0) break;//primes[j] 一定是i的最小质因子。
10^6差不多，10^7次方线性筛法比埃氏筛法快一倍。
线性筛法使用了什么性质？
如果i % primes[j] == 0， primes[j]是i的最小质因子
如果i % primes[j] != 0， primes[j] * i 的最小质因子是primes[j], 但是primes[j]不是i的最小质因子，并且由于我们是从小到达枚举质数的所以primes[j]小于i的所有质因子。
合数一定会被筛掉吗？因为合数一定存在最小质因子，所以我们可以枚举到n / primes[j]=i,这时候就可以筛掉这个合数。
最终我们达到了每个数只筛一次的效果。所以是O(N)的

4、求约数
```cpp
试除法：因为约数是成对出现的，所以我们可以枚举到sqrt(n)
for (int i = 2; i <= n / i; i ++)
if (n % i == 0) {
res.push_back (i);
if (i != n / i) res.push_back (n / i);
}O(sqrt(n))
sort (res.begin(),res.end());(logn * logn) < sqrt(n);
n + n/ 2 + n / 3 +…+ n / n = nlnn = nlogn,平均意义下每个数logn

求约数个数(a1 + 1)(a2 + 1)…(an+1);，int范围内最多是1600个。
约数之和(p0 + p1 + p2 + … + pn)(a0 + a1 + a2 + … + an) ....每一种组合都是一种约数
注意这里快速幂不如while(n) res = res * a + 1;.注意这里有log(a)的求法，思路是分治。
辗转相除法
return b?gcd(b, a % b): a;
```

5、