func countSemiPrimes(n int, p, q []int) []int {
	primes := make([]bool, n+1)
	for i := range primes {
		primes[i] = true
	}
	semiPrimes := make([]int, n+1)
	result := make([]int, len(p))

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

	for k := range p {
		result[k] = semiPrimes[q[k]] - semiPrimes[p[k]-1]
	}

	return result
}