欧拉线性筛法（素数模板）

╰半橙微兮° 2023-07-01 15:00 6阅读 0赞

# 什么是素数？ #

**ans：** 素数也又称质数。一个大于 1 的自然数，除了 1 和它自身外，不能被其他自然数整除的数叫做质数。最小的质数是 2，它也是唯一的偶数质数。最前面的质数依次排列为：2，3，5，7，11等。比 1 大但不是质数的数称为合数

# 普通素数的模板 #

bool isprime(int a)
    { 
        if(a <= 1) return false;
        for(int i = 2; i <= sqrt((double)a); i++)
            if(a % i == 0)
                return false;
        return true;
    }

# 超大素数的模板 #

#include <bits/stdc++.h>
    #define _for(i,a,b) for(int i=a;i<b;i++)
    using namespace std;
    typedef long long LL;
    
    const int N=1e6;
    int pre[N],tmp;
    bool vis[N];
    void prime() //用到了 N、tmp 和 pre[N] 和 vis[N] 
    { 
    	_for(i,2,N-10)
    	{ 
    		if(!vis[i])
    			pre[tmp++]=i;
    		for(int j=0;j<tmp&&i*pre[j]<N-5;j++)
    		{ 
    			vis[i*pre[j]]=1;
    			if(i%pre[j]==0)break;
    		}
    	}
    }
    int main()
    { 
    	prime();
    	_for(i,0,10)
    	{ 
    		LL ans = pre[i];
    		cout<<ans<<' ';
    	}
    	return 0;
    }

Output
    2 3 5 7 11 13 17 19 23 29

### 补充 ###

vis 数组存储的是每个下标的数字是不是素数，0 代表是素数，1 代表不是素数  
如 `vis[2]=0 , vis[3]=0 , vis[4]=1` ，但是很重要的一点是虽然下标 0 和 1 不是素数  
`vis[0]=0 , vis[1]=0` ，却是这样的，尤其要注意哦~

发表评论取消回复

表情：

评论列表（有 0 条评论，6人围观）

还没有评论，来说两句吧...

相关阅读

相关欧拉筛&&埃氏筛

数论——欧拉筛、埃氏筛 `记录一点关于数论的知识，该知识点本身不难，主要是学习一下思想~` -------------------- 文章目录数论——欧

向右看齐/ 2024年03月30日 12:54/ 0 赞/ 101 阅读

相关关于欧拉筛法和普通筛法

为的是让一个合数只让最小的一个素数筛去 prime\[\]数组中的素数是递增的,当i能整除prime\[j\]，那么i\prime\[j+1\]这个合数肯定被pri

「爱情、让人受尽委屈。」/ 2024年02月17日 21:36/ 0 赞/ 97 阅读

相关欧拉函数 AcWing 874. 筛法求欧拉函数

欧拉函数 AcWing 874. 筛法求欧拉函数原题链接 [AcWing 874. 筛法求欧拉函数][AcWing 874.] 算法标签数学知识欧拉函

超、凢脫俗/ 2023年09月28日 11:41/ 0 赞/ 9 阅读

相关欧拉线性筛法（素数模板）

什么是素数？ ans：素数也又称质数。一个大于 1 的自然数，除了 1 和它自身外，不能被其他自然数整除的数叫做质数。最小的质数是 2，它也是唯一的偶数质数。最前面的质

╰半橙微兮°/ 2023年07月01日 15:00/ 0 赞/ 7 阅读

相关【素数判断】埃氏筛法和欧拉筛法（线性筛法）

埃氏筛法埃氏筛法的原理是：给出要筛数值的范围n，找出以内的素数。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个质数，也就是3筛，把3留下，把3的倍数剔

本是古典何须时尚/ 2023年01月10日 10:28/ 0 赞/ 161 阅读

相关素数筛模板

查找N内所有素数 1.埃氏筛 include<iostream> using namespace std; typede

约定不等于承诺〃/ 2022年11月06日 00:59/ 0 赞/ 177 阅读

相关素数基本（埃氏筛法/线性筛法）

一、检查n是否为素数最简单思路：所有可能的因数全部试一遍。 int gg(int n) { for(int i=2;i<n;i

拼搏现实的明天。/ 2022年05月17日 06:10/ 0 赞/ 284 阅读

相关素数线性筛模板

[参考于该博客][Link 1] int Mark[MAXSIZE]; int prime[MAXSIZE]; //判断是

╰+哭是因爲堅強的太久メ/ 2022年05月14日 03:36/ 0 赞/ 255 阅读

相关数论 - 欧拉函数【普通求法 + 筛法求欧拉函数】

欧拉函数 1.定义对于正整数n,欧拉函数是小于或等于n的正整数中(即1-n中)与n互质的数的数目，记作φ(n) 其中φ(1)=1。 2求n的

向右看齐/ 2021年07月24日 23:53/ 0 赞/ 459 阅读

相关埃拉托色尼筛法（素数筛）

列举大于等于2的整数，将其倍数划掉，往后遍历发现被划掉的直接略过，还没被划掉的则是质数（表示其不是前面任何一个数的倍数，也即没有除1和本身外的因子）。时间复杂度 O(Nlogl

骑猪看日落/ 2021年07月16日 21:52/ 0 赞/ 438 阅读