再看欧拉筛

Description

欧拉筛如何实现：每个合数仅被它的最小质因子筛掉？

Code

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 3e7+5;

int p[N], cnt;
bool vis[N];/// 1 表示合数 0 表示素数

void Euler(int n)
{
    cnt = 0;
    for(int i = 2; i <= n; ++i)
    {
        if(!vis[i])
            p[++cnt] = i;
        for(int j = 1; j <= cnt && p[j] * i <= n; ++j)
        {
            vis[ p[j] * i ] = 1;
            if(i % p[j] == 0)///确保每个合数只被它的最小质因子筛掉
                break;
        }
    }
}

欧拉筛做了什么？

我们要知道从2到n哪些是素数，哪些是合数，欧拉筛就从2到n都遍历了一遍

遍历这一遍干了啥？

两步

①判断当前所访问的数字i有没有被前面的数字筛掉，若没有，则是素数，存下来

(对应第一个if)

②用已筛选出来的全部素数由小到大依次 x i (乘i),得到的乘积因为是合数被筛掉。

(对应for循环以及vis[] = 1，至于后面那个if，下面来讨论)

倘若没有if(i % p[j] == 0) break; 会发生什么？

我们看 i == 4 的时候

2 x 4 == 8，筛掉了8

进行一步if判断：i % p[j] == 0 ? (此时 j == 1 第1个素数 ：2 )

条件成立 (即 i % p[1] == 0 式①)

如果不停止，那么 j++，j 变成2，p[2]是一个更大的质数3 (质数就是素数)，

那么合数 A = i x p[j] (式②)是被当前这个较大的p[j]（也就是3）筛掉了

那么接下来，就是见证奇迹的时刻

我们看:

A是能被 i 整除的(式②)

i是能被p[1]整除的(式①)

那么A是能被p[1]整除的！！！

那么A的最小质因子应该是p[1]而非p[2]

那么if(i % p[j] == 0)就该break！

你品！你细品！

就像上面的例子

2 x 4 == 8筛掉8后执行if

4 % 2 == 0

那么3 x 4 得到的12既然能被4整除，必然能被2整除(因为4能被2整除)

当然现在没有更大的素数筛出来，退一步讲，即使5筛出来了也是这样

5 x 4 得到的20既然能被4整除，必然能被2整除，所以到此为止

后面4的倍数的最小质因子都是2，不要用更大的质数去筛了

欧拉筛与埃氏筛

欧拉筛保证了每个合数只被筛过一次

(埃氏筛是用每个素数去筛掉它的倍数，像6会被2、3各筛一次，30会被2、3、5各筛一次)

节省了不必要的重复筛除，节省了时间