function countSemiPrimes(int $n, array $p, array $q): array
{
    $primes          = array_fill(0, $n + 1, true);
    $semiPrimes      = array_fill(0, $n + 1, 0);
    $semiPrimeCounts = array_fill(0, count($p), 0);

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

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

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

    foreach ($p as $k => $v) {
        $semiPrimeCounts[$k] = $semiPrimes[$q[$k]] - $semiPrimes[$v - 1];

    }

    return $semiPrimeCounts;


}