素数筛模板

前言

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

问题：

判定一个数是否为素数：

想都不想的方法：

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];//记录第几个primeint 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];// 记录第几个primeint 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
  

《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读

总结

以上是生活随笔为你收集整理的素数筛模板的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。