# Find numbers with n-divisors in a given range

Given three integers a, b, n .Your task is to print number of numbers between a and b including them also which have n-divisors. A number is called n-divisor if it has total n divisors including 1 and itself.
Examples:

```Input  : a = 1, b = 7, n = 2
Output : 4
There are four numbers with 2 divisors in
range [1, 7]. The numbers are 2, 3, 5, and 7.
```

Naive Approach:
The naive approach is to check all the numbers between a and b how many of them are n-divisor number for doing this find out the number of each divisors for each number . If it is equal to n then it is a n-divisor number

Efficient Approach:
Any number can be written in the form of its prime factorization let the number be x and p1, p2..pm are the prime numbers which divide x so x = p1e1 * p2e2….pmem where e1, e2…em are the exponents of prime numbers p1, p2….pm. So the number of divisors of x will be (e1+1)*(e2+1)…*(em+1).
Now the second observation is for prime numbers greater than sqrt(x) their exponent cannot exceed 1. Let’s prove this by contradiction suppose there is a prime number P greater than sqrt(x) and its exponent E in prime factorization of x is greater than one (E >= 2) so P^E sqrt(x) so P^E > (sqrt(x))E and E >= 2 so PE will always be greater than x
Third observation is that number of prime numbers greater than sqrt(x) in the prime factorization of x will always be less than equal to 1. This can also be proved similarly by contradiction as above.

Now to solve this problem
Step 1: Apply sieve of erastothenes and calculate prime numbers upto sqrt(b).

Step 2: Traverse through each number from a to b and calculate exponents of each prime number in that number by repeatedly dividing that number by prime number and use the formula numberofdivisors(x) = (e1+1)*(e2+1)….(em+1).

Step 3: If after dividing by all the prime numbers less than equal to square root of that number if number > 1 this means there is a prime number greater than its square root which divides and its exponent will always be one as proved above.

div class="responsive-tabs">

## C++

 `// C++ program to count numbers with n divisors ` `#include ` `using` `namespace` `std; ` ` `  `// applying sieve of erastothenes ` `void` `sieve(``bool` `primes[], ``int` `x) ` `{ ` `    ``primes = ``false``; ` ` `  `    ``// if a number is prime mark all its multiples ` `    ``// as non prime ` `    ``for` `(``int` `i=2; i*i <= x; i++) ` `    ``{ ` `        ``if` `(primes[i] == ``true``) ` `        ``{ ` `            ``for` `(``int` `j=2; j*i <= x; j++) ` `                ``primes[i*j] = ``false``; ` `        ``} ` `    ``} ` `} ` ` `  `// function that returns numbers of number that have ` `// n divisors in range from a to b. x is sqrt(b) + 1. ` `int` `nDivisors(``bool` `primes[], ``int` `x, ``int` `a, ``int` `b, ``int` `n) ` `{ ` `    ``// result holds number of numbers having n divisors ` `    ``int` `result = 0; ` ` `  `    ``// vector to hold all the prime numbers between 1 ` `    ``// ans sqrt(b) ` `    ``vector <``int``> v; ` `    ``for` `(``int` `i = 2; i <= x; i++) ` `        ``if` `(primes[i] == ``true``) ` `            ``v.push_back (i); ` ` `  `    ``// Traversing all numbers in given range ` `    ``for` `(``int` `i=a; i<=b; i++) ` `    ``{ ` `        ``// initialising temp as i ` `        ``int` `temp = i; ` ` `  `        ``// total holds the number of divisors of i ` `        ``int` `total = 1; ` `        ``int` `j = 0; ` ` `  `        ``// we need to use that prime numbers that ` `        ``// are less than equal to sqrt(temp) ` `        ``for` `(``int` `k = v[j]; k*k <= temp; k = v[++j]) ` `        ``{ ` `            ``// holds the exponent of k in prime ` `            ``// factorization of i ` `            ``int` `count = 0; ` ` `  `            ``// repeatedly divide temp by k till it is ` `            ``// divisble and accordingly increase count ` `            ``while` `(temp%k == 0) ` `            ``{ ` `                ``count++; ` `                ``temp = temp/k; ` `            ``} ` ` `  `            ``// using the formula  no.of divisors = ` `            ``// (e1+1)*(e2+1).... ` `            ``total = total*(count+1); ` `        ``} ` ` `  `        ``// if temp is not equal to 1 then there is ` `        ``// prime number in prime factorization of i ` `        ``// greater than sqrt(i) ` `        ``if` `(temp != 1) ` `            ``total = total*2; ` ` `  `        ``// if i is a ndvisor number increase result ` `        ``if` `(total == n) ` `            ``result++; ` `    ``} ` `    ``return` `result; ` `} ` ` `  `// Returns count of numbers in [a..b] having ` `// n divisors. ` `int` `countNDivisors(``int` `a, ``int` `b, ``int` `n) ` `{ ` `    ``int` `x = ``sqrt``(b) + 1; ` ` `  `    ``// primes[i] = true if i is a prime number ` `    ``bool` `primes[x]; ` ` `  `    ``// initialising each number as prime ` `    ``memset``(primes, ``true``, ``sizeof``(primes)); ` `    ``sieve(primes, x); ` ` `  `    ``return` `nDivisors(primes, x, a, b, n); ` `} ` ` `  `// driver code ` `int` `main() ` `{ ` `    ``int` `a = 1, b = 7, n = 2; ` `    ``cout << countNDivisors(a, b, n); ` `    ``return` `0; ` `} `

## Java

 `// Java program to count numbers with n divisors  ` `import` `java.util.*; ` ` `  `class` `GFG{ ` `// applying sieve of erastothenes  ` `static` `void` `sieve(``boolean``[] primes, ``int` `x)  ` `{  ` `    ``primes[``1``] = ``true``;  ` ` `  `    ``// if a number is prime mark all its multiples  ` `    ``// as non prime  ` `    ``for` `(``int` `i=``2``; i*i <= x; i++)  ` `    ``{  ` `        ``if` `(primes[i] == ``false``)  ` `        ``{  ` `            ``for` `(``int` `j=``2``; j*i <= x; j++)  ` `                ``primes[i*j] = ``true``;  ` `        ``}  ` `    ``}  ` `}  ` ` `  `// function that returns numbers of number that have  ` `// n divisors in range from a to b. x is sqrt(b) + 1.  ` `static` `int` `nDivisors(``boolean``[] primes, ``int` `x, ``int` `a, ``int` `b, ``int` `n)  ` `{  ` `    ``// result holds number of numbers having n divisors  ` `    ``int` `result = ``0``;  ` ` `  `    ``// vector to hold all the prime numbers between 1  ` `    ``// ans sqrt(b)  ` `    ``ArrayList v=``new` `ArrayList();  ` `    ``for` `(``int` `i = ``2``; i <= x; i++)  ` `        ``if` `(primes[i] == ``false``)  ` `            ``v.add(i);  ` `     `  `    ``// Traversing all numbers in given range  ` `    ``for` `(``int` `i=a; i<=b; i++)  ` `    ``{  ` `        ``// initialising temp as i  ` `        ``int` `temp = i;  ` ` `  `        ``// total holds the number of divisors of i  ` `        ``int` `total = ``1``;  ` `        ``int` `j = ``0``;  ` ` `  `        ``// we need to use that prime numbers that  ` `        ``// are less than equal to sqrt(temp) ` `        ``for` `(``int` `k = v.get(j); k*k <= temp; k = v.get(++j)) ` `        ``{  ` `            ``// holds the exponent of k in prime  ` `            ``// factorization of i  ` `            ``int` `count = ``0``;  ` ` `  `            ``// repeatedly divide temp by k till it is  ` `            ``// divisble and accordingly increase count  ` `            ``while` `(temp%k == ``0``)  ` `            ``{  ` `                ``count++;  ` `                ``temp = temp/k;  ` `            ``}  ` ` `  `            ``// using the formula no.of divisors =  ` `            ``// (e1+1)*(e2+1)....  ` `            ``total = total*(count+``1``); ` `             `  `        ``}  ` ` `  `        ``// if temp is not equal to 1 then there is  ` `        ``// prime number in prime factorization of i  ` `        ``// greater than sqrt(i)  ` `        ``if` `(temp != ``1``)  ` `            ``total = total*``2``;  ` ` `  `        ``// if i is a ndvisor number increase result  ` `        ``if` `(total == n)  ` `            ``result++;  ` `    ``}  ` `    ``return` `result;  ` `}  ` ` `  `// Returns count of numbers in [a..b] having  ` `// n divisors.  ` `static` `int` `countNDivisors(``int` `a, ``int` `b, ``int` `n)  ` `{  ` `    ``int` `x = (``int``)Math.sqrt(b) + ``1``;  ` ` `  `    ``// primes[i] = true if i is a prime number  ` `    ``boolean``[] primes=``new` `boolean``[x+``1``];  ` ` `  `    ``// initialising each number as prime  ` `    ``sieve(primes, x);  ` ` `  `    ``return` `nDivisors(primes, x, a, b, n);  ` `}  ` ` `  `// driver code  ` `public` `static` `void` `main(String[] args)  ` `{  ` `    ``int` `a = ``1``, b = ``7``, n = ``2``;  ` `    ``System.out.println(countNDivisors(a, b, n));  ` `  `  `}  ` `} ` `// This code is contributed by mits `

## Python3

# Python3 program to count numbers
# with n divisors
import math;

# applying sieve of erastothenes
def sieve(primes, x):
primes = False;

# if a number is prime mark all
# its multiples as non prime
i = 2;
while (i * i <= x): if (primes[i] == True): j = 2; while (j * i <= x): primes[i * j] = False; j += 1; i += 1; # function that returns numbers of number # that have n divisors in range from a to b. # x is sqrt(b) + 1. def nDivisors(primes, x, a, b, n): # result holds number of numbers # having n divisors result = 0; # vector to hold all the prime # numbers between 1 and sqrt(b) v = []; for i in range(2, x + 1): if (primes[i]): v.append(i); # Traversing all numbers in given range for i in range(a, b + 1): # initialising temp as i temp = i; # total holds the number of # divisors of i total = 1; j = 0; # we need to use that prime numbers that # are less than equal to sqrt(temp) k = v[j]; while (k * k <= temp): # holds the exponent of k in prime # factorization of i count = 0; # repeatedly divide temp by k till it is # divisble and accordingly increase count while (temp % k == 0): count += 1; temp = int(temp / k); # using the formula no.of divisors = # (e1+1)*(e2+1).... total = total * (count + 1); j += 1; k = v[j]; # if temp is not equal to 1 then there is # prime number in prime factorization of i # greater than sqrt(i) if (temp != 1): total = total * 2; # if i is a ndvisor number # increase result if (total == n): result += 1; return result; # Returns count of numbers in [a..b] # having n divisors. def countNDivisors(a, b, n): x = int(math.sqrt(b) + 1); # primes[i] = true if i is a prime number # initialising each number as prime primes = [True] * (x + 1); sieve(primes, x); return nDivisors(primes, x, a, b, n); # Driver code a = 1; b = 7; n = 2; print(countNDivisors(a, b, n)); # This code is contributed by mits [tabby title="C#"]

 `// C# program to count numbers with n divisors  ` `using` `System.Collections; ` `using` `System; ` `class` `GFG{ ` `// applying sieve of erastothenes  ` `static` `void` `sieve(``bool``[] primes, ``int` `x)  ` `{  ` `    ``primes = ``true``;  ` ` `  `    ``// if a number is prime mark all its multiples  ` `    ``// as non prime  ` `    ``for` `(``int` `i=2; i*i <= x; i++)  ` `    ``{  ` `        ``if` `(primes[i] == ``false``)  ` `        ``{  ` `            ``for` `(``int` `j=2; j*i <= x; j++)  ` `                ``primes[i*j] = ``true``;  ` `        ``}  ` `    ``}  ` `}  ` ` `  `// function that returns numbers of number that have  ` `// n divisors in range from a to b. x is sqrt(b) + 1.  ` `static` `int` `nDivisors(``bool``[] primes, ``int` `x, ``int` `a, ``int` `b, ``int` `n)  ` `{  ` `    ``// result holds number of numbers having n divisors  ` `    ``int` `result = 0;  ` ` `  `    ``// vector to hold all the prime numbers between 1  ` `    ``// ans sqrt(b)  ` `    ``ArrayList v=``new` `ArrayList();  ` `    ``for` `(``int` `i = 2; i <= x; i++)  ` `        ``if` `(primes[i] == ``false``)  ` `            ``v.Add(i);  ` `     `  `    ``// Traversing all numbers in given range  ` `    ``for` `(``int` `i=a; i<=b; i++)  ` `    ``{  ` `        ``// initialising temp as i  ` `        ``int` `temp = i;  ` ` `  `        ``// total holds the number of divisors of i  ` `        ``int` `total = 1;  ` `        ``int` `j = 0;  ` ` `  `        ``// we need to use that prime numbers that  ` `        ``// are less than equal to sqrt(temp) ` `        ``for` `(``int` `k = (``int``)v[j]; k*k <= temp; k = (``int``)v[++j]) ` `        ``{  ` `            ``// holds the exponent of k in prime  ` `            ``// factorization of i  ` `            ``int` `count = 0;  ` ` `  `            ``// repeatedly divide temp by k till it is  ` `            ``// divisble and accordingly increase count  ` `            ``while` `(temp%k == 0)  ` `            ``{  ` `                ``count++;  ` `                ``temp = temp/k;  ` `            ``}  ` ` `  `            ``// using the formula no.of divisors =  ` `            ``// (e1+1)*(e2+1)....  ` `            ``total = total*(count+1); ` `             `  `        ``}  ` ` `  `        ``// if temp is not equal to 1 then there is  ` `        ``// prime number in prime factorization of i  ` `        ``// greater than sqrt(i)  ` `        ``if` `(temp != 1)  ` `            ``total = total*2;  ` ` `  `        ``// if i is a ndvisor number increase result  ` `        ``if` `(total == n)  ` `            ``result++;  ` `    ``}  ` `    ``return` `result;  ` `}  ` ` `  `// Returns count of numbers in [a..b] having  ` `// n divisors.  ` `static` `int` `countNDivisors(``int` `a, ``int` `b, ``int` `n)  ` `{  ` `    ``int` `x = (``int``)Math.Sqrt(b) + 1;  ` ` `  `    ``// primes[i] = true if i is a prime number  ` `    ``bool``[] primes=``new` `bool``[x+1];  ` ` `  `    ``// initialising each number as prime  ` `    ``sieve(primes, x);  ` ` `  `    ``return` `nDivisors(primes, x, a, b, n);  ` `}  ` ` `  `// driver code  ` `public` `static` `void` `Main()  ` `{  ` `    ``int` `a = 1, b = 7, n = 2;  ` `    ``Console.WriteLine(countNDivisors(a, b, n));  ` `  `  `}  ` `} ` `// This code is contributed by mits `

## PHP

 ` `

Output:

```4
```