Finding number with prime number of divisors? The problem is to find the number of numbers in [l,r] that have prime number of divisors.
Example for $l=1,r=10$
The answer is $6$
since $2,3,4,5,7,9$ are the numbers having prime number of divisors
constraints are $l,r\le10^{12}$
and $r-l\le10^6$.
Can someone help me with the fastest solution?
Here is my approach
I stored primes  3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 in an array.
Loop through i=1 to 1000000
   if i is prime
       for j in primes
           calculate val=i^(j-1)
              add the val to answer list
for each query [l,r], the answer is all primes in [l,r]+ 
                     the numbers in the list in range [l,r]

but finding all primes in [l,r] takes too much time.
Any sugesstion?

Your answer is simply the count of prime numbers plus some extra numbers $p^{2^k},k\geq 1,$ where $p$ is prime, or more generally, all the numbers of the form $p^{2^k},k\geq 0$ and $p$ prime.
See this for more details.
By the way, I am also trying this problem of codechef...but not AC yet :(
