/*    可以在筛选质数的同时，算出每组数据中能被各个质数整除的个数，    然后算出[0，s]的个数 [l,r] 的个数即为[0,r]的个数减去[0,l]个数。 */#include 
     
      #include 
      
       #include 
       
        #define maxn 10000010using namespace std;int prime[maxn];int isprime[maxn];int x[maxn];void make_prime(){    memset(isprime, 0, sizeof(isprime));    for(int i = 2;i < maxn;i++){        if(!isprime[i]){            //prime[i] += x[i];            for(int j = i;j < maxn;j += i){                isprime[j] = 1;                prime[i] += x[j];            }        }    }//    for(int i = 0;i < 100;i++)//        printf("%d ",prime[i]);    for(int i = 2;i < maxn;i++)        prime[i] += prime[i-1];    }int main(){    int n,m;    while(~scanf("%d",&n)){        int temp = 0;        memset(x, 0, sizeof(x));        memset(prime, 0, sizeof(prime));        for(int i = 0;i < n;i++){            scanf("%d",&temp);            x[temp]++;        }//        for(int i = 0;i < 25;i++)//            printf("%d ",x[i]);//        printf("\n");        make_prime();        int l,r;        scanf("%d",&m);        while(m--){            scanf("%d%d",&l,&r);//由于x1, x2, ..., xn (2 ≤ xi ≤ 10^7)            if(l > maxn)                l = maxn-1;//这里的边界一定要注意，WA了好几次才发现            if(r > maxn)                r = maxn-1;            printf("%d\n",prime[r]-prime[l-1]);        }    }    return 0;}