Help Hanzo LightOJ - 1197
区间素数筛


const int LEN  = 1e6+1;
bool vis[LEN];
LL Prime[LEN];
int cnt = 1;
void init(void)
{
    int n = 70000;
    for(int i = 2; i <= n; ++i)
    {
        if(!vis[i])
        {
            Prime[cnt++] = i;
            for(LL j = (LL)i +  i; j <= n; j += i)
                vis[j] = 1;
        }

    }
}
bool  sign[200000];
int main(void)
{
    init();
    int T;
    cin>>T;
    int kase = 0;
    while(T--)
    {
        LL a,b;

        cin>>a>>b;
        int len = b-a+1;
        int num = 0;
        me(sign);
        int t = sqrt(b);
        for(int i = 1; i < cnt&&Prime[i] <= t; ++i)
        {
            LL tmp = max(a/Prime[i],(LL)2);
            if(tmp*Prime[i] < a)
                tmp++;
            while(tmp * Prime[i] <= b)
            {
                if(tmp*Prime[i]-a>100000)
                while(1);
                else
                sign[tmp*Prime[i]-a] = 1;
                tmp++;
            }
        }
        for(int i = 0; i < len; ++i)
        {
            if(!sign[i])
                num++;
        }
        if(a==1)
            num--;
        printf("Case %d: %d\n",++kase,num);
    }
    return 0;
}