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;
}

补充：软件开发 , C++ ,