素数筛模板

前言

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

问题：

判定一个数是否为素数：

想都不想的方法：

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;
      }
    }
  }