Finding number with prime number of divisors?

Question

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?

Answer 1

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 :(

Answer 2

While prime factorization doesn't exactly happen instantly for large numbers, you can determine the number of divisors of a number using the exponents from the prime factorization.

For every distinct power in a number's prime factorization, there is an integral exponent. Add 1 to every one of these powers, multiply the resulting numbers, and you will obtain the number of divisors that divide even into the original number.

Some examples are called for to demonstrate the power of this fact (of which I can't recall a rigorous proof).

Example 1: 60. The prime factorization of 60 is $2^23^15^1$. Just looking at each of the exponents, we have 2,1,1. Add one to each of them to get 3,2,2 and multiply them to get 3*2*2 = 12. This means that 60 has 12 divisors (including 1 and 60 itself). Indeed, the positive divisors of 60 are, in ascending order, 1,2,3,4,5,6,10,12,15,20,30,60.

Example 2: 17. 17 is prime, so its prime factorization is (explicitly with exponents) 17^1. Take the exponent 1, add one to it to get 2, and now you have the number of positive divisors of 17: 1,17.

Example 3: $p$, where $p$ is any prime. Needless to say, the prime factorization is $p^1$, and the positive divisors of $p$ are 1,$p$. Since the number of divisors is always 2 (which is prime), we can conclude that all primes have a prime number of divisors.

Now we can consider composites. Every natural number $n\geq 1$ must have 1 and $n$ at least in its prime divisor list. For every other divisor $d$ of $n$, there is a corresponding divisor $d/n$ that keeps the number of divisors even. The only special case is when $d=\frac{n}{d} \implies d^2 = n$. But then $d$ is just the square root of $n$ (!) and will only occur once in the list of $n$'s divisors, thus producing an odd number of divisors. So the only composite numbers with an odd number of divisors are perfect squares. There is no need to check any non-square composite number because they will have an even number of at least 4 divisors.

Computational Pro-Tip: when searching for all numbers on the interval $[a,b]$, "simply" list the primes in the interval. Then assign $m = \lfloor \sqrt{a} \rfloor$, and $n = \lceil \sqrt{b} \rceil$. Find the prime factorization for every natural number on the interval $[m,n]$, double each of the exponents in said prime factorization, add one to every exponent, multiply all of them as before and determine if this product is prime. If so, just append the square of corresponding integer to the list that keeps track of the numbers with a prime number of positive divisors.