CF 237C (質數區間）

給定區間[a,b] 求l的最小值使[a,b]中任意長度為l的一段包含至少k個Prime
二分l

[cpp] 
#include<cstdio> 
#include<cstring> 
#include<cstdlib> 
#include<cmath> 
#include<algorithm> 
#include<functional> 
#include<iostream> 
using namespace std; 
#define MAXN (1000000+10) 
int a[MAXN],tot=0,x,y,k; 
bool b[MAXN]={0}; 
void work() 
{ 
    b[1]=1; 
    for (int i=2;i<=y;i++) 
    { 
        if (!b[i]) 
        { 
            tot++; 
            a[tot]=i; 
        } 
        for (int j=1;j<=tot;j++) 
        { 
            if (a[j]*i>y) break; 
            b[a[j]*i]=1; 
            if (!i%a[j]) break; 
        } 
    } 
} 
bool is_ok(int l) 
{ 
    int tot=0; 
    for (int i=x;i<=x+l-1;i++)  
        if (!b[i]) tot++; 
    if (tot<k) return false; 
    for (int j=x+l;j<=y;j++) 
    { 
        tot=tot+(!b[j])-(!b[j-l]); 
        if (tot<k) return false; 
    } 
    return true;     
} 
 
int main() 
{ 
    scanf("%d%d%d",&x,&y,&k); 
    work(); 
    int l=k,r=y-x+1; 
    if (l>r||!is_ok(r))  
    { 
        printf("-1\n"); 
        return 0; 
    } 
    for (int i=1;i<=60;i++) 
    { 
        if (l==r) break; 
        int m=(l+r)>>1; 
//      if (r-l==1) m++; 
        if (is_ok(m)) r=m; 
        else l=m+1;      
    } 
    printf("%d\n",l); 
//  while (1); 
    return 0; 
}