M - Help Hanzo

题目意思就是给定你一个数N，让你往下执行N组数据，每一组数据给会给你两个数a，b。问你在（a，b）之间

然后这里告诉你一个范围就是b-a<10^5

这道题目就是一个素数筛再加上区间映射。一开始上来想开个b那么大的数组，再暴力素数筛，看b那么大，不用说也知道没有戏了，想到之前一个数论结论（当一个数都不能被10^5里面的素数整除的话就证明这个数是素数）。然后现在就是一个空间映射问题了，当b<10^5，时候就裸暴力。

A[n]逻辑空间是a到b。这里有个问题就是空间要开到10^6才过，10^5就哇掉了。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int  vis[1001000];
int  isprim[1001000];
int visab[1001000];
int cnt;
void is_prim()
{
    cnt=-1;
    memset(vis,0,sizeof(vis));
    vis[1]=1;
    for(int i=2;i<=1001000;i++)
    {
        if(!vis[i])
        {
            isprim[++cnt]=i;
            for(long long j=2;i*j<=1001000;j++)
                vis[i*j]=1;
        }
    }
}
int main()
{
    is_prim();
    int T;
    scanf("%d",&T);
    int t=1;
    while(T--)
    {
        long long a,b;
        scanf("%lld %lld",&a,&b);
        int sum=0;
        if(b<=1000000)
        {
            for(long long i=a;i<=b;i++)
            {
                if(!vis[i])
                  sum++;
            }
        }
        else
        {
            memset(visab,0,sizeof(visab));
            for(int i=0;i<=cnt&&isprim[i]<=b;i++)
            {
                long long k=a/isprim[i];
                if(k*isprim[i]<a) k++;
                for(long long j=k*isprim[i];j<=b;j=j+isprim[i])
                    visab[j-a]=1;
            }
            for(long long i=a;i<=b;i++)
            {
                if(!visab[i-a])
                    sum++;
            }
        }
        printf("Case %d: %d\n",t++,sum);
    }
    return 0;
}