Pre-generate the almost prime values. We need almost-prime upto 10^12. So, we take all primes less than 10^6. Why is that? Cause if we take a prime larger than 10^6 and square it, it will cross 10^12.
In order to generate all primes less than 10^6, we can run the sieve algorithm.
Once the primes are generated, we can easily generate almost prime. First take the first prime, 2. 2 is not almost prime, but 2^2 is. So run a loop, and get all values of 2^x, where 2^x is less then 10^12. Do the same for 3, 5, 7 and all primes less than 10^12.
Now sort all your almost primes.
In the problem, when you will be given low and high, simply binary search over the almost-prime array you generated and find the positions of high and low. The difference is answer ( this will depend on your implementation of binary search).