INFO

若无特殊说明，本章涉及的变量皆为正整数。

定义

• 若 $n$ 只能被 $1$ 和 $n$ 整除，则 $n$ 是质数，否则是合数；
• $\pi (n)$：$n$ 以内的质数个数，$\pi (n)\approx \frac{n}{\ln n}$；
• $p(n)$：第 $n$ 个质数，$p(n)\approx n\ln n$。

质数判定

若 $n$ 为合数，则必定存在 $i\le \sqrt{n}$，使 $n$ 能整除 $i$。$n=\phantom{0}$$\phantom{0}0,\phantom{0}$$\phantom{0}1$ 需要特判。

时间复杂度：$O(\sqrt{n})$。

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

质数筛法

求 $n$ 以内的所有质数。

暴力算法

对 $[2,\phantom{0}$$\phantom{0}n]$ 中的所有整数进行一次 质数判定。时间复杂度：$O(n\sqrt{n})$。

vector<int> prime;

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

void getPrime(int n) {
    for(int i = 2; i <= n; i ++)
        if(isPrime(i))
            prime.push_back(i);
}

埃氏筛法

任意数的倍数必定是合数。

划掉 $[2,\phantom{0}$$\phantom{0}n]$ 中每个数的倍数，剩下的就是质数。

• 划掉 $2$ 的倍数：$4,\phantom{0}$$\phantom{0}6,\phantom{0}$$\phantom{0}8,\phantom{0}$$\phantom{0}\cdots$；
• 划掉 $3$ 的倍数：$6,\phantom{0}$$\phantom{0}9,\phantom{0}$$\phantom{0}12,\phantom{0}$$\phantom{0}\cdots$；
• $4$ 已划，则 $4$ 的倍数也已划，跳过；
• 划掉 $5$ 的倍数：$10,\phantom{0}$$\phantom{0}15,\phantom{0}$$\phantom{0}20,\phantom{0}$$\phantom{0}\cdots$；
• $6$ 已划，跳过；
• $\cdots$

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

@LR;
ranksep=0.2;
nodesep=0.2;
node[@big, @gray, color=none, fontcolor="#757575"]
edge[@invis]
25->26->27->28->29->30
19->20->21->22->23->24
13->14->15->16->17->18
7->8->9->10->11->12
1->2->3->4->5->6
1[@invis]
2, 3, 5, 7, 11, 13, 17, 19, 23, 29[@purple, fontcolor=black]

埃氏筛法优化：$i$ 的倍数中，$2i$ 已被 $2$ 划掉，$3i$ 已被 $3$ 划掉，$\cdots$，$(i-\phantom{0}$$\phantom{0}1)i$ 已被 $i-\phantom{0}$$\phantom{0}1$ 划掉，故只需从 $i^2$ 开始划。

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

const int N = 1e6;
bool mark[N];   // mark[i]: i 是否被划掉
vector<int> p;

void getPrime(int n) {
    for (int i = 2; i <= n; i ++) {
        if (mark[i])
            continue;
        p.push_back(i);
        for (int v = i * i; v <= n; v += i)
            mark[v] = true;
    }
}

线性筛法

埃氏筛法 中，有些数会被重复划，如 $i=\phantom{0}$$\phantom{0}2,\phantom{0}$$\phantom{0}3$ 时都划了 $12$。针对此问题，线性筛法改变了划数的策略：

使每个合数只被其最小质因子划去。

在第 $i$ 次循环中，埃氏筛法 简单地划掉了 $i$ 的倍数 $i^2,\phantom{0}$$\phantom{0}i(i+\phantom{0}$$\phantom{0}1),\phantom{0}$$\phantom{0}i(i+\phantom{0}$$\phantom{0}2),\phantom{0}$$\phantom{0}\cdots$。

for (int v = i * i; v <= n; v += i) {
    mark[v] = true;
}

而线性筛法划掉的是 $i\times p[j=\phantom{0}$$\phantom{0}0,\phantom{0}$$\phantom{0}1,\phantom{0}$$\phantom{0}\cdots ]$，且 $i\times p[j]$ 的最小质因子必须是 $p[j]$。

for (int j = 0; j < p.size() && i * p[j] <= n; j ++) {
    if (/* i × p[j] 的最小质因子是 p[j] */) {
        mark[i * p[j]] = true;
    }
}

对于任意 $n$ 以内的合数 $v$，若 $v$ 的最小质因子是 $p$，则 $v$ 会且仅会在 $i=\phantom{0}$$\phantom{0}{\displaystyle \frac{v}{p}}$ 时被划掉，真正做到了不重不漏。

现在只需讨论 if() 的条件。举个例子：$i=\phantom{0}$$\phantom{0}15$ 时 $p=\phantom{0}$$\phantom{0}\{2,3,5,7,11,13\}$：

• $15\times 2=\phantom{0}$$\phantom{0}30$，最小质因子是 $2$，可以划；
• $15\times 3=\phantom{0}$$\phantom{0}45$，最小质因子是 $3$，可以划；
• $15\times 5=\phantom{0}$$\phantom{0}75$，最小质因子是 $3\ne \phantom{0}$$\phantom{0}5$，跳过；
• $15\times 7=\phantom{0}$$\phantom{0}105$，最小质因子是 $3\ne \phantom{0}$$\phantom{0}7$，跳过；
• $15\times 11=\phantom{0}$$\phantom{0}165$，最小质因子是 $3\ne \phantom{0}$$\phantom{0}11$，跳过；
• $\cdots$

不难发现，由于 $15$ 本身有因数 $3$，这导致 $15\times 3$ 之后的情况都可以跳过。因此当 $imodp[j]=\phantom{0}$$\phantom{0}=\phantom{0}$$\phantom{0}0$ 时直接跳出循环。

for (int j = 0; j < p.size() && i * p[j] <= n; j ++) {
    mark[i * p[j]] = true;
    if (i % p[j] == 0)
        break;
}

时间复杂度：$O(n)$。

const int N = 1e6;
bool mark[N];
vector<int> p;

void getPrime(int n) {
    for (int i = 2; i <= n; i ++) {
        if (!mark[i])
            p.push_back(i);
        for (int j = 0; j < p.size() && i * p[j] <= n; j ++) {
            mark[i * p[j]] = true;
            if (i % p[j] == 0)
                break;
        }
    }
}