素数筛法

引入

我们先来看一个最基本的一个判断素数的方法，基于 $6k \pm 1$ 优化。

$Prove$

对于所有正整数，都可以表示为 $6k + i$。

由于以下情况 :

$6k \equiv 0 \pmod{2}$

$6k+2 \equiv 0 \pmod{2}$

$6k+3\equiv 0 \pmod{3}$

$6k+4\equiv 0 \pmod{2}$

也就是说，只有 $6k \pm 1$ 存在可能为质数的可能，所以我们只要检查 $6k \pm 1$ 有没有可能是质数就行了，这种方法也可以进行推广，但是要筛的数的范围也会随之变大，不过时间复杂度也会变得更加优秀。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


template <typename type>
bool isPrime(type n) {
    if(n <= 1)
        return false;
    if(n <= 3) 
        return true;
    if(n % 2 == 0 || n % 3 == 0) 
        return false;
    for(type i = 5; i <= n / i; i += 6) {
        if(n % i == 0 || n % (i + 2) == 0) 
            return false;
    }
    return true;
}

这种方法在求较小的质数时相当优秀和简洁，但是在大范围查询的时候，就不够适用了，这个时候，就该引入我们的质数筛法了。

埃拉托斯特尼筛法

朴素版本

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


std::vector<int> prime;
std::vector<int> vis(N, 0);

void Eratosthenes() {
    for(int i = 2; i <= N; ++i) {
        if(!vis[i]) {
            prime.push_back(i);
            if(1LL * i * i > N) 
                continue;
            for(int j = i * i; j <= N; j += i) {
                vis[j] = 1;
            }
        }
    }
}

时间复杂度为$O(n\log \log(n))$。

平方根优化

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


std::vector<int> prime;
std::vector<int> vis(N, 0);

void Eratosthenes() {
    for(int i = 2; i * i <= N; ++i) {
        if(!vis[i]) {
            for(int j = i * i; j <= N; j += i) {
                vis[j] = 1;
            }
        }
    }
    for(int i = 2; i <= N; ++i) {
        if(!vis[i]) {
            prime.push_back(i);
        }
    }
}

该版本对比朴素版本，仅仅添加了平方根的优化，时间复杂度为 $O(n\log \log(\sqrt{ n })\ +\ n)$, 然而这样会显著优化时间。

由于我们知道，合数不可能为素数，所以我们只需要对奇数进行检验即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


std::vector<int> prime;
std::vector<int> vis(N, 0);

void Eratosthenes() {
    prime.push_back(2);
    for(int i = 3; i * i <= N; i += 2) {
        if(!vis[i]) {
            for(int j = i * i; j <= N; j += (2 * i)) {
                vis[j] = 1;        
            }
        }
    }
    for(int i = 3; i <= N; i += 2) {
        if(!vis[i]) {
            prime.push_back(i);
        }
    }
}

虽然这些优化可以让埃筛达到一个很好的优化，甚至在某些场景比欧拉筛还要快捷，但是埃筛的时间复杂度终究不是 $O(N)$。

欧拉筛

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


void euler(int n) {
    std::vector<bool> vis(n + 1, 0);
    std::vector<int> primes;
    for(int i = 2; i <= n; ++i) {
        if(!vis[i]) {
            primes.push_back(i);
        }
        for(auto &prime : primes) {
            if(1LL * prime * i > n) 
                break;

            vis[prime * i] = true;

            if(i % prime == 0) 
                break;
        }
    }
}

[!hint]- 说明核心：欧拉筛确保每一个合数只被他自己的最小质因数筛去。

$for\ i\ \dots n$ ，维护一个 prime 数组，表示到 $i$ 为止的所有质数。

设 $p_{i}$ 为 $i$ 的最小质因子，在 $prime$ 数组中 : prime: $[\underbrace{\dots\dots}_{\text{p}_{j}}\ , \quad \underset{\substack{\uparrow \\ \text{pi}}}{\boxed{p_i}}, \quad \dots ]$

$p_{j}$ 表示所有小于 $p_{i}$ 的质数。考虑 $newNum=i \cdot p_{j}$ 。已知 $p_{j}
这就说明了当合数被筛走的时候，必然是被自己的最小质因子筛走的。下面来说明，这样的操作是唯一的。

假设存在一个合数 $N$，他被至少两个不同的操作筛除。设这两个操作为 $(i_{1},p_{1}),\ (i_{2},p_{2})$。由于我们证明了合数必然是被自己的最小质因数筛除，则 $p_{1}=lpf(N)=p_{2}$，那么也就有 $i_{1}=i_{2}$ ，也就是说，这两个操作是等价的。

假设不成立，唯一性得证。

这里的 $lpf(N)$ 是 $Least\ Prime\ Factor\ of\ N$。

筛法求约数个数

用 $d_i$ 表示 $i$ 的约数个数，$num_i$ 表示 $i$ 的最小质因子出现次数。

约数个数定理

定理：若 $n=\prod_{i=1}^m p_i^{c_i}$ 则 $d_i=\prod_{i=1}^m (c_i+1)$。

证明：我们知道 $p_i^{c_i}$ 的约数有 $p_i^0,p_i^1,\dots ,p_i^{c_i}$ 共 $c_i+1$ 个，根据乘法原理，$n$ 的约数个数就是 $\prod_{i=1}^m (c_i+1)$。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


 void euler(int n) {
    std::vector<bool> vis(n + 1);
    std::vector<int> primes, d(n + 1), num(n + 1);
    // d 储存约数个数， num 储存最小因子 p 的指数
    for(int i = 2; i <= n; ++i) {
        if (!vis[i]) {
            primes.push_back(i);
            d[i] = 2;
            num[i] = 1;
        }
        for(auto& prime : primes) {
            if(1LL * i * prime > n) 
                break;

            int id = i * prime;
            vis[id] = true;

            if(i % prime == 0) {
                num[id] = num[i] + 1;
                d[id] = d[i] / num[id] * (num[id] + 1);
                break;
            } else {
                num[id] = 1;
                d[id] = (d[i] << 1);
            }
        }
    }
}

欧拉筛求约数个数原理

结合代码，根据之前欧拉筛原理的推导。

设 $d[i]$ 表示 $i$ 的约数个数， $\text{num}[i]$ 表示在 $i$ 中的最小质因子 $p_{i}$ 的指数大小。

$for\ i\ \dots n$ ，维护一个 prime 数组，表示到 $i$ 为止的所有质数。

设 $p_{i}$ 为 $i$ 的最小质因子， $p_{j}$ 为所有小于 $p_{i}$ 的质数，在 $prime$ 数组中 :

prime: $[\underbrace{\dots\dots}_{\text{p}_{j}}\ , \quad \underset{\substack{\uparrow \\ \text{pi}}}{\boxed{p_i}}, \quad \dots ]$

数 $N$ 为质数。

显然，$d[N]=2,\ \text{num}[N]=1$。

数 $N$ 为合数 ($N=i\cdot prime$ 也就是 $N=i\cdot p_{j}$)。

$I.$ $p_{j} \nmid i$ :

我们要求 $d[N]\text{ 和 num}[N]$，有 $N=i\cdot p_{j}$，根据已知结论， $p_{j}\text{ 是 N 的最小质因子}$，得 $\text{num}[N]=1$，由乘法原理，$\text{num}[N]=2\cdot d[i]$。

$II.$ $p_{j}\mid i$ :

此时有 $p_{i}=p_{j}，i=p_{j}\cdot rest，N=p_{j}\cdot i=p_{j}\cdot p_{i}\cdot rest=p_{i}^2\cdot rest$。

这里可以看出来 $N\text{ 里面的 } p_{i}\text{ 的个数比 i 里面的多 1 个}$，由于 $p_{i}$ 是 $N$ 和 $i$ 的最小质因子，所以 $\text{num}[N]=\text{num}[i]+1$。

不妨设 $i=p_{i}^q\cdot remainNum，d[i]=(q+1)\cdot d[remainNum]$ 。

则 $N=p_{i}^{q+1}\cdot remainNum，d[N]=(q+1+1)\cdot d[remainNum]$ 。

那么有 $d[N]=(q+2)\cdot \frac{d[i]}{q+1}$，也就是 $d[N]=(\text{num[i]+2})\cdot \frac{d[i]}{\text{num}[i]+1}$。代换 $\text{num}[i]$ 得到 $d[N]=(\text{num}[N]+1)\cdot \frac{d[i]}{\text{num}[N]}$。

$Q.E.D.$