素数与筛法

埃氏筛

筛到一个质数后，把它所有的倍数全部删去。非常简单易懂。

复杂度 $O(n \log \log n)$ 。（证明略去）

bool prime[N];

void solve(int n){
    for(int i=2;i<=n;i++)prime[i]=1;
    for(int i=2;i<=n;i++){
        if(!prime[n])continue;

        // 优化：从质数 i 的 i 倍开始筛
        // 因为 i 的 2~(i-1) 倍一定有一个更小的质数因子
        // 所以已经被筛掉了
        for(int j=i*i;j<=n;j+=i){
            prime[j]=0;
        }
    }
}

线性筛（欧氏筛）

埃氏筛的效率还是不够高，我们尝试构建一个复杂度为 $O(n)$ 的筛法。

线性筛的思路是对于一个数（不一定是质数），筛掉它的一些质数倍（质数倍的质数应该小于它的最小值质因数）。

int v[N]; // v[i] 是 i 的最小质因数
int prime[N];
int cnt=0;

void solve(int n){
    for(int i=2;i<=n;i++){
        if(v[i]==0){
            v[i]=i;
            prime[++cnt]=i;
        }
        for(int j=1;j<=cnt;j++){
            // 在 oi-wiki 上，第一个条件也写作 i%prime[j]==0，这两个是等价的
            if(prime[j]>v[i] || i*prime[j] > n){
                break;
            }
            v[i*prime[j]]=prime[j];
        }
    }
}

在线性筛中，一个合数会且仅会被筛一遍，并且是被它的最小质因数筛掉的。

我们来证明一下为什么一个合数会且仅会被筛一遍：

先证至少会被筛一遍：

考虑合数 $N = p_1 p_2 \dots p_n$ （设 $p_1 \le p_2 \le \dots <p_n$ ）。

则在循环到合数 $N_0 = p_2 p_3 \dots p_n$ 时，一定会在第二重循环中循环到 $p_1$ （因为合数 $p_2 \dots p_n$ 的最小质因数为 $p_2$ ， $p_1 \le p_2$ ，循环不会跳出）
只会被筛一遍

那么，会不会一个合数被筛了很多次呢？你可能会有疑问，合数 $N = p_1 p_2 \dots p_n$ （ $p_1 \le p_2 \le \dots \le p_n$ ）会不会在之前循环到合数 $N_1 = p_1 p_3 p_4 \dots p_n$ 时先把它乘上 $p_2$ ，把 $N$ 筛了两次呢？（此时等号 $p_1=p_2$ 无法取到，因为 $N_1 \neq N_0$ ）

这是不会的，因为 $N_1$ 的最小值因数是 $p_2$ ，而 $p_2 > p_1$ ，循环已经跳出了。这就是我们写的 prime[j]>v[i] 条件的作用。

例题

求出区间 $[L,R]$ 之间的整数中，相邻质数的差最小值和最大值。

数据范围： $1 < L < R < 2^{31}$ ， $R-L \le 10^6$ 。

样例输入：1 11

样例输出：1 4 （2 和 3 差 1，7 和 11 差 4）

首先，筛出 $2\sim\sqrt{R}$ 中所有的质数。

然后将 $L\sim R$ 范围内这些质数的倍数全部删去即可。

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6+5;

int cnt=0;
int v[N];
int prime[N];

void init(int n){
    for(int i=2;i<=n;i++){
        if(v[i]==0){
            v[i]=i,prime[++cnt]=i;
        }

        for(int j=1;j<=cnt;j++){
            if(v[i]<prime[j] || i*prime[j]>n){
                break;
            }
            v[i*prime[j]]=prime[j];
        }
    }

}


bool x[N];

int main(){
    int l,r;
    scanf("%d%d",&l,&r);
    init(sqrt(r));

    for(int i=1;i<=cnt;i++){
        for(int j=max(2,l/prime[i]);prime[i]*j<=r;j++){
            x[j*prime[i]-l]=1;
        }
    }

    int maxn = -1;
    int minn = INT_MAX;
    int last=-1;
    for(int i=0;i<=r-l;i++){
        if(x[i])continue;
        if(last==-1){last=i;continue;}
        maxn = max(maxn,i-last);
        minn = min(minn,i-last);
        last = i;
    }

    printf("%d %d\n",minn,maxn);
    return 0;
}