【题面】
你决定用素数定理来做一个调查. 众所周知, 素数又被称为质数，其含义就是除了数字一和本身之外不能被其他任何的数字除尽.
现在给定一个正整数序列 ,+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.
输入输出样例
输入 #1
2 4 2
输出 #1
3
输入 #2
6 13 1
输出 #2
4
输入 #3
1 4 3
输出 #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; }