素数打表,加上sum[i]数组表示1-i中有多少个素数
二分查找
#include <iostream>
#include <cmath>
using namespace std;
#define max 1000005
int phi[max],sum[max];
int a,b,k;
void getp(){
for(int i=2;i<max;i++){phi[i]=0;sum[i]=0;}
phi[1]=1;sum[1]=0;
sum[0]=0;
for(int i=2;i<max;i++){
sum[i]=sum[i-1];
if(!phi[i]){
sum[i]++;
for(int j=i*2;j<max;j+=i){
phi[j]=1;
}
}
}
}
bool check(int c){
for(int x=a;x<=b-c+1;x++){
if(sum[x+c-1]-sum[x-1]<k)return false;
}
return true;
}
int main(){
getp();
cin>>a>>b>>k;
if(sum[b]-sum[a-1]<k){
cout<<"-1"<<endl;
return 0;
}
int L=1,R=b-a+1,ans;
while(L <= R){
int mid = (L+R)/2;
if(check(mid)) ans = mid,R = mid-1;
else L = mid+1;
}
cout<<ans<<endl;
return 0;
}
#include <iostream> #include <cmath> using namespace std; #define max 1000005 int phi[max],sum[max]; int a,b,k; void getp(){ for(int i=2;i<max;i++){phi[i]=0;sum[i]=0;} phi[1]=1;sum[1]=0; sum[0]=0; for(int i=2;i<max;i++){ sum[i]=sum[i-1]; if(!phi[i]){ sum[i]++; for(int j=i*2;j<max;j+=i){ phi[j]=1; } } } } bool check(int c){ for(int x=a;x<=b-c+1;x++){ if(sum[x+c-1]-sum[x-1]<k)return false; } return true; } int main(){ getp(); cin>>a>>b>>k; if(sum[b]-sum[a-1]<k){ cout<<"-1"<<endl; return 0; } int L=1,R=b-a+1,ans; while(L <= R){ int mid = (L+R)/2; if(check(mid)) ans = mid,R = mid-1; else L = mid+1; } cout<<ans<<endl; return 0; }
CodeForces 237C,布布扣,bubuko.com
原文:http://www.cnblogs.com/Mr-Xu-JH/p/3871965.html