Codeforces Round #226 (Div. 2) C - Bear and Prime Numbers

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
using namespace std;
int s[10000005]={0},r[1000005],d[10000005]={0},ct[10000005]={0},add[10000005]={0};
vector<int> pr;
int main(){
    int i,j,l,n,m,p,x,y,ans=0,L,R,M;
    for(i=2;i<=10000000;i++){
        if(s[i]==0){
            for(j=i+i;j<=10000000;j+=i)
                s[j]=1;
        }
    }
    for(i=10000000;i>1;i--)
        if(!s[i]){
            d[i]=pr.size();
            pr.push_back(i);
        }

    pr.push_back(0);
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&r[i]);
        p=r[i];
        for(j=pr.size()-2;j>=0 && p>1 && pr[j]*pr[j]<=p;j--){
            if(p%pr[j]==0)
                ct[j]++;
            while(p%pr[j]==0){
                p/=pr[j];
            }
        }
        if(p>1) ct[d[p]]++;
    }
    for(i=pr.size()-1;i>=0;i--){
        pr[i]*=-1;
        add[i]=add[i+1]+ct[i];
        //if(i>pr.size()-10)
        //printf("%d.%d.\n",pr[i],add[i]);
    }
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d%d",&x,&y);

        x=lower_bound(pr.begin(),pr.end(),-x+1)-pr.begin();
        y=lower_bound(pr.begin(),pr.end(),-y)-pr.begin();
        //printf("%d.%d.\n",pr[x],pr[y]);
        printf("%d\n",add[y]-add[x]);
    }

}