质数

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

定义 #

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

质数判定 #

若 $n$ 为合数，则必定存在 $i≤\sqrt{n}$，使 $n$ 能整除 $i$. $n=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,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,n]$ 中每个数的倍数，剩下的就是质数.

划掉 $2$ 的倍数：$4,6,8,\cdots$
划掉 $3$ 的倍数：$6,9,12,\cdots$
$4$ 已划，则 $4$ 的倍数也已划，跳过.
划掉 $5$ 的倍数：$10,15,20,\cdots$
$6$ 已划，跳过.
$\cdots$

时间复杂度：$O(n\log{n})$.

埃氏筛法优化：$i$ 的倍数中，$2i$ 已被 $2$ 划掉，$3i$ 已被 $3$ 划掉，$\cdots$，$(i-1)i$ 已被 $i-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=2,3$ 时都划了 $12$. 针对此问题，线性筛法改变了划数的策略：

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

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

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

而线性筛法划掉的是 $i\times p[j=0,1,\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=\dfrac{v}{p}$ 时被划掉，真正做到了不重不漏.

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

$15\times 2=30$，最小质因子是 $2$，可以划.
$15\times 3=45$，最小质因子是 $3$，可以划.
$15\times 5=75$，最小质因子是 $3\not=5$，跳过.
$15\times 7=105$，最小质因子是 $3\not=7$，跳过.
$15\times 11=165$，最小质因子是 $3\not=11$，跳过.
$\cdots$

不难发现，由于 $15$ 本身有因数 $3$，这导致 $15\times 3$ 之后的情况都可以跳过. 因此当 $i\mod p[j]==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;
        }
    }
}