def count_semi_primes(n: int, p: list[int], q: list[int]) -> list[int]:
    primes = [True] * (n + 1)
    semi_primes = [0] * (n + 1)

    i = 2
    while i * i <= n:
        if primes[i]:
            for k in range(i * i, n + 1, i):
                primes[k] = False
        i += 1

    k = 2
    while k * k <= n:
        if primes[k]:
            i = 2
            while i * k <= n:
                if primes[i]:
                    semi_primes[k * i] = 1
                i += 1
        k += 1

    for i in range(1, n + 1):
        semi_primes[i] += semi_primes[i - 1]

    return [semi_primes[q[idx]] - semi_primes[p[idx] - 1] for idx in range(len(p))]