埃氏筛与欧拉筛(线性筛)
后台-插件-广告管理-内容页头部广告(手机) |
目录
一、前言
二、埃氏筛与欧拉筛(线性筛)
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++)
- {
- if(st[i] == 0)
- {
- for(int j = 2 * i; j <= n; j += i)
- st[j] = 1; // j是i的一个倍数,j是合数,筛掉。
- }
- }
- }
优化后的埃氏筛:
- 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; i++)
- {
- if(st[i] == 0)
- {
- for(int j = i * i; j <= n; j += i)
- st[j] = 1; // j是i的一个倍数,j是合数,筛掉。
- }
- }
- }
优化后的时间复杂度可以近似看成 O(n) 了。但是,我们还可以更快,那就是欧拉筛。
补充:
算法代码(C++):
- #include
- using namespace std;
- //埃氏筛法
- bool v[100001000]; //v[i]为0代表数i为素数
- int cnt=0;
- void prime(int n){
- v[0]=v[1]=1;
- for(int i=2;i<=n;++i){ //注意这里也统计了等于n的数
- if(!v[i]){
- cnt++;
- for(int j=i+i;j<=n;j+=i){ //注意这里也统计了等于n的数
- v[j]=1;
- }
- }
- }
- }
- int main(){
- int n;
- cin>>n;
- prime(n);
- cout<
- return 0;
- }
对该代码稍作修改便可AC掉下面给出的力扣的例题。
(2)欧拉筛法
欧拉筛法的原理同埃氏筛法,只不过多了一个判断删除与标记最小质因子的过程。
在埃氏筛法中,一个合数来说可能会被筛多次,比如6可以被2筛去,也可以被3筛去,而欧拉筛要做的事情就是让一个合数只被筛一次。
首先,任何合数都能表示成多个素数的积。所以,任何的合数肯定有一个最小质因子。我们通过这个最小质因子就可以判断什么时候不用继续筛下去了。
欧拉筛核心代码:
- static final int N = 1e7 + 5;
- static int[] st = new int[N], primes = new int[N];
- void ola(int n)
- {
- for (int i = 2; i <= n; i ++ )
- {
- if (st[i] == 0) primes[cnt ++ ] = i;//将质数存到primes中
- for (int j = 0; primes[j] <= n / i; j ++ )//要确保质数的第i倍是小于等于n的。
- {
- st[primes[j] * i] = 1;
- if (i % primes[j] == 0) break;
- }
- }
- }
欧拉筛法的基本思想 :
在埃氏筛法的基础上,让每个合数只被它的最小质因子筛选一次,以达到不重复的目的。
比如说: 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++):
- #include
- using namespace std;
- //欧拉筛法
- int v[100001000]; //v[i]=a代表数i的最小质因数为a
- int prime[600000];
- int cnt=0;
- void is_prime(int n){
- v[0]=v[1]=1;
- for(int i=2;i<=n;++i){ //注意这里也统计了等于n的数
- if(!v[i]){ //从小到大枚举,能保证如果v[i]==0,那么i就是素数
- v[i]=i;
- prime[++cnt]=i;
- }
- //注意一点,i显然永远是大于或等于prime[j]的,但 v[i] 不一定
- //而一个质数的最小质因数也就是其本身,即prime[j]的最小质因数是prime[j]
- for(int j=1;j<=cnt;++j){
- //因为从小到大枚举,所以当前的大于,以后的一定大于
- if(prime[j]>n/i||prime[j]>v[i])
- break;
- v[i*prime[j]]=prime[j];
- // i*prime[j] 代表当前数乘以之前出现的素数
- // v[i*prime[j]] 的最小质因数是prime[j]
- // 当 i%prime[j]==0 时,显然成立
- // 当 i%prime[j]!=0 时,又由于上面的 if 判断保证了 v[i]>=prime[j],所以也成立
- /**
- 解释上面的这个 if 判断条件
- 第一个条件 prime[j]>n/i 用于防止越界
- 第二个条件 prime[j]>v[i],如果 i 的最小质因子比prime[j]的最小质因子小,那么
- v[i*prime[j]]应该等于v[i],但是现在用当前数的最小质因子给 i*prime[j] 的最小质因子赋值会导致重复赋值,
- 因为后面 i==(i*prime[j])/v[i] 的时候prime[i]能在不大于v[i]的情况下 v[i*prime[j]]=prime[j]
- 也就是说,我们要保证prime[j]为最小质因子,这样能减少操作次数 */
- }
- }
- }
- int main(){
- int n,q;
- cin>>n>>q;
- is_prime(n);
- for(int i=0;i
- int k;
- cin>>k;
- cout<
- }
- return 0;
- }
代码为何这样写看注释,解释得非常清楚了。(该代码能直接AC掉下面给出的洛谷的例题)
三、题例
1、上链接
【模板】线性筛素数 - 洛谷
力扣
2、简单思路
同上。
3、代码
(1)埃氏筛python版
- class Solution:
- global v
- def is_prime(self,n:int)->int:
- cnt=0
- v[0]=v[1]=1
- for i in range(2,n+1):
- if v[i]==0:
- cnt+=1
- for j in range(i+i,n+1,i):
- v[j]=1
- return cnt
- if __name__=='__main__':
- v=[0]*10001000
- n=int(input())
- # print(type(n))
- res=Solution.is_prime(Solution,n)
- print(res)
- '''
- 下面的代码能AC掉力扣上的题:
- class Solution:
- def countPrimes(self, n: int) -> int:
- v=[0]*10000000
- cnt=0
- v[0]=v[1]=1
- for i in range(2,n):
- if v[i]==0:
- cnt+=1
- for j in range(i+i,n+1,i):
- v[j]=1
- return cnt
- '''
(2)欧拉筛python版
- # 下面代码AC不了洛谷的例题,主要是因为空间的问题,算法思想和代码实现是没问题的
- class Solution:
- global v,prime
- def is_prime(self,n:int)->None:
- cnt=0
- v[0]=v[1]=1
- for i in range(2,n+1):
- if v[i]==0:
- v[i]=i
- cnt+=1
- prime[cnt]=i
- for j in range(1,cnt+1):
- if prime[j]>n//i or prime[j]>v[i]:
- break
- v[i*prime[j]]=prime[j]
- if __name__=='__main__':
- v=[0]*55001000
- prime=[0]*800100
- n,q=map(int,input().split())
- # print(type(n))
- Solution.is_prime(Solution,n)
- for _ in range(q):
- k=int(input())
- print(prime[k])
另一个模板python代码:
- # 线性筛质数
- N=1000010
- n=int(input())
- cnt=0 # 用来计算有几个素数
- primes=[] # 用来存素数
- def get_primes(n):
- global cnt,primes
- st=[False for i in range(N)] # 是否被筛过
- for i in range(2,n+1):
- if(st[i]==0): # 如果没被筛过 是素数
- primes.append(i) # 放到素数列表中
- cnt+=1
- for j in range(N):
- if(primes[j]>n//i): break # 枚举已经筛过的素数
- st[primes[j]*i]=1 # 将他们标为已经筛过了
- if(i%primes[j]==0): break
- get_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时会计算。因为欧拉筛法的原理便是通过最小素因子来消除。
- '''
以上,埃氏筛与欧拉筛(线性筛)
祝好
1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。
在线投稿:投稿 站长QQ:1888636
后台-插件-广告管理-内容页尾部广告(手机) |