素数筛法

对于单个素数的判断有许多方法，但是如果要判断出一个大范围内的素数，单个素数的判断方法仍然可行，但是时间复杂度就过高了，效率不够。本文列举了2种素数筛法：埃氏筛，欧拉筛。

埃氏筛

一个数的倍数一定不是素数，那么对于每个数只需要把他的倍数筛掉，而对于每个合数 \(x\) ，一定能被一个素数 \(i\) \((2\leq i\leq \sqrt x)\) 筛掉，遍历区间后剩下的就一定是素数。

时间复杂度为 \(O(nloglogn)\) 。

///埃氏筛，O(nloglogn)，通过标记素数的倍数筛掉合数
const int N = 1e6+7;
bool vis[N];
int prime[N],cnt;
void eratosthenes_screen(int n){
    for(int i = 2;i<=n;i++){
        if(vis[i]) continue;
        prime[cnt++] = i;
        for(int j = 2;j*i<=n;j++) vis[i*j] = 1;
    }
}

欧拉筛(线性筛)

1. 对于区间 \([1,n]\) 中任何一个合数 \(x\) ，设其最小质因子为 \(p\) ，那么一个区间的所有合数都能通过它的最小质因子 \(p\) 和数 \(\frac{x}{p}\) 以 \(\frac{x}{p}\times p\)的方式筛掉，因此每个合数都能被它的最小质因子 \(p\) 筛掉。而对于数 \(\frac{x}{p}\) ，其最小质因子 \(p\prime\)一定大于等于 \(p\) ，因此 \(x\) 一定能在遍历 \(\frac{x}{p}\) 的倍数到其最小质因子 \(p\prime\) 前被筛掉。

2. 对于区间的任意的数 \(i\) ，设其最小质因子为 \(p\) ，最多只需要从 \(i\) 的最小素数倍的合数，即 \(2\times i\) ，筛到其 \(p\) 倍的合数 \(p\times i\) 。因为对于任何 \(i\) 的大于 \(p\)倍的素数倍合数 \(x\) ，其最小质因子一定是 \(p\) ，因此能被 \(\frac{x}{p}\) \((i<\frac{x}{p} 筛掉。

综上，我们得到结论：对于 \([1,n]\) 内的任意数 \(i\) ，设其最小质因子是 \(p\)，我们只需要筛掉数\(i\times j\) \((2\leq j \leq p, i\times j\leq n)\) ，最终每个合数都会被其最小质因子筛掉。

时间复杂度为 \(O(n)\)，因为是线性复杂度，所以也被称为线性筛。

///欧拉筛，O(n)，每个合数只会被最小质因子筛掉
const int N = 1e6+7;
bool vis[N];
int prime[N],cnt;
void euler_screen(int n){
    for(int i = 2;i<=n;i++){
        if(!vis[i]) prime[cnt++] = i;
        for(int j = 0;j