筛法

前置知识

素数

目标

朴素筛，埃式筛，线性筛

What

问题，求小于等于n有多少个质数

朴素筛，O(nlogn)

把每一个数的倍数，全部筛掉。这样就会有很多冗余，比如，其实不用处理合数的倍数，一些数字是被重复筛掉的。 原理，对于任何一个数 p，从 2 到 p - 1，没有把 p 删掉。即 p 不是 2 到 p - 1 的倍数，2 到 p - 1 没有 p 的约数，那么，p 就是质数。

void get_primes(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (!st[i])
        {
            primes[cnt++] = i;
        }

        for (int j = i + i; j <= n; j += i) st[j] = true;
    }
}

埃式筛，O(n)，标准计算值O(nloglogn)

把朴素筛的for循环，放到 if 判断里面，只对质数的倍数，进行筛法处理。

// 版本1，只枚举质数的倍数
void get_primes(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (st[i]) continue;
        primes[cnt++] = i;
        for (int j = i + i; j <= n; j += i)
            st[j] = true;
    }
}

// 版本2，枚举质因子，把质因子的倍数，全部约掉
void get_primes(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (st[i]) continue;
        primes[cnt++] = i;
        for (int j = i; j <= n / i; j ++) st[i * j] = true;   
    }
}

// 版本3
// 注意观察这个细节，j的枚举，从i*i开始
// 不必从i*2开始，它已经在i=2时被筛掉了
void get_primes(int n)
{
    int m = sqrt(n + 0.5);
    for (int i = 2; i <= m; i++) if (!st[i]){
        primes[cnt++] = i;
        for (int j = i * i; j <= n; j += i) st[j] = true;
    }
}

线性筛，O(n)

目标：把每一个合数，用他的某一个质因子筛掉。核心：n只会被他的最小质因子筛掉 每一个合数 i * p，只会被它的最小质因子 p 筛一次，时间复杂度是O(n) 从小到大枚举所有质数，每一次，把当前质数 和 i 的乘积筛掉， 当 i % primes[j] == 0的时候，break 当 i % primes[j] == 0成立的时候，就说明primes[j] 是 i 的最小质因子

// 版本1
void get_primes(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (!st[i]) primes[cnt++] = i;
        for (int j = 0; primes[j] <= n / i; j++)
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

// 版本2
int v[N], primes[N], cnt;

void get_primes(int n){
    for (int i = 2; i <= n; i++){
    // i 是质数
        if (!v[i]) v[i] = i, primes[cnt++] = i;
        // 给当前的数 i 乘上一个质因子
        for (int j = 0; j < cnt; j++){
            // i 有比 primes[j] 更小的质因子，或者超出 n 的范围，停止循环
            if (primes[j] > v[i] || primes[j] > n / i) break;

            // primes[j] 是合数 i * primes[j] 的最小质因子
            v[i * primes[j]] = primes[j];
        }
    }
}

总结

朴素筛，埃氏筛，线性筛

参考

AcWing