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?

  • $\begingroup$ Put $s around mathematics. $\endgroup$
    – Shaun
    Commented Nov 1, 2013 at 19:59
  • $\begingroup$ Prime numbers, except for 2, are odd. The only numbers with an odd number of divisors are perfect squares. That narrows down the search considerably. $\endgroup$
    – MJD
    Commented Nov 1, 2013 at 20:03
  • 6
    $\begingroup$ The numbers are the primes, and the numbers of the form $p^{2k}$, where $2k+1$ is prime, and $p$ is prime. I have no suggestion for fast listing. $\endgroup$ Commented Nov 1, 2013 at 20:04
  • $\begingroup$ You need to look up primality tests The usual recommendation is to do trial division by small primes followed by Fermat's little theorem tests. The failures of Fermat's little theorem up to $10^{12}$ are known, so you can just code them and ignore the other tests. $\endgroup$ Commented Nov 1, 2013 at 20:33
  • $\begingroup$ See OEIS A009087 $\endgroup$
    – Henry
    Commented Feb 26 at 1:31

3 Answers 3


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.


For prime factorization $n = p_1^{e_1} \cdots p_r^{e_r} $, the number of divisors is $\sigma(n) = (e_1 + 1) (e_2 + 1)\cdots (e_r + 1)$. For that to be prime, $n$ must be a prime power $p^e$ where $e + 1$ is prime, so $e = 1, 2, 4, 6, 10, \dots$ (primes minus one is A006093).

For prime $n$ (i.e. $e = 1$), you can use probabilistic primality tests for all $10^6$ numbers in range (or use Meissel-Lehmer algorithm for prime-counting function). For the other powers, observe there are only $(10^{12})^{1/2} = 10^6$ squares less than or equal to $10^{12}$, $(10^{12})^{1/4}$ fourth powers $\le 10^{12}$, etc. and you only need to check powers up to $2^{40} > 10^{12}$.


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

  • $\begingroup$ i suppose you mean $p^{2k}$ $\endgroup$ Commented Nov 2, 2013 at 8:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .