关于筛法 | Shirakami Lynrics

什么是筛法？

筛法的直接用途是用来解决寻找$1~N$中的质数的问题的。
也常用来间接解决一些其他的数论问题。

最简单的筛法：艾氏筛法

简介

艾氏筛法是比较直接就能想到的一种筛法。
每找到一个质数，就用它来筛掉后面所有它的倍数。
这样每找到一个没有被筛掉的数，由于前面所有比他小的数都不是它的因数，所以它一定是一个质数。

代码

代码也很容易实现：

#include <vector>
#include <cmath>

auto eratosthenes(int upperbound) 
{
  std::vector<bool> flag(upperbound + 1, true);
  flag[0] = flag[1] = false; //exclude 0 and 1
  for (int i = 2; i <= sqrt(upperbound); ++i) 
  {
    if (flag[i]) 
    {
      for (int j = i * i; j <= upperbound; j += i)
      {
        flag[j] = false;
      }
    }
  }
  return flag;
}

它的复杂度是$O(nloglogn)$。

欧拉筛法

简介

上面的筛法虽然复杂度已经很低了，但是我们仍然需要一种更加快速的筛法。

很明显，我们上一个算法不够迅速的原因是有的数字被筛了多次。如果能避免这种情况，我们的算法就会更快。

欧拉筛法可以保证范围内的每个合数都被删掉（在 bool 数组里面标记为非素数），而且任一合数只被：

“最小质因数 × 最大因数（非自己） = 这个合数”

的途径删掉。由于每个数只被筛一次，时间复杂度为 O(n)。

代码

先上代码：

#include <cstdio>
#include <cstring>

bool isPrime[100000010];
//isPrime[i] == 1表示：i是素数
int Prime[6000010], cnt = 0;
//Prime存质数

void GetPrime(int n)//筛到n
{
    memset(isPrime, 1, sizeof(isPrime));
    //以“每个数都是素数”为初始状态，逐个删去
    isPrime[1] = 0;//1不是素数
    for(int i = 2; i <= n; i++)
    {
        if(isPrime[i])//没筛掉 
            Prime[++cnt] = i; //i成为下一个素数
        for(int j = 1; j <= cnt && i*Prime[j] <= n/*不超上限*/; j++) 
        {
            //从Prime[1]，即最小质数2开始，逐个枚举已知的质数，并期望Prime[j]是(i*Prime[j])的最小质因数
            //当然，i肯定比Prime[j]大，因为Prime[j]是在i之前得出的
            isPrime[i*Prime[j]] = 0;
            if(i % Prime[j] == 0)//i中也含有Prime[j]这个因子
                break; //重要步骤。见原理
        }
    }
}

int main()
{
    int n, q;
    scanf("%d %d", &n, &q);
    GetPrime(n);
    while (q--)
    {
        int k;
        scanf("%d", &k);
        printf("%d\n", Prime[k]);
    }
    return 0;
}