哈尔滨理工大学软件与微电子学院程序设计竞赛 I-Prime

题解：
数据范围式1e7所以感觉尽量还是用一下欧拉筛吧，毕竟时间复杂度越低越好。
用visited数组记录，我们用前缀和来处理一下前i个数的质数个数，之后再O(1)的复杂度情况下即可查出。

/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
const int maxn = 1e7;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 100000000;
using namespace std;
bool visited[maxn+10];
int prim[1000000+5];
int ans[maxn+10];
void ispirm(){
    int cnt=0;
    memset(visited,true,sizeof(visited));
    for(int i=2;i<=maxn;i++){
        if(visited[i]) prim[cnt++]=i;
        for(int j=0;j<cnt&&prim[j]*i<=maxn;j++){
            visited[prim[j]*i]=false;
            if(i%prim[j]==0) break;
        }
    }
}
int main()
{
    ispirm();
    int t;
    cin>>t;
    for(int i=2;i<=maxn;i++){
        ans[i]=ans[i-1]+visited[i];
    }
    while(t--){
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%d\n",ans[y]-ans[x-1]);
    }
    return 0;
}