埃氏筛与欧拉筛(线性筛)

这篇具有很好参考价值的文章主要介绍了埃氏筛与欧拉筛(线性筛)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

一、前言

二、埃氏筛与欧拉筛(线性筛)

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是合数,筛掉。
		}
	}
	
}

埃氏筛法,复习版数据结构与算法,1024程序员节,算法,python,c++,数据结构

优化后的埃氏筛:

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<iostream>
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<<cnt<<endl;
	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,我们就结束内层循环,为什么?

埃氏筛法,复习版数据结构与算法,1024程序员节,算法,python,c++,数据结构

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

算法代码(C++):

#include<iostream>
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<q;++i){
		int k;
		cin>>k;
		cout<<prime[k]<<endl;
	}
	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时会计算。因为欧拉筛法的原理便是通过最小素因子来消除。
'''

以上,埃氏筛与欧拉筛(线性筛)

祝好文章来源地址https://www.toymoban.com/news/detail-756452.html

到了这里,关于埃氏筛与欧拉筛(线性筛)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 欧拉函数和线性筛法:AcWing 874. 筛法求欧拉函数

    1. 属于是先手推数学式子,然后代码比较简单的题目 2. 线性筛法,之前接触过一道类似的线性筛法的题目:线性筛法 3. 线性筛法是一个算法模板 顺便写一下这一道题目的笔记:AcWing 868. 筛质数 4. 下面详细分析一下线性筛法之外的数学部分的内容 5. 从1一直到某一个质因子的

    2024年02月08日
    浏览(35)
  • [Go版]算法通关村第十三关黄金——数字数学问题之数论问题(最大公约数、素数、埃氏筛、丑数)

    题目链接:LeetCode-1979. 找出数组的最大公约数 辗转相除法其核心部分为:若r 是a ÷ b的余数,则 gcd(a, b)=gcd(b, r) 题目链接:LeetCode-204. 计数质数 如果 x 是质数,那么大于 x 的 x 的倍数 2x,3x,… 一定不是质数。 时间复杂度分析: 外层循环的迭代次数是 n-2,即 O ( n ) O(n) O ( n ) 次

    2024年02月11日
    浏览(38)
  • 湘大 XTU OJ 1345 素数字符串 题解:欧拉筛法 前缀和 ‘\0‘ sprintf

    素数字符串 我们将素数从小到大依次书写,可以得到一个字符串\\\"23571113⋯\\\",已知一个数码d(0≤d≤9),求字符串在区间[L,R]之间的多少个d? 第一行是一个整数T(1≤T≤10000),表示样例的个数。 每个样例是一行, 为3个整数,区间L,R,(1≤L≤R≤1000000)和数码d。 区间从1开始计数。 每

    2024年02月12日
    浏览(33)
  • 筛法--朴素筛法和埃式筛法和线性筛法

    朴素筛法:  这个朴素算法的 思路 就是,枚举这些数,首先在st数组初始化时,就是已经把这个数组内的值都初始化为0,也就是说都是看成是质数。。。。 然后,如果这个数确实是质数,那么我们就可以把这个数放入我们存质数的数组里面去,然后对质数的个数进行增加,

    2024年02月07日
    浏览(58)
  • 线性筛法 O(n)

      线性筛O(n)而埃氏筛进行筛时会重复筛,线性筛不会出现这个问题 线性筛:对于某个合数使用其最小质因子筛去 st[primes[j] * i] = true;  因为这句话只会被执行一次,所以复杂度O(fn)  

    2023年04月09日
    浏览(91)
  • 【考研复习】24王道数据结构课后习题代码|2.3线性表的链式表示

    删除结点:1、2、4 就地逆置:5、 合并链表 分解链表:10、11、 去除重复元素:12、 并集:14、15 循环链表:17、18、19、20 头插法、尾插法重点基础必掌握。 判断是否有环:21 用函数递归调用删除结点。 注意删除结点的时候可能断链。 利用函数调用的特性反向输出。 设置保

    2024年02月13日
    浏览(44)
  • 线性筛(欧拉筛)C语言

    前言 线性筛是一种用于找出小于等于给定数值的所有质数的高效算法。它是一种改进版的埃拉托斯特尼筛法,可以在更短的时间内计算出大量的质数。其有时间复杂度低,空间复杂度低,可扩展性强的优点。今天我们就来给大家讲解线性筛的实现。话不多说,我们现在开始!

    2024年02月04日
    浏览(29)
  • 整数因子分解问题(分治法&&欧拉线性筛素数)

    问题描述: 大于1 的正整数n 可以分解为:n=x1*x2*…*xm。 例如,当n=12 时,共有8 种不同的分解式: 12=12; 12=6*2; 12=4*3; 12=3*4; 12=3*2*2; 12=2*6; 12=2*3*2; 12=2*2*3 。 编程任务: 对于给定的正整数n,编程计算n 共有多少种不同的分解式。 数据输入: 由文件input.txt 给出输入数据

    2024年01月17日
    浏览(42)
  • 动态维护直径 || 动态维护树上路径 || 涉及LCA点转序列 || 对欧拉环游序用数据结构维护:1192B

    https://www.luogu.com.cn/problem/CF1192B 对于直径的求法,常用dp或两次dfs,但如果要动态维护似乎都不太方面,那么可以维护树上路径最大值。 树上路径为: d e p u + d e p v − 2 × d e p l c a ( u , v ) dep_u+dep_v-2times dep_{lca(u,v)} d e p u ​ + d e p v ​ − 2 × d e p l c a ( u , v ) ​ 为方便求 l c

    2024年02月11日
    浏览(27)
  • 数据结构第13周 :( 迪杰斯特拉最短路径 + 弗洛伊德求最短路径 + 欧拉回路 + Invitation Cards)

    【问题描述】 在带权有向图G中,给定一个源点v,求从v到G中的其余各顶点的最短路径问题,叫做单源点的最短路径问题。 在常用的单源点最短路径算法中,迪杰斯特拉算法是最为常用的一种,是一种按照路径长度递增的次序产生最短路径的算法。 在本题中,读入一个有向图

    2024年02月13日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包