#include <bits/stdc++.h>   using namespace std;   const int N = 1e6 + 5;   const int M = 1e7 + 5;   int x[N];   int cnt[M];   bool vis[M + 5];   int f[M + 5];   int sum[M + 5];   void erato() {     for (int i = 2; i <= M; i++) vis[i] = true;     for (int i = 2; i <= M; i++) {       if (vis[i]) {         f[i] += cnt[i];         for (int j = 2; j <= M / i; j++) {           vis[j * i] = false;           f[i] += cnt[j * i];         }       }     }   }   int main() {     int n, m;     scanf( %d , &n);     for (int i = 1; i <= n; i++) {       scanf( %d , &x[i]);       cnt[x[i]]++;     }     erato();     sum[0] = 0;     for (int i = 1; i <= M - 5; i++) sum[i] += (sum[i - 1] + f[i]);     scanf( %d , &m);     while (m--) {       int l, r;       scanf( %d%d , &l, &r);       if (l >= M - 5) {         printf( 0 n );         continue;       }       if (r >= M - 5) r = M - 5;       printf( %d n , sum[r] - sum[l - 1]);     }     return 0;   }   