数论

前置知识：

a|b（“|”是整除符号），读作“a整除b”或“b能被a整除”。a叫做b的约数（或因数），b叫做a的倍数。

质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

（1）判定——试除法

遍历查找，能否找到一个值为2~n-1的i，且i|n，即i整除n;

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;
}

试除法优化

假设d能整除n，则有(n / d)能整除n，而我们只需要找到一个

for (int i = 2; i <= n / i; i++)

i * i <= n 可能会出现溢出(i+1)*(i+n) > int_max的情况，溢出为负值会影响判断。

时间复杂度O(sqrt(n))

（2）分解质因数——试除法

暴力做法

i为什么一定是质数？因为当循环经历过i=2之后则i的倍数均不可能满足

void divide(int n) {
    for (int i = 2; i <= n; i++) {
        if (n % i == 0) { // i 一定是质数
            int sum = 0;
            while (n % i == 0) {
                n /= i;
                sum++;
            }
            printf("%d %d
", i, sum);
        }
    }
}

时间复杂度优化

void divide(int n) {
    for (int i = 2; i <= n / i; i++) {
        if (n % i == 0) { // i 一定是质数
            int sum = 0;
            while (n % i == 0) {
                n /= i;
                sum++;
            }
            printf("%d %d
", i, sum);
        }
    }
    if (n > 1) printf("%d %d
", n, 1);
    puts("");
}

时间复杂度O(sqrt(n))

（3）筛质数

算数基本定理

算术基本定理可表述为：任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积

事件复杂度O(nlogn) 1~n中有(n/log{n}) 个质数

int primes[N], 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 = i + i; j <= n; j += i) 
            st[j] = true;
    }
}

优化后，埃氏筛法

int primes[N], 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 = i + i; j <= n; j += i) 
            st[j] = true;
        }
    }
}

线性筛法

核心：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] <= n / i; j++) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break; // primes[j] 是i的最小质因子
        }
    }
}