【算法/数论】欧拉筛法详解：过程详述、正确性证明、复杂度证明

文章目录

- - 一、什么是筛法
  - 二、欧拉筛法详解
  - 三、欧拉筛法正确性的证明
  - 四、欧拉筛法时间复杂度的证明

一、什么是筛法

筛法就是求出小于等于【算法/数论】欧拉筛法详解：过程详述、正确性证明、复杂度证明的所有素数的方法，在数论中发挥着很大的作用。

二、欧拉筛法详解

筛法进行复杂度优化，所采用的一个惯用思路是：找到一个素数后，就将它的倍数标记为合数，也就是把它的倍数“筛掉”；如果一个数没有被比它小的素数“筛掉”，那它就是素数。欧拉筛法的大致思路也是如此，就是其中有些细节有差异。欧拉筛法拥有线性的复杂度，而且编码较简单，应用十分广泛。

我们先给出代码：

bool isprime[MAXN]; // isprime[i]表示i是不是素数
int prime[MAXN]; // 现在已经筛出的素数列表
int n; // 上限，即筛出<=n的素数
int cnt; // 已经筛出的素数个数

void euler()
{
    memset(isprime, true, sizeof(isprime)); // 先全部标记为素数
    isprime[1] = false; // 1不是素数
    for(int i = 2; i <= n; ++i) // i从2循环到n（外层循环）
    {
        if(isprime[i]) prime[++cnt] = i;
        // 如果i没有被前面的数筛掉，则i是素数
        for(int j = 1; j <= cnt && i * prime[j] <= n; ++j)
        // 筛掉i的素数倍，即i的prime[j]倍
        // j循环枚举现在已经筛出的素数（内层循环）
        {
            isprime[i * prime[j]] = false;
            // 倍数标记为合数，也就是i用prime[j]把i * prime[j]筛掉了
            if(i % prime[j] == 0) break;
            // 最神奇的一句话，如果i整除prime[j]，退出循环
            // 这样可以保证线性的时间复杂度
        }
    }
}

假设要筛出n以内的素数。我们先把所有数标记为素数。枚举i从2到n，所以因为i是从小到大的，如果i没有被前面的数（比它小的数）标记为合数，那i就是素数，加入素数列表。现在用i来筛后面的数，枚举已经筛出来的素数prime[j]（j=1~cnt），标记i * prime[j]为合数，当i是prime[j]的倍数时退出循环，i++。

思路很简单，也很莫名其妙。首先我们看似无法保证每个合数都被筛掉，也无法保证复杂度为线性（因为有两层循环）。要解决这些问题，必须经过深入的思考。

三、欧拉筛法正确性的证明

假设我们要筛掉合数【算法/数论】欧拉筛法详解：过程详述、正确性证明、复杂度证明，且的最小质因数为，令。那么显然，先被外层循环碰到。现在要筛掉它的倍数。因为是的最小质因数，所以的最小质因数必不小于，这样就保证筛掉前不会在if(i % prime[j] == 0) break;处跳出循环。即使【算法/数论】欧拉筛法详解：过程详述、正确性证明、复杂度证明的最小质因数等于，也会先筛掉后再退出循环。这样就保证了每个合数都会被筛掉。

四、欧拉筛法时间复杂度的证明

欧拉筛法的时间、空间复杂度为【算法/数论】欧拉筛法详解：过程详述、正确性证明、复杂度证明。空间复杂度是显然的。下面证明时间复杂度为线性。

我们的核心就是要证明一个合数只会被筛掉一次，即标记isprime[它]=1一次。首先，对于【算法/数论】欧拉筛法详解：过程详述、正确性证明、复杂度证明，当然只会筛掉一次，因为我们从小到大枚举prime[j]，也就是说b * prime[j]递增，因此不可能遇到两次。会不会有其他的数筛掉呢？假设又被筛掉了，其中，就是【算法/数论】欧拉筛法详解：过程详述、正确性证明、复杂度证明用来筛掉的prime[j]。
①若，则，与是最小的质因数矛盾，假设不成立；
②若，则，这意味着是的质因数。那么从小到大筛掉它的素数倍，在筛到时就break了，所以根本轮不到【算法/数论】欧拉筛法详解：过程详述、正确性证明、复杂度证明。