素数判定和素数筛

素数判定

埃氏筛法

1. 整体流程是从小到大遍历，并将利用小的因数将后面大的合数剔除掉
2. 原理就是合数和素数的判定条件
3. 边界条件就是不能超过n,可以从i*i开始比较
4. 复杂度是O(nloglogn)
   埃氏筛的时间复杂度为O(n log log n)，其中n是要筛选质数的范围。具体地，该算法的复杂度可以分为两部分：
   1.标记合数的复杂度：O(n)。因为每个数最多只会被标记一次，而每个数最多有log log n个质因数，所以总共需要进行O(n log log n)次操作。
   2.枚举质数的复杂度：O(n log log n)。因为每个质数最多只会被枚举一次，而n个数中质数的个数约为n/ln n，所以总共需要进行O(n/ln n)次操作。
   因此，总的时间复杂度为O(n log log n)。

版本1

bool is_prime[N];
int Eratosthenes(int n) {
  int p = 0;
  //初始化标记数组,先标记成都是素数,后面是合数就擦掉
  for (int i = 0; i <= n; ++i) {
    is_prime[i] = 1;
  }
  is_prime[0] = is_prime[1] = 0;

  for (int i = 2; i <= n; ++i) {
    if (is_prime[i]) {
      prime[p++] = i;  // prime[p]是
      if (i * i <= n && i*i > 0)//防溢出
      //i的倍数都是合数,实际上也是i*2,i*3，但由于在2-i-1时已经处理过了,
      //所以接下来从i*i,i*(i+1)=i*i+i,....
        for (int j = i * i; j <= n; j += i)
          is_prime[j] = 0;
    }
  }
  return p;
}

只筛奇数的版本

bool is_prime[N];
int Eratosthenes(int n) {
  int p = 0;
  for (int i = 0; i <= n; ++i){
    is_prime[i] = 1;
  } 
  is_prime[0] = is_prime[1] = 0;
  // i * i <= n 说明 i <= sqrt(n)
  //只需要筛一半
  for (int i = 2; i * i <= n; ++i) {
    if (is_prime[i]) {
      prime[p++] = i;

      for (int j = i * i; j <= n; j += i)
        is_prime[j] = 0;
    }
  }
  return p;
}

只保留奇数的版本

is_prime可以只申请n/2一半，因为偶数肯定是合数

线性筛

如果能让每个合数只被标记一次，复杂度就来到了O(n)

void init(int n) {
  for (int i = 2; i <= n; ++i) {
    if (!vis[i]) {
      pri[cnt++] = i;
    }
    for (int j = 0; j < cnt; ++j) {
      if ( (long long)(i * pri[j]) > n){
           break;
      } 
      vis[i * pri[j]] = 1;
      if (i % pri[j] == 0) {
        // i 之前被 pri[j] 筛过了
        // 由于 pri 里面质数是从小到大的，所以 i乘上其他的质数的结果一定会被
        // pri[j]的倍数筛掉
        break;
      }
    }
  }
}