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

���录

一、前言

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

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开始，将每个质数的倍数都标记成合数，以达到筛选素数的目的。

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

埃氏筛核心代码：

static final int N = 1e7 + 5;static int[] st = new int[N];public static void E_sieve(int  n){for(int i = 2; i n//i): break # 枚举已经筛过的素数            st[primes[j]*i]=1 # 将他们标为已经筛过了            if(i%primes[j]==0): breakget_primes(n)print(cnt)'''（1）对于 visit[i*prime[j]] = 1 的解释： 这里不是用i的倍数来消去合数，而是把 prime里面纪录的素数，升序来当做要消去合数的最小素因子。（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]时会重复，所以才跳出循环。举个例子 ：i = 8 ，j = 1，prime[j] = 2，如果不跳出循环，prime[j+1] = 3，8 * 3 = 2 * 4 * 3 = 2 * 12，在i = 12时会计算。因为欧拉筛法的原理便是通过最小素因子来消除。'''

祝好