fn count_semi_primes(n: usize, p: &[usize], q: &[usize]) -> Vec<i64> {
    let mut is_prime = vec![true; n + 1];
    let mut semi_primes = vec![0i64; n + 1];

    let mut i = 2;
    while i * i <= n {
        if is_prime[i] {
            let mut k = i * i;
            while k <= n {
                is_prime[k] = false;
                k += i;
            }
        }
        i += 1;
    }

    let mut k = 2;
    while k * k <= n {
        if is_prime[k] {
            let mut i = 2;
            while i * k <= n {
                if is_prime[i] {
                    semi_primes[k * i] = 1;
                }
                i += 1;
            }
        }
        k += 1;
    }

    for i in 1..=n {
        semi_primes[i] += semi_primes[i - 1];
    }

    p.iter()
        .zip(q.iter())
        .map(|(&pi, &qi)| semi_primes[qi] - semi_primes[pi - 1])
        .collect()
}