埃氏筛

埃拉托斯特尼筛法(the sieve of Eratosthenes),简称埃氏筛,也称素数筛。这是一种简单且历史悠久的筛法,用来找出一定范围内所有的素数。

朴素埃氏筛

所使用的原理是从2开始,将每个素数的各个倍数,标记成合数。一个素数的各个倍数,是一个差为此素数本身的等差数列。此为这个筛法和试除法不同的关键之处,后者是以素数来测试每个待测数能否被整除。大概的过程则如图所示。

首先,我们顺序列出2~n的数字,这里仅列至16;

从前往后看,找到第一个未被划掉的数,2,这说明它是质数。然后把2的倍数(不包括2)划掉:

下一个未被划掉的数是3,它是质数,把3的倍数划掉:

接下来应该是5,但是5已经超过 16\sqrt{16} 了,所以遍历结束,剩下未被划掉的都是素数:

简而言之,从2开始,找到第一个没有被筛的数,把它标记为素数,然后把它的2倍、3倍……筛掉。
时间复杂度为 O(nlogn)O(nlogn)
但是,很容易就可以发现,一个数字会被筛掉多次,比如样例中的6。接着,我们就要对朴素埃氏筛进行改进。

改进埃氏筛

从2开始,找到第一个没有被筛的数x,把它标记为素数,然后把它的x倍、x+1倍……筛掉。
时间复杂度降低为 O(nloglogn)O(nloglogn)
埃氏筛实现过程
代码如下:

1
2
3
4
5
6
7
bool notprime[MAXN]; 
void init(int n){
for (int i = 2; i * i <= n; i++)
if (!notprime[i])
for (int j = i * i; j <= n; j += i)
notprime[j] = true;
}

改进埃氏筛的复杂度达到 O(nloglogn)O(nloglogn) ,已经非常优秀了。但是我们可能会发现,在筛的过程中我们还是会重复筛到同一个数,例如12同时被2和3筛到,30同时被2、3和5筛到。所以我们引入欧拉筛,也叫线性筛,可以在 O(n)O(n) 时间内完成对2~n的筛选。
欧拉筛的核心思想是:让每一个合数被其最小质因数筛到

线性筛

这次,相较于埃氏筛,我们不仅列出2~n,我们还维护了一个质数表

从头到尾遍历,第一个数是2,把它放进质数表;

然后用2去乘质数表里的每个数,并筛去它们;

下一个是3,加入质数表,并筛去6、9;

下一个是4(被筛去的数也要遍历,但不加入质数表),先筛去8,但我们不筛去12,因为12 (12=2×6=3×4)(12=2\times6=3\times4) 应该由它的最小质因数2筛掉,而不是3;

下一个是5,加入质数表,并筛去10、15;

类似地,我们就可以筛去所有的合数,并得到一个质数表。

一个简单的证明:
我们可以保证每个合数都被筛过,设任意合数 x=pr(rp)x=pr(r\ge p) ,其中 ppxx 的最小质因数,又设 r=pr(rp)r=p'r'(r'\ge p')pp'rr 的最小质因数。在处理 rr 时,要遍历质数表,直到遇到 pp' 时才结束,所以任意小于等于 pp' 的质数与 rr 的乘积,都会在此时被筛掉。

而由于一定有 ppp\le p' (因为 xx 的最小质因数是 pp ,而不是 pp' ),所以在处理到 rr 时, rprp 一定会被筛到。

1
2
3
4
5
6
7
8
9
10
11
12
13
bool notPrime[MAXN]; 
vector<int> prime; // 质数表
void init(int n){
for (int i = 2; i <= n; i++){
if (!notPrime[i])
prime.push_back(i);
for (int p : prime){
if (p * i > n) break;
notPrime[p * i] = true;
if (i % p == 0) break;
}
}
}

筛法求欧拉函数

后记

由于最近不知道该学点什么,想了想还是再拾起C++的算法吧。算法永流传嘛 😃

虽说选的不是什么好时候,马上要开始长达两星期的金工实习。希望可以好好度过吧。