素数筛

快速求 n 以内的素数

埃氏筛 the Sieve of Eratosthenes

• 复杂度 $O(n \log \log n)$
• 筛的过程中，会重复筛到同一个数。比如 12 同时被 2 和 3 筛到。

线性筛

• 复杂度 $O(n)$
• 让每一个合数被其最小的质因数筛到，比如 12=3*4=6*2 需要被 6 划去。

bool isnp[MAXN];
vector<int> primes; // 质数表
void init(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (!isnp[i])
            primes.push_back(i);
        for (int p : primes)
        {
            if (p * i > n)
                break;
            isnp[p * i] = 1;
            if (i % p == 0) //保证每个数最多被筛一次。
                break;
        }
    }
}

Ref

• 算法学习笔记(17): 素数筛 - 知乎 (zhihu.com)

网络回响