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 eratosthenes 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.
C++
// C++ program to count numbers with n divisors #include<bits/stdc++.h> using namespace std; // applying sieve of eratosthenes void sieve( bool primes[], int x) { primes[1] = 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*j <= 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 // divisible 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 eratosthenes 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<Integer> v= new ArrayList<Integer>(); 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 // divisible 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 eratosthenes def sieve(primes, x): primes[ 1 ] = 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 # divisible 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 ndivisor 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 |
C#
// C# program to count numbers with n divisors using System.Collections; using System; class GFG{ // applying sieve of eratosthenes static void sieve( bool [] 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( 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 // divisible 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 ndivisor 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
<?php // PHP program to count numbers with n divisors // applying sieve of eratosthenes function sieve(& $primes , $x ) { $primes [1] = false; // if a number is prime mark all // its multiples as non prime for ( $i = 2; $i * $i <= $x ; $i ++) { if ( $primes [ $i ] == true) { for ( $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. function 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 ans sqrt(b) $v = array (); for ( $i = 2; $i <= $x ; $i ++) if ( $primes [ $i ] == true) array_push ( $v , $i ); // Traversing all numbers in given range for ( $i = $a ; $i <= $b ; $i ++) { // 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) for ( $k = $v [ $j ]; $k * $k <= $temp ; $k = $v [++ $j ]) { // holds the exponent of k in // prime factorization of i $count = 0; // repeatedly divide temp by k till // it is divisible and accordingly // increase count while ( $temp % $k == 0) { $count ++; $temp = (int)( $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 n divisor number increase result if ( $total == $n ) $result ++; } return $result ; } // Returns count of numbers in [a..b] // having n divisors. function countNDivisors( $a , $b , $n ) { $x = (int)(sqrt( $b ) + 1); // primes[i] = true if i is a prime number // initialising each number as prime $primes = array_fill (0, $x + 1, true); 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 ?> |
Javascript
<script> // Javascript program to count numbers with n divisors // applying sieve of eratosthenes function sieve(primes, x) { primes[1] = true ; // if a number is prime mark all its multiples // as non prime for ( var i=2; i*i <= x; i++) { if (primes[i] == false ) { for ( var 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. function nDivisors(primes, x, a, b, n) { // result holds number of numbers having n divisors var result = 0; // vector to hold all the prime numbers between 1 // ans sqrt(b) var v = []; for ( var i = 2; i <= x; i++) if (primes[i] == false ) v.push(i); // Traversing all numbers in given range for ( var i=a; i<=b; i++) { // initialising temp as i var temp = i; // total holds the number of divisors of i var total = 1; var j = 0; // we need to use that prime numbers that // are less than equal to sqrt(temp) for ( var k = v[j]; k*k <= temp; k = v[++j]) { // holds the exponent of k in prime // factorization of i var count = 0; // repeatedly divide temp by k till it is // divisible and accordingly increase count while (temp%k == 0) { count++; temp = parseInt(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 ndivisor number increase result if (total == n) result++; } return result; } // Returns count of numbers in [a..b] having // n divisors. function countNDivisors(a, b, n) { var x = parseInt(Math.sqrt(b)) + 1; // primes[i] = true if i is a prime number var primes = Array(x+1).fill( false ); // initialising each number as prime sieve(primes, x); return nDivisors(primes, x, a, b, n); } // driver code var a = 1, b = 7, n = 2; document.write(countNDivisors(a, b, n)); // This code is contributed by rutvik_56. </script> |
Output:
4
Time Complexity: O(n)
Auxiliary Space: O(n)
Contact Us