🔢 数论

一、质数

• 概念：质数（ Prime number ）又称素数，是指在大于 1 的自然数中，

  除了 1 和它本身以外不再有其他因数的自然数。否则称为合数（规定 1 既不是质数也不是合数）。

1.1 试除法判质数

• 模板题：866. 试除法判定质数

• 核心：当 x 可以整除一个数 i , 那么必定有 x 可以整除另一个数 x / i

  比如说 ：12 可以整除 3 ， 那么必定可以整除 12 / 3 = 4

  则我们只需要做循环做到 i <= x / i 即可（分界线是 根号 x）

• 示例代码：

#include <iostream>
using namespace std;

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

int main()
{
    int n;
    cin >> n;
    while( n -- ){
        int x;
        cin >> x;
        if(is_prime(x)) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    
    return 0;
}

1.2 分解质因数

• 模板题：867. 分解质因数

• 核心：

  • 整数唯一分解定理亦称算术基本定理，该定理断言：任何一个大于 1 的整数 n 都可以

    分解成若干个 质(素) 因数的连乘积，如果不计各个 质(素) 因数 的顺序，那么这种分解是唯一的

  • 同样可以只枚举到 根号 x 也就是 i <= x / i

  • 虽然可以只枚举到 根号 x 但需要最后特别处理一下大于 根号 x 那个质因数，而有同学会疑惑为什么

    只有一个？？答：其实要不没有大于根号 x 的，要是有就只有一个，且指数为 1 ，

    可以根据反证法说明，如果有两个大于根号 x 的质因数，那么相乘就大于 x 了，矛盾！！

• 示例代码：

#include <iostream>
using namespace std;

void divide(int x){
    for(int i = 2; i <= x / i; i ++ ){
        if(x % i == 0){
            // 一旦 x 能整除 i , 那么就把所有 i 的因子除尽(while)
            // 那么就可以保证后面出现的 i 不可能是之前某个因子的倍数
            // 那么从小到大试除，每次的 i 就一定是质数(2 ~ x-1 没有它的因数)
            int s = 0;
            while(x % i == 0){
                x /= i;
                s ++;
            }
            cout << i << ' ' << s << endl;
        }
    }
    // 处理那个大于 根号 x 的质因数
    if(x > 1) cout << x << ' ' << 1 << endl;
    cout << endl;
}

int main()
{
    int n;
    cin >> n;
    while( n -- ){
        int x;
        cin >> x;
        divide(x);
    }
    
    return 0;
}

1.3 筛质数

• 模板题：868. 筛质数

• 朴素筛 / 埃氏筛：

#include <iostream>
using namespace std;

const int N = 1e6 + 10;
// primes 存质数，cnt 存质数个数
int primes[N], cnt;
// st 用来标志某个数有没有被筛成合数
bool st[N];

// 埃氏筛
void get_primes(int x){
    for(int i = 2; i <= x; i ++ ){
        // 如果某个数在前面没有被筛成合数，那么就是质数
        if(!st[i]){
            // 记录质数
            primes[cnt ++ ] = i;
            // 筛掉以这个质数为因子的数
            for(int j = i + i; j <= x; j += i){
                st[j] = true;
            }
        }
    }
}

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

• 线性筛：

#include <iostream>
using namespace std;

const int N = 1e6 + 10;
// primes 存质数，cnt 存质数个数
int primes[N], cnt;
// st 用来标志某个数有没有被筛成合数
bool st[N];

// 线性筛
void get_primes(int x){
    for(int i = 2; i <= x; i ++ ){
        // 如果某个数在前面没有被筛成合数，那么就是质数
        if(!st[i]) primes[ cnt ++ ] = i;
        // 由唯一分解定理知: 任何一个大于 1 的整数 n 都可以分解成若干个素因数的连乘积
        // 那么我们就可以拿前面已经获取到的质数来筛后面的数
        // 其次，每个数都只用它的最小质因数来筛，那么可以保证每个数只被筛一次，不会被重复判断
        for(int j = 0; primes[j] <= x / i; j ++ ){
            st[primes[j] * i] = true;
            // 下面的break是关键步骤，它可以保证每个数都只用它的最小质因数来筛
            // 分类讨论: (下面 pj 指primes[j])
            //      1. 如果 i % pj == 0 : 那么 pj 一定是 i 的最小质因子, 且 pj 一定是 pj * i 的最小质因子
            //      2. 如果 i % pj != 0 : 那么 pj 一定小于 i 所有的质因子, 且 pj 一定是 pj * i的最小质因子
            // 那么综合以上两种情况,可以得到在遍历过程中，所有的 pj 都一定是 pj * i 的最小质因子
            // 所以前面才有 st[primes[j] * i] = true; --> 使用最小质因子来筛
            if(i % primes[j] == 0) break;
        }
    }
}

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

二、约数