Untitled

#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL)
#define ll long long

const int N = 1e7;
vector<bool> isprime(N + 1, true);
vector<int> freq(N + 5); // To count the frequeny of a certain number
vector<int> primes; // store the primes in a certain array
vector<ll> val; // val[i] = how many numbers in the array are divisible by primes[i]

void sieve() {
    isprime[0] = isprime[1] = false;
    for (int i = 2; i <= N; ++i) {
        if (isprime[i]) {
            primes.emplace_back(i);
            val.emplace_back(0);
            for (int j = i; j <= N; j += i) {
                if (j != i) isprime[j] = false; /// j cannot be prime
                /// the number of numbers that are divisible by i, will increse by freq[j]
                /// as j is divisible by i
                val.back() += freq[j];
            }
        }
    }
}

void solve() {
    int n; cin >> n;
    while(n--) {
        int x; cin >> x;
        freq[x]++;
    }
    sieve();
    int m; cin >> m;
    /// Prefix sum on val array
    for (int i = 1; i < (int)val.size(); ++i)
        val[i] += val[i - 1];
    while(m--) {
        int a, b; cin >> a >> b;
        int lower_idx = lower_bound(primes.begin(), primes.end(), a) - primes.begin();
        int upper_idx = upper_bound(primes.begin(), primes.end(), b) - primes.begin() - 1;
        if (lower_idx > upper_idx)
            cout << 0 << '\n';
        else
            cout << val[upper_idx] - (lower_idx ? val[lower_idx - 1] : 0) << '\n';
    }
}

int main(){
    fast;
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("Error.txt", "w", stderr);
#endif
    int t = 1; //cin >> t;
    for (int i = 1 ; i <= t; ++i)
    {
        solve();
        if (i != t)
            cout << '\n';
    }
    return 0;
}