这个线性复杂度的欧拉素数筛法，爱了爱了

今天讲一下关于欧拉筛法的原理和代码实现，实不相瞒，我也才刚get到这个筛法的点，乘着记忆清晰来教一遍梳理一下思路。

我查阅资料的时候也在很多博客和公众号上看到关于欧拉筛法的解释和代码实现，然后想学习了之后用我自己的话重新描述一遍，希望我的角度能让你有所收获！

欧拉筛法与埃氏筛法一样，都是围绕【素数的倍数不是素数】这个核心原理来展开的，有关埃氏筛法请移步我的上一篇博客“埃氏筛法的详解”，但是它比埃氏筛法更高效，当数据量足够大的时候，欧拉筛法的时间是埃氏筛法时间的十分之一甚至更少。

现在我们正式展开欧拉筛法的学习。

欧拉筛法效率高的一个重要原因是，它不会重复标记一个数是不是素数的倍数，例如：6是素数2的倍数，同时也是素数3的倍数，欧拉算法能做到只标记一次6。

我们先看一下代码

#include <stdio.h>
#include <string.h>
using namespace std;

int main()
{
    int n, cnt = 0; // n是你要找的素数范围，cnt代表在这个范围内素数的个数

    int prime[100001];// 用来保存素数，注意，是用数组的值而不是用下标保存哦！

    bool visited[100001];// 就是这个数组！用来记录一个数是否是某个素数的倍数，标记它
    
    scanf("%d", &n); // 输入你想查找的范围

    memset(visited, false, sizeof(visited));// 初始化 

    memset(prime, 0, sizeof(prime));// 初始化
    
    for(int i = 2; i <= n; i++)

    {

        if(!visited[i])// 如果没有被标记过

        {
            prime[cnt++] = i;// 那么它就是素数啦~，存起来存起来，cnt记得+1 
        }

        for(int j = 0; j<cnt && i*prime[j]<=n; j++) // 这个循环是最难理解的部分，我将在下文详细解释

        {

            visited[i*prime[j]] = true;// 标记素数倍数

            if(i % prime[j] == 0) break;// 这一步跳出循环是欧拉筛法高效率的关键，也是同一个合数只被标记一次的关键

        }

    }
    return 0;
}

ok，代码如上，可以直接拷贝过去试试哦！

现在来详细分解一下那个for循环代码

此处我们暂时抛开 if(i % prime[j] == 0) break; 这句代码来讨论

---

for循环的循环变量 j 每次都从 0 开始跑，而这个 j 是从 prime[] 数组中取数据的，我们就可以这样等价，for循环每次都从已经找到的素数中从头开始取值。
例如 prime[] 中已经判断出了 2,3,5,7 那么for循环第一次取值2，如果没有跳出的话，第二次取值3，然后没有跳出的话就一直循环到已经找出的素数末尾。

然后

visited[i*prime[j]] = true;

这个代码段，是用来标记素数倍数的，例如，当 i 等于2的时候，素数数组里只存在一个素数 2 ，然后进入 for 循环，for 循环会将 2 取出来与 i 相乘，得到 2 的倍数 4 ，标记它，然后结束 for 循环。跑过 i = 3，执行到 i = 4 的时候，千万不要以为这个时候 for 循环不执行了！ 这个时候 for 循环依旧会尽职地把 2 取出来和 4 相乘，将 2 的倍数 8 标记！然后 不会取到第二个素数 3 ，因为 4 % 2 == 0 -------

纵观之，如果我们不把

if(i % prime[j] == 0) break;

这段代码放在内的话， for 循环的作用就是将素数的倍数都标记上。

---

讨论关键性代码段 if(i % prime[j] == 0) break;

然后我们开始讨论上面那一小段代码的关键性作用：

18 是素数 3 的倍数，但是我们并不会用 3 的倍数来标记掉 18 , 因为假如我们用 3 来标记 18 ，那么 i 势必要跑到 6 这样 i * 3 才会标记掉18， 但是在这之前 i 就已经被 3 之前的一个素数 2 弄死了，退出循环了。
那么为什么要这么做？因为 6 既然能被 2 整除， 那么 18 迟早会被 2 标记，所以这里就不要再用 3 来重复标记 18。
你问我怎么知道 18 迟早会被 2 标记的？ 6 能被 2 整除，那么 3 乘 6 就可以分解为 3 乘 2 乘 3， 也就是 2 乘 9 ， 2 乘 9 就标记掉了18.

---

如果你看懂了上面的代码，我们再来总结一下

有个规律，不知道大家发现没有，凡是 i 跑到偶数位的时候，它永远只能与素数 2 相乘一次来标记掉一个数，然后因为能整除 2 而退出循环。 从这个规律，这个筛法的时间复杂度就可见一斑了。
外层 i 循环用来选出素数和作为标记素数倍数的倍数因子，内层 j 循环用来从素数中最小的开始遍历作为标记素数倍数的素数因子。然后通过 i % 素数 == 0 来退出标记避免重复标记。

谢谢你的观看！
也可以转到我的个人博客上去观看。
http://hsluoyang.club/