Help Hanzo

题目

T组数据，每组数据给出a，b两个值，让求a<=x<=b中有多少个x是质数



分析

可以发现此题的a，b可以到2e9的范围，所以想要把这么大的范围质数筛选完是不可能的，筛质数有个常用的做法就是筛出sqrt(N)的质数，然后再用这些质数去筛后面的质数。
所以我们先把2~2^16范围的质数筛选出来，我们对其之后的合数进行质因数分解 其中必定有一个质数是在2~2^16中，否则这个数一定是大于的，并不在范围内。

所以，我们可以用前预筛选出来的质数(大概6000个)，去对a,b区间去掉合数,这里因为a，b可能非常大，所以我们把[a,b]映射到[0,b-a]。
如果我们可以直接在前6000个质数看有多少个质数落在这个区间

所以总到时间复杂度： 2s一般是可以过的

AC代码

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cstring>
#include <unordered_map>
#include <unordered_set>
using namespace std;
typedef long long ll;
const ll maxn = (1LL<<16)+10;
ll T,A,B;
bool vis[maxn],vis2[100010];
ll P[100010],tail;
void init(){
    for(int i = 2;i<maxn;i++){
        if(!vis[i]){
            P[tail++] = i;
            for(ll j = (ll)i*i;j<maxn;j+=i){
                vis[j] = true;
            }
        }
    }
}
ll test(ll a ,ll b){ //用于对拍
    ll cnt = 0;
    for(ll i = a;i<=b;i++){
        int tag = 1;
        for(ll j = 2;j*j<=i;j++){
            if(i%j ==0) {
                tag = 0;
                break;
            }
        }
        if(tag) cnt++;
    }
    return cnt;
}

ll solve(ll a,ll b){
    ll cnt = 0;
    if(b<maxn){
        for(int i = 0;i<tail;i++){
            if(P[i]>=a && P[i]<=b) cnt++;
            if(P[i]>b) break;
        }
    }else{
        memset(vis2,0,sizeof vis2);
        for(ll i = 0;i<tail;i++){
            for(ll j = (a+P[i]-1)/P[i];j<=b/P[i];j++){
                if(j == 1 || j == 0) continue;//质数的0倍，1倍不是合数，需要跳过
                vis2[P[i]*j-a] = true;
            }
        }
        for(ll i = 0;i<=b-a;i++){
            if(!vis2[i]) cnt++;
        }
    }
    return cnt;
}
int main(){
    init();
    cin>>T;
    int kase = 0;
    while(T--){
        scanf("%lld %lld",&A,&B);
        if(A==1) A = 2; //这个最好改成2
        printf("Case %d: %lld\n",++kase,solve(A,B));
    }

    return 0;
}