517编程普及组数学之筛法

作用：筛法可以求出 $[1,n]$​ 的所有素数

埃氏筛

埃拉托斯特尼筛法，简称埃氏筛是求解素数的一种经典方法，和辗转相减一样古老，最初由古希腊数学家埃拉托斯特尼（Eratosthenes）提出。

我们发现对于任意一个正整数，他的所有倍数一定都是合数。

有了这个理论，我们便可以写出最朴素的筛法，复杂度 $O(n\log n)$​。

1
2
3
4
5
6
7
8
9
10
11
12
void sieve()
{
    for(int i=1;i<=n;i++)
    {
        if(!flag[i])//如果当前这个数没有被筛，那么说明他是质数
        {
            prm.push_back(i);
            for(int j=i+i;j<=n;j+=i)//筛掉他的所有倍数
                flag[j]=1;
        }
    }
}

埃氏筛（优化）

对于上面这个版本，我们发现 $21$ 会被 $3$ 和 $7$ 筛两遍，大大浪费了时间。

针对这种情况，我们可以只枚举较小的因子，也就是说只用小于 $\sqrt[2]n$ 的数去筛，转化为因子的角度就是只去筛大于等于 $x^2$ 的数。

代码变动不大，虽然渐进复杂度仍然是 $O(n\log n)$，不过常数得到了优化：

1
2
3
4
5
6
7
8
9
10
11
12
void sieve()
{
    for(int i=1;i<=n;i++)
    {
        if(!flag[i])
        {
            prm.push_back(i);
            for(int j=i*i;j<=n;j+=i)
                flag[j]=1;
        }
    }
}

欧拉筛

欧拉筛由著名的古希腊数学家欧拉（Euler）提出，他是18世纪著名的数学家和物理学家，被认为是现代数学的奠基人之一。

在欧拉时代，素数的研究已经有了相当长的历史。埃拉托斯特尼筛法虽然在古代就已经被提出，但随着数学研究的深入，人们开始意识到埃拉托斯特尼筛法的局限性，尤其是在大数值范围内的应用。因此，人们迫切需要一种更高效的素数筛法。

实现

欧拉筛可以实现 $O(n)$ 复杂度，也就是线性筛。

观察到在埃氏筛中，经过优化后仍会出现同一个数可能被多个素数重复筛掉，比如 $30$ 会被 $2,3,5$​ 重复筛掉。

为了解决这一问题，我们可以让合数只被它的最小质因数筛掉

先放上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void sieve()
{
    flag[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!flag[i])//如果当前这个数没有被筛，那么说明他是质数
            prm.push_back(i);
        for(int j=0;j<prm.size()&&i*prm[j]<=n;j++)//枚举目前的所有质数
        {
            flag[prm[j]*i]=1;//prm[j] 是 prm[j]*i 的最小质因子
            if(i%prm[j]==0)
                break;
        }
    }
}

虽然不是很长，但是十分玄学。

证明

首先说一下 if(i%prm[j]==0) break; 的作用：

  • 如果没有这一句，每一个素数会筛掉所有与大于等于它本身的数相乘得到的数，而我们只需要用最小质因数去筛。

再讲一下加上他后为何仍然正确（（（：

  • 假设我们要筛掉合数 $a$，$a$ 的最小质因数是 $p$，令 $a=pb$。
    • 显然 $a>b$，
    • 因为 $p$ 是最小质因数，所以 $p\le b$，
    • 这样就能保证在用 $b$ 筛掉 $a$ 之前不会 break 掉。