static int[] CountSemiPrimes(int n, int[] p, int[] q)
{
    var primes = new bool[n + 1];
    Array.Fill(primes, true);
    var semiPrimes = new int[n + 1];

    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];
    }

    var semiPrimeCounts = new int[p.Length];
    for (int k = 0; k < p.Length; k++)
    {
        semiPrimeCounts[k] = semiPrimes[q[k]] - semiPrimes[p[k] - 1];
    }

    return semiPrimeCounts;
}