欧拉线性素数筛(转)

欧拉线性素数筛(转)

简介

在埃氏筛中,我们会重复筛到同一个数,例如12同时被2和3筛到,15同时被3和5筛到。所以我们引入欧拉筛,也叫线性筛,可以在$O(n)$的时间内完成对2~n的筛选。它的核心思想是:让每一个最小的合数被其最小质因数筛到

过程

我们这次除了把2~n列出来,还维护一个质数表

还是从头到尾遍历,第一个数是2,未被划掉,把它放进质数表:

然后我们用2去乘质数表里的每个数,划掉它们:

下一个是3,加入质数表,划掉6、9:

下一个是4(注意这里划掉的数也要遍历,只是不加入质数表),先划掉8,但我们不划掉12,因为12 应该由它的最小质因数2筛掉,而不是3。

实际上,对于 ,我们遍历到质数表中的 [] ,且发现 时,就应当停止遍历质数表。因为:设 [] 本身是 的最小质因数),那么对于任意 ,有 ,说明 的最小质因数不是 ,我们不应该在此划掉它。

这么说有点抽象,具体地说,如这里的2能被4整除,则 ,那么对于任何大于2的质数 ,都有 ,其中2是一个比 更小的质数,所以 应该被2筛掉而不是被 筛掉。

下一个是5,加入质数表,划掉10,15:

下一个是6,划掉12,6被2整除,跳过。

……

按这样的步骤进行下去,可以筛掉所有的合数,并得到一张质数表。

我们可以保证每个合数都被筛过,设任意合数 ,其中 的最小质因数,又设 的最小质因数。在处理 [] 时,要遍历质数表,直到遇到 [] 时才结束,所以任意小于等于 的质数与 的乘积,都会在此时被筛掉。

而由于一定有 (因为 的最小质因数是 ,而不是 ),所以在处理到 时, 一定会被筛到。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool prime[maxn];
vector<int> primes;
void make_prime(int n)
{
memset(prime,1,sizeof(prime));
for (int i = 2;i <= n;i++)
{
if (prime[maxn])
primes.push_back(i);
for (int p : primes)
{
if (p * i > n)
break;
prime[p * i] = 0;
if (i % p == 0)
break;
}
}
}

注意判断越界那里最好使用乘法而不是除法,一般不ecco会溢出,计算机算除法比乘法要慢得多。

转载自:算法学习笔记(17): 素数筛-Pecco


评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×