质数

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

定义 #

  • 若 $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;
        }
    }
}