素数筛模板

前言

在判定素数的问题中，随着不断学习，里面的拓展性也在不断地增加。

问题：

判定一个数是否为素数：

想都不想的方法：

static boolean isprime(int value){ for(int i=2;i<value;i++) { if(value%i==0) {return false;} } return true; }

暴力从开始判断的方法。复杂度O(n)。当数据大于1e7左右基本就爆了。更别说多组输入了

稍微思考数据组成

对于一个数n如果不是素数，一定有a*b=n（a<b）;a<根号n，b>根号n，所以只要出现一定是成双成对。所以你只要找到1个就能说明这个数不是素数。所以从开始遍历到a是最省时的方法。因为a是log级。算法复杂度为O(logn)所以代码为：

static boolean isprime(int value) { for(int i=2;i*i<value+1;i++) { if(value%i==0) {return false;} } return true; }

这种情况能够基本单输入的素数问题。但是遇到多个输入肯定也会GG的。

埃拉托斯特尼(Eratosthenes)筛法

问题：多个输入，问关于素数相关的问题。 如果用上述方法肯定爆。多组输入的最好解决办法是打表。至于打表，如果上述的打表nlogn打表的话会TLE，所以就要换一种思考方式。

埃氏筛的核心思想就是将素数的倍数确定为合数。对于一个从2开始连续数据，我们假设其中每一个都是素数。如果一个数为素数，那么这个数的倍数一定也是素数。所以算法大致流程： 2： [i=(2+2)—>(+2)数组尾]，4,6,8,10 * * 不是素数 3： [i=(3+3)—>(+3)数组尾],6,9,12 * * 不是素数 4： [i=4]不是素数，跳过 5: . . . . . . . . . . . . 这个到除了前面几次的计算量多一点，到后面随着数据增大对整个复杂度相加是比较小的，算法复杂度为O(nloglogn);别小瞧多的这个logn，数据量大一个log可能少不少个0，那时间也是十倍百倍甚至更多的差距。 具体代码为

static boolean isprime[]; static long prime[]; static void getprime() { prime=new long[100001];//记录第几个prime int index=0; isprime=new boolean [1000001]; for(int i=2;i<1000001;i++) { if(!isprime[i]) { prime[index++]=i; } for(int j=i+i;j<1000000;j=j+i)//他的所有倍数都over { isprime[j]=true; } } }

欧拉筛——线性筛

对于上述的埃氏筛，虽然能解决大部分的问题。但是不难发现里面还是有挺多不够精简的地方，比如有的地方会重复访问。而欧拉筛在埃氏筛的基础上进行优化，达到O(n)的复杂度。

static boolean isprime[]; static int prime[]; static void getprimeoula()// 欧拉筛 { prime = new int[100001];// 记录第几个prime int index = 0; isprime = new boolean[1000001]; for (int i = 2; i < 1000001; i++) { if (!isprime[i]) { prime[index++] = i; } for (int j = 0; j < index && i * prime[j] <= 100000; j++){ isprime[i * prime[j]] = true;// if (i % prime[j] == 0) break; } } } 如果对后端、爬虫、数据结构算法等感性趣欢迎关注我的个人公众号交流：bigsai Big sai 认证博客专家 数据结构与算法 爬虫 Java 原创公众号:「bigsai」，回复【bigsai】获取珍藏pdf书籍资源，回复【进群】即可加入leetcode打卡群。主要分享Java，数据结构与算法，期待你的关注！