Primes on Interval(欧拉筛+二分+滑动窗口)

【题面】

你决定用素数定理来做一个调查. 众所周知, 素数又被称为质数，其含义就是除了数字一和本身之外不能被其他任何的数字除尽.

现在给定一个正整数序列 ,+1,⋯ ,a,a+1,⋯,b (≤)(a≤b), 请找出一个最小值 l, 使其满足对于任意一个长度为 l 的子串, 都包含 k 个质数.

找到并输出符合要求的最小值 l, 如果不存在符合要求的长度 l, 则输出 −1−1.

【输入格式】

输入一行, 包含三个用空格隔开的整数 ,,a,b,k (1≤,,≤106;≤1≤a,b,k≤106;a≤b)

【输出格式】 输出一行, 为符合要求的最小值 l, 若不存在, 输出 −1−1.

输入输出样例

2 4 2

3

6 13 1

4

1 4 3

-1

//Primes on Interval: https://www.luogu.com.cn/problem/CF237C
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m,k,res,num,p[N],prime[N];
bool vis[N];
bool check(int u)//滑动窗口判断素数
{
    int hh=n-1,tt=n,cnt=0;//建立队头队尾
    while(hh-tt+1<u){//找到区间的第一个头
        hh++;
        if(!vis[hh]) cnt++;//先++;
    }
    while(hh<=m){
        if(cnt<k) return false;//判断
        hh++; if(!vis[hh]) cnt++;//向前滑动一位,并判断
        tt++; if(!vis[tt-1]) cnt--;//队尾也向前,如果划掉素数了就要减
    }
    return true;
}
int main()
{
    cin>>n>>m>>k;
    vis[1]=true;
    for(int i=2;i<=m;i++){
        if(!vis[i]) prime[++num]=i,p[i]=i;
        for(int j=1;prime[j]<=m/i;j++){
            vis[i*prime[j]]=true;
            if(!(i%prime[j])) break;
        }
    }
    if(!check(m-n+1)) return cout<<-1,0;
    int l=1,r=m+1;
    while(l<r){
        int mid=l+r>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    cout<<r;
    return 0;
}