本笔记内容来源于算法基础课

质数

对于所有$ \geq 2$的正整数可以划分为质数与合数

在$> 1$的整数中，如果只包含1和本身这两个约数，则被称之为质数/素数

质数的判定 - 试除法

朴素写法，时间复杂度度为$O(n)$

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

若$d | n$则必然有$\frac{n}{d} | n$，因此在进行枚举时只需要枚举较小的约数即可，即
$$ d \leq \frac{n}{d} \rightarrow d^2 \leq n \rightarrow d \leq \sqrt{n} $$
时间复杂度为$\sqrt n$

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

错误写法：
1. i <= sqrt(n) 每次循环都会求一次$\sqrt{n}$
2. i * i <= n i * i存在溢出风险

分解质因数 - 试除法

对于一个合数$N$，$N$可以分解为若干个质数的乘积$N = p^{a_1}_1 p^{a_2}_2 \dots p^{a_n}_n$，其中$a_i$为正整数

从小到大枚举所有数，然后判断能分解成多少个,时间复杂度为$O(n)$

void divide(int n) {
    for (int i = 2; i <= n; i ++) {
        if (n % i == 0) { // 判断是否为约数（必然为质数）
            int cnt = 0; // 存储约数的个数
            while (n % i == 0) { // 不断试除
                n /= i;
                cnt ++;
            }
        }
    }
}

约数一定为质数，因为当n % i == 0时，$n$为$i$的倍数，然而由于$n$已经不包含$2 \sim i - 1$的因子（已除完），因此$i$也已经不包含$2 \sim i - 1$的因子，因此$i$必然为质数

$n$中最多只包含一个$> \sqrt n$的质因子，（反证法：存在两个及以上，则相乘后的数$> n$，因此可以优化

时间复杂度为$\sqrt n$（最坏情况，好情况如$2 ^ k$）

void divide(int n) {
    for (int i = 2; i <= n / i; i ++) { // 先枚举 < sqrt(n) 的质因子
        if (n % i == 0) { // 判断是否为约数（必然为质数）
            int cnt = 0; // 存储约数的个数
            while (n % i == 0) { // 不断试除
                n /= i;
                cnt ++;
            }
            wr.write(i + " " + cnt);
        }
    }
    if (n > 1) wr.write(n); // 除剩下的数为> sqrt(n)的质因子
}

筛质数

将$2 \sim n - 1$中的所有数的倍数删去，剩下的数为质数

在$1 \sim n$中有$\frac{n}{\ln n}$个质数

埃式筛

对于数$p$若$2 \sim p - 1$的数已经被删去，那么说明$p$不为$2 \sim p - 1$的倍数，因此$p$为质数

int primes[N]存储所有质数
int cnt = 0 哨兵
boolean 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; // 标记删除所有倍数，注意从2i开始枚举，i已经被标记过
    }
}

时间复杂度为
$$ \frac{n}{2} + \frac{n}{3} + \dots \frac{n}{n} = n (\frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n} ) = n \ln n < n \lg n \ $$
而由于只需要判断质数的倍数筛去，因为合数可以分解成质因数。时间复杂度$O(n\lg ( \lg n ) )$

例题：Acwing 4083

线性筛

对于数$n$只会被其最小质因子筛去，时间复杂度为$O(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++) { // 从小到大枚举质数,保证primes[j] * i <= n
            st[primes[j] * i] = true; // 
            if (i % primes[j] == 0) break; // 当成立时，primes[j]是i的最小质因子
        }
    }
}

i % primes[j] == 0时，primes[j]是i的最小质因子，且primes[j]是primes[j] * i的最小质因子
i % primes[j] != 0时，primes[j]小于i的所有质因子，primes[j]也是primes[j] * i的最小质因子

注意不需要j < cnt，若i是合数，则枚举到最小质因子时会停止，若i是质数，则会在枚举到primes[j] = i时break

$1 \sim N$中与$p$

注意$p$可以不为质数，它代表一个因数

$1 \sim N$ 中包含$p$的元素个数 $\lfloor\frac{N}{p}\rfloor$

当中包含$p$的元素为$p, 2p, \dots kp$，$kp \le N \Rightarrow k \le \frac{N}{p} \Rightarrow k = \frac{N}{p}$

当中所有包含$p$的元素为for (int i = p; i <= N; i += p)

$1 \sim N$ 中包含$p$的因子的个数 $\lfloor \frac{N}{p} \rfloor + \lfloor \frac{N}{p^2} \rfloor + \cdots$

设当中存在包含$p^k$的元素，则会被包含$p, p^2, \cdots p^k$的元素各统计一次，即$\frac{N}{p}, \frac{N}{p^2}, \cdots \frac{N}{p^k}$，因此总共会统计$k$次，即包含的因子个数