function countSemiPrimes(n: number, p: number[], q: number[]): number[] {
  const primes: boolean[] = new Array(n + 1).fill(true);
  const semiPrimes: number[] = new Array(n + 1).fill(0);
  const semiPrimeCounts: number[] = new Array(p.length).fill(0);

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

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

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

  for (let k = 0; k < p.length; k++) {
    semiPrimeCounts[k] = semiPrimes[q[k]] - semiPrimes[p[k] - 1];
  }

  return semiPrimeCounts;
}