埃氏筛

比较原始，但很实用，性价比高。

最简单的实现如下：(筛出1~N的质数)

1
2
3
4
5
6
7
bool notp[N];
void is() {
	for (int i = 2;i <= N;++i) 
		if (!notp[i])
			for (int j = 2*i;j <= N;j += i)
				notp[j] = 1;
}

当然这有很多的优化空间，比如排除偶数、从i*i开始等等。

上面这段代码没有记录素数的数组。可以改为：

1
2
3
4
5
6
7
8
9
10
11
bool notp[N];
vector<int> pri;
void is{
    for (int i = 2;i <= N;++i) {
        if (!notp[i]) pri.push_back(i);
        for (auto p:pri) {
            if (i*p > N) break;
            notp[i*p] = 1;
        }
    }
}

这里把筛去 “质数的整数倍” 变为 “整数的质数倍”，效果相同。

而且这种改法离欧拉筛就差一行代码

欧拉筛

也叫线性筛：

1
2
3
4
5
6
7
8
9
10
11
bool notp[i];
void els(){
    for (int i = 2;i <= N;++i) {
        if (!notp[i]) pri.push_back(i);
        for (auto p : pri) {
            if (i*p > N) break;
            notp[i*p] = 1;
            if (i % p == 0) break; //欧拉筛的精髓
        }
    }
}

每个数只筛一次

如 6=2*3=3*2。就让2先不筛它，让3去筛它。

12 = 2*6 = 3*4 = 4*3 = 6*2，实际上是6把他筛掉。

24 = 2*12 = 3*8 = 4*6 = 6*4 = 8*3 = 12*2,12去筛。

15 = 3*5 = 5*3 ，3筛掉。

这样看有点像保持第一个乘数不小于第二个乘数，且尽量保持第二个小的意思。

i 之前被 p 筛过了，由于 pri 里面质数是从小到大的，所以 i 乘上之后其他的质数 p’ 的结果一定会被 p 的倍数筛掉，就不需要在这里先筛一次，所以这里直接 break掉就好了 ——改自OI wiki

所以 i*p’ 一定会被之后的 i’*p 筛掉。

这里放一下 i 筛去的数来理解一下。

1
2
3
4
5
6
7
8
2 4
3 6 9
4 8
5 10 15 20 25
6 12 
7 14 21 28 35 42 49
8 16
9 18 27