埃氏筛与欧拉筛（线性筛）

目录

一、前言

二、埃氏筛与欧拉筛（线性筛）

1、问题描述

2、基本思路

（1）埃氏筛法

（2）欧拉筛法

三、题例

1、上链接

2、简单思路

3、代码

（1）埃氏筛python版

（2）欧拉筛python版

---

一、前言

对于学计算机的同学来说，学习算法是一件非常重要的事情，废话不多讲，我们来讲讲“埃氏筛与欧拉筛（线性筛）问题”。

二、埃氏筛与欧拉筛（线性筛）

1、问题描述

如题，给定一个范围 n，有 q 个询问，每次输出第 k 小的素数。

具体可见下面题目链接。

2、基本思路

先在 1~n 中筛选出所有素数（质数），然后再做判断。

显然朴素的判断素数的方法时间复杂度高，不可取。

下面介绍两种时间复杂度较低的方法，即埃氏筛法和欧拉筛法。（但是这个世界上没有天上掉馅饼的事情，我降低了时间复杂度，那么就必然要牺牲空间）

（1）埃氏筛法

首先将2到n范围内的整数写下来。

其中2是最小的素数，将表中所有的2的倍数划去。

表中剩下的最小的数字就是3，他不能被更小的数整除，所以3是素数。

再将表中所有的3的倍数划去…… 以此类推，如果表中剩余的最小的数是m，那么m就是素数。

然后将表中所有m的倍数划去，像这样反复操作，就能依次枚举n以内的素数。

埃氏筛法的时间复杂度是0(n*log(logn))。

埃氏筛法的基本思想 ：

从2开始，将每个质数的倍数都标记成合数，以达到筛选素数的目的。

因为随便一个合数的约数都不会大于自己，且必然存在有约数是素数的情况，那么我对规定范围内的数进行从小到大的判断，正好是能“划掉大的合数”且不会出现遗漏。

埃氏筛核心代码：

1. static final int N = 1e7 + 5;
2. static int[] st = new int[N];
3. public static void E_sieve(int n){
5. for(int i = 2; i <= n; i++)
6. {
7. if(st[i] == 0)
8. {
9. for(int j = 2 * i; j <= n; j += i)
10. st[j] = 1; // j是i的一个倍数，j是合数，筛掉。
11. }
12. }
14. }

优化后的埃氏筛：

1. static final int N = 1e7 + 5;
2. static int[] st = new int[N];
3. public static void E_sieve(int n){
5. for(int i = 2; i <= n / i; i++)
6. {
7. if(st[i] == 0)
8. {
9. for(int j = i * i; j <= n; j += i)
10. st[j] = 1; // j是i的一个倍数，j是合数，筛掉。
11. }
12. }
14. }

优化后的时间复杂度可以近似看成 O(n) 了。但是，我们还可以更快，那就是欧拉筛。

补充：

算法代码（C++）：

1. #include
2. using namespace std;
4. //埃氏筛法
5. bool v[100001000]; //v[i]为0代表数i为素数
6. int cnt=0;
8. void prime(int n){
9. v[0]=v[1]=1;
10. for(int i=2;i<=n;++i){ //注意这里也统计了等于n的数
11. if(!v[i]){
12. cnt++;
13. for(int j=i+i;j<=n;j+=i){ //注意这里也统计了等于n的数
14. v[j]=1;
15. }
16. }
17. }
18. }
20. int main(){
21. int n;
22. cin>>n;
23. prime(n);
24. cout<
25. return 0;
26. }

对该代码稍作修改便可AC掉下面给出的力扣的例题。

（2）欧拉筛法

欧拉筛法的原理同埃氏筛法，只不过多了一个判断删除与标记最小质因子的过程。

在埃氏筛法中，一个合数来说可能会被筛多次，比如6可以被2筛去，也可以被3筛去，而欧拉筛要做的事情就是让一个合数只被筛一次。

首先，任何合数都能表示成多个素数的积。所以，任何的合数肯定有一个最小质因子。我们通过这个最小质因子就可以判断什么时候不用继续筛下去了。

欧拉筛核心代码：

1. static final int N = 1e7 + 5;
2. static int[] st = new int[N], primes = new int[N];
3. void ola(int n)
4. {
5. for (int i = 2; i <= n; i ++ )
6. {
7. if (st[i] == 0) primes[cnt ++ ] = i;//将质数存到primes中
8. for (int j = 0; primes[j] <= n / i; j ++ )//要确保质数的第i倍是小于等于n的。
9. {
10. st[primes[j] * i] = 1;
11. if (i % primes[j] == 0) break;
12. }
13. }
14. }

欧拉筛法的基本思想 ：

在埃氏筛法的基础上，让每个合数只被它的最小质因子筛选一次，以达到不重复的目的。

比如说： 120 = 2^3∗3∗5

120 会被 2 筛去一次， 3 筛去一次， 5 筛去一次。

多做了两次不必要的操作。

那么我们如何确保 120 只被 2 筛掉呢？

在埃氏筛中我们用了一个循环来筛除一个质数的所有倍数，即对于p来说，筛除数列：

2 ∗ p , 3 ∗ p , . . . , k ∗ p 
另外，我们是从小到大枚举区间中的每个数的，数列是：

2 , 3 , 4 , . . . , n

对比两个数列：

2 ∗ p , 3 ∗ p , . . . , k ∗ p
2 ，    3 ， . . . .  ,  n

会发现，第二个数列是第一个数列的系数。

所以，我们不需要用一个 for 循环去筛除一个质数的所有倍数，我们将所有质数存储到 primes[] 中，然后枚举到第 i 个数时，就筛去所有的 primes[j] * i。这样就在每一次遍历中，正好筛除了所有已知素数的 i 倍。

如果 i % primes[j] == 0，我们就结束内层循环，为什么？

 显然，i % primes[j] == 0 保证了每个合数只被它的最小质因子筛选一次！

算法代码（C++）：

1. #include
2. using namespace std;
4. //欧拉筛法
5. int v[100001000]; //v[i]=a代表数i的最小质因数为a
6. int prime[600000];
7. int cnt=0;
9. void is_prime(int n){
10. v[0]=v[1]=1;
11. for(int i=2;i<=n;++i){ //注意这里也统计了等于n的数
12. if(!v[i]){ //从小到大枚举，能保证如果v[i]==0，那么i就是素数
13. v[i]=i;
14. prime[++cnt]=i;
15. }
16. //注意一点，i显然永远是大于或等于prime[j]的，但 v[i] 不一定
17. //而一个质数的最小质因数也就是其本身，即prime[j]的最小质因数是prime[j]
18. for(int j=1;j<=cnt;++j){
19. //因为从小到大枚举，所以当前的大于，以后的一定大于
20. if(prime[j]>n/i||prime[j]>v[i])
21. break;
22. v[i*prime[j]]=prime[j];
23. // i*prime[j] 代表当前数乘以之前出现的素数
24. // v[i*prime[j]] 的最小质因数是prime[j]
25. // 当 i%prime[j]==0 时，显然成立
26. // 当 i%prime[j]!=0 时，又由于上面的 if 判断保证了 v[i]>=prime[j]，所以也成立
28. /**
29. 解释上面的这个 if 判断条件
30. 第一个条件 prime[j]>n/i 用于防止越界
31. 第二个条件 prime[j]>v[i]，如果 i 的最小质因子比prime[j]的最小质因子小，那么
32. v[i*prime[j]]应该等于v[i]，但是现在用当前数的最小质因子给 i*prime[j] 的最小质因子赋值会导致重复赋值，
33. 因为后面 i==(i*prime[j])/v[i] 的时候prime[i]能在不大于v[i]的情况下 v[i*prime[j]]=prime[j]
34. 也就是说，我们要保证prime[j]为最小质因子，这样能减少操作次数 */
35. }
36. }
37. }
39. int main(){
40. int n,q;
41. cin>>n>>q;
42. is_prime(n);
43. for(int i=0;i
44. int k;
45. cin>>k;
46. cout<
47. }
48. return 0;
49. }

代码为何这样写看注释，解释得非常清楚了。（该代码能直接AC掉下面给出的洛谷的例题）

三、题例

1、上链接

【模板】线性筛素数 - 洛谷

力扣

2、简单思路

同上。

3、代码

（1）埃氏筛python版

1. class Solution:
2. global v
3. def is_prime(self,n:int)->int:
4. cnt=0
5. v[0]=v[1]=1
6. for i in range(2,n+1):
7. if v[i]==0:
8. cnt+=1
9. for j in range(i+i,n+1,i):
10. v[j]=1
11. return cnt
13. if __name__=='__main__':
14. v=[0]*10001000
15. n=int(input())
16. # print(type(n))
17. res=Solution.is_prime(Solution,n)
18. print(res)
21. '''
22. 下面的代码能AC掉力扣上的题:
23. class Solution:
24. def countPrimes(self, n: int) -> int:
25. v=[0]*10000000
26. cnt=0
27. v[0]=v[1]=1
28. for i in range(2,n):
29. if v[i]==0:
30. cnt+=1
31. for j in range(i+i,n+1,i):
32. v[j]=1
33. return cnt
34. '''

（2）欧拉筛python版

1. # 下面代码AC不了洛谷的例题，主要是因为空间的问题，算法思想和代码实现是没问题的
2. class Solution:
3. global v,prime
4. def is_prime(self,n:int)->None:
5. cnt=0
6. v[0]=v[1]=1
7. for i in range(2,n+1):
8. if v[i]==0:
9. v[i]=i
10. cnt+=1
11. prime[cnt]=i
12. for j in range(1,cnt+1):
13. if prime[j]>n//i or prime[j]>v[i]:
14. break
15. v[i*prime[j]]=prime[j]
17. if __name__=='__main__':
18. v=[0]*55001000
19. prime=[0]*800100
20. n,q=map(int,input().split())
21. # print(type(n))
22. Solution.is_prime(Solution,n)
23. for _ in range(q):
24. k=int(input())
25. print(prime[k])

另一个模板python代码：

1. # 线性筛质数
2. N=1000010
3. n=int(input())
4. cnt=0 # 用来计算有几个素数
5. primes=[] # 用来存素数
6. def get_primes(n):
7. global cnt,primes
8. st=[False for i in range(N)] # 是否被筛过
9. for i in range(2,n+1):
10. if(st[i]==0): # 如果没被筛过 是素数
11. primes.append(i) # 放到素数列表中
12. cnt+=1
13. for j in range(N):
14. if(primes[j]>n//i): break # 枚举已经筛过的素数
15. st[primes[j]*i]=1 # 将他们标为已经筛过了
16. if(i%primes[j]==0): break
17. get_primes(n)
18. print(cnt)
20. '''
21. （1）对于 visit[i*prime[j]] = 1 的解释： 这里不是用i的倍数来消去合数，而是把 prime里面纪录的素数，升序来当做要消去合数的最小素因子。
22. （2）对于 i%prime[j] == 0 就break的解释 ：当 i是prime[j]的倍数时，i = kprime[j]，如果继续运算 j+1，i * prime[j+1] = prime[j] * k prime[j+1]，这里prime[j]是最小的素因子，当i = k * prime[j+1]时会重复，所以才跳出循环。
23. 举个例子 ：i = 8 ，j = 1，prime[j] = 2，如果不跳出循环，prime[j+1] = 3，8 * 3 = 2 * 4 * 3 = 2 * 12，在i = 12时会计算。因为欧拉筛法的原理便是通过最小素因子来消除。
24. '''

以上，埃氏筛与欧拉筛（线性筛）

祝好