#include <cstddef>
#include <vector>

std::vector<int> countSemiPrimes(int n, const std::vector<int>& p, const std::vector<int>& q)
{
    std::vector<bool> primes(n + 1, true);
    std::vector<int> semiPrimes(n + 1, 0);
    std::vector<int> semiPrimeCounts(p.size(), 0);

    for (int i = 2; i * i <= n; ++i) {
        if (primes[i]) {
            for (int k = i * i; k <= n; k += i) {
                primes[k] = false;
            }
        }
    }

    for (int k = 2; k * k <= n; ++k) {
        if (primes[k]) {
            for (int i = 2; i * k <= n; ++i) {
                if (primes[i]) {
                    semiPrimes[k * i] = 1;
                }
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        semiPrimes[i] += semiPrimes[i - 1];
    }

    for (std::size_t k = 0; k < p.size(); ++k) {
        semiPrimeCounts[k] = semiPrimes[q[k]] - semiPrimes[p[k] - 1];
    }

    return semiPrimeCounts;
}