素数筛模板

前言

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

问题：

判定一个数是否为素数：

想都不想的方法：

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

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
 

暴力从开始判断的方法。复杂度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;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
 

这种情况能够基本单输入的素数问题。但是遇到多个输入肯定也会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; }
		}
	}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
 

欧拉筛——线性筛

对于上述的埃氏筛，虽然能解决大部分的问题。但是不难发现里面还是有挺多不够精简的地方，比如有的地方会重复访问。而欧拉筛在埃氏筛的基础上进行优化，达到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; }
		}

	}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
 

• 如果对后端、爬虫、数据结构算法等感性趣欢迎关注我的个人公众号交流：bigsai
  

文章来源: bigsai.blog.csdn.net，作者：Big sai，版权归原作者所有，如需转载，请联系作者。

原文链接：bigsai.blog.csdn.net/article/details/90453024