Skip to content

质数

2021-07-05

INFO

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

定义

  • n 只能被 1n 整除,则 n 是质数,否则是合数;
  • π(n)n 以内的质数个数,π(n)nlnn
  • p(n):第 n 个质数,p(n)nlnn

质数判定

n 为合数,则必定存在 in,使 n 能整除 in=0,1 需要特判。

时间复杂度:O(n)

cpp
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(nn)

cpp
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,
  • 划掉 3 的倍数:6,9,12,
  • 4 已划,则 4 的倍数也已划,跳过;
  • 划掉 5 的倍数:10,15,20,
  • 6 已划,跳过;

时间复杂度:O(nlogn)

埃氏筛法优化:i 的倍数中,2i 已被 2 划掉,3i 已被 3 划掉,(i1)i 已被 i1 划掉,故只需从 i2 开始划。

时间复杂度:O(nloglogn)

cpp
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 的倍数 i2,i(i+1),i(i+2),

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

而线性筛法划掉的是 i×p[j=0,1,],且 i×p[j] 的最小质因子必须是 p[j]

cpp
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=vp 时被划掉,真正做到了不重不漏。

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

  • 15×2=30,最小质因子是 2,可以划;
  • 15×3=45,最小质因子是 3,可以划;
  • 15×5=75,最小质因子是 35,跳过;
  • 15×7=105,最小质因子是 37,跳过;
  • 15×11=165,最小质因子是 311,跳过;

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

cpp
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)

cpp
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;
        }
    }
}