质数的定义

若一个正整数除了 $1$ 和它本身外，不能被其他正整数整除，则称这个正整数为质数（或素数）。

$1$ 既不是质数也不是合数。

质数的分布

对于一个足够大的整数 $n$，$[1,n]$ 范围内的质数大约有 $\frac{n}{\ln n}$ 个。

质数的判定

试除法

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

埃氏筛法

const int N = 1000000;
int primes[N], cnt = 0;
bool is_prime[N]; // is_prime[i] 为 true 表示 i 是质数

void get_primes(int n) {
    memset(is_prime, true, sizeof is_prime);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i <= n; i++) {
        if (!is_prime[i]) continue;
        
        primes[cnt++] = i;
        for (int j = i * i; j <= n; j += i) {
            is_prime[j] = false;
        }
    }
}

线性筛法

埃氏筛法存在的问题是同一个合数可能会被重复标记，这是因为它没有确定唯一产生某一合数的方式！

线性筛法通过从大到小累计质因子的方式标记每个合数，举例来说，$12$ 只有 $3\ast 2\ast 2$ 一种产生方式。

设数组 $v$ 记录每个数的最小质因子，按以下方式维护 $v$：

1. 依次考虑 $2\sim N$ 之间的每一个数 $i$。
2. 若 $v[i]=i$，说明 $i$ 是质数。
3. 扫描不大于 $v[i]$ 的每一个质数 $p$，令 $v[i\ast p]=p$，也就是再 $i$ 的基础上累积一个质因子 $p$，因为 $p\le v[i]$，所以 $p$ 就是合数 $i\ast p$ 的最小质因子。

由此，每个合数 $i\ast p$ 只会被它的最小质因子 $p$ 标记一次，而不会被重复标记。时间复杂度为 $O(N)$。

const int N = 1000000;
int v[N], primes[N], cnt = 0;
void get_primes(int n) {
    for (int i = 2; i <= n; i++) {
        if (v[i] == 0) {
            // i 是质数
            v[i] = i;
            primes[++cnt] = i;
        }

        // 给当前数 i 累积质因子
        for (int j = 1; j <= cnt; j++) {
            // i 存在比 primes[j] 小的质因子，或者 i * primes[j] 大于 n
            if (primes[j] > v[i] || i * primes[j] > n) break;
            // primes[j] 是合数 i * primes[j] 的最小质因子
            v[i * primes[j]] = primes[j];
        }
    }
}

或者更一般的写法：

const int N = 1000000;
int primes[N], cnt = 0;
bool not_prime[N]; // not_prime[i] 为 true 表示 i 不是质数

void get_primes(int n) {
    for (int i = 2; i <= n; i++) {
        if (!not_prime[i]) primes[cnt++] = i;

        for (int j = 0; j < cnt && primes[j] <= n / i; j++) {
            not_prime[i * primes[j]] = true;
            if (i % primes[j] == 0) break; // 魔法优化
        }
    }
}

算术基本定理

对于任意正整数 $n$，都有：

$$\begin{array}{rl}n& =(p_1^{a_1}\times p_2^{a_2}\times \cdots \times p_k^{a_k})\\ & \text{其中 }{p}_i\text{ 为质数，}{a}_i\text{ 为它们的指数}\\ & \text{且 }{p}_1<p_2<\cdots <p_k\end{array}$$

分解质因数

void factorize(int n) {
    for (int i = 2; i <= n / i; i++) {
        if (n % i == 0) {
            int cnt = 0;
            while (n % i == 0) {
                n /= i;
                cnt++;
            }
            cout << i << ' ' << cnt << endl;
        }
    }
    // n 中至多只包含一个大于 sqrt(n) 的质因子
    if (n > 1) cout << n << ' ' << 1 << endl;
}