素数打表，加上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;

}