Count the numbers < N which have equal number of divisors as K
Given two integers N and K, the task is to count all the numbers < N which have equal number of positive divisors as K.
Examples:
Input: n = 10, k = 5
Output: 3
2, 3 and 7 are the only numbers < 10 which have 2 divisors (equal to the number of divisors of 5)Input: n = 500, k = 6
Output: 148
Approach:
- Compute the number of divisor of each number < N and store the result in an array where arr[i] contains the number of divisors of i.
- Traverse arr[], if arr[i] = arr[K] then update count = count + 1.
- Print the value of count in the end.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the count of the // divisors of a number int countDivisors( int n) { // Count the number of // 2s that divide n int x = 0, ans = 1; while (n % 2 == 0) { x++; n = n / 2; } ans = ans * (x + 1); // n must be odd at this point. // So we can skip one element for ( int i = 3; i <= sqrt (n); i = i + 2) { // While i divides n x = 0; while (n % i == 0) { x++; n = n / i; } ans = ans * (x + 1); } // This condition is to // handle the case when // n is a prime number > 2 if (n > 2) ans = ans * 2; return ans; } int getTotalCount( int n, int k) { int k_count = countDivisors(k); // Count the total elements // that have divisors exactly equal // to as that of k's int count = 0; for ( int i = 1; i < n; i++) if (k_count == countDivisors(i)) count++; // Exclude k from the result if it // is smaller than n. if (k < n) count = count - 1; return count; } // Driver code int main() { int n = 500, k = 6; cout << getTotalCount(n, k); return 0; } |
Java
// Java implementation of the approach public class GFG{ // Function to return the count of the // divisors of a number static int countDivisors( int n) { // Count the number of // 2s that divide n int x = 0 , ans = 1 ; while (n % 2 == 0 ) { x++; n = n / 2 ; } ans = ans * (x + 1 ); // n must be odd at this point. // So we can skip one element for ( int i = 3 ; i <= Math.sqrt(n); i = i + 2 ) { // While i divides n x = 0 ; while (n % i == 0 ) { x++; n = n / i; } ans = ans * (x + 1 ); } // This condition is to // handle the case when // n is a prime number > 2 if (n > 2 ) ans = ans * 2 ; return ans; } static int getTotalCount( int n, int k) { int k_count = countDivisors(k); // Count the total elements // that have divisors exactly equal // to as that of k's int count = 0 ; for ( int i = 1 ; i < n; i++) if (k_count == countDivisors(i)) count++; // Exclude k from the result if it // is smaller than n. if (k < n) count = count - 1 ; return count; } // Driver code public static void main(String []args) { int n = 500 , k = 6 ; System.out.println(getTotalCount(n, k)); } // This code is contributed by Ryuga } |
Python3
# Python3 implementation of the approach # Function to return the count of # the divisors of a number def countDivisors(n): # Count the number of 2s that divide n x, ans = 0 , 1 while (n % 2 = = 0 ): x + = 1 n = n / 2 ans = ans * (x + 1 ) # n must be odd at this point. # So we can skip one element for i in range ( 3 , int (n * * 1 / 2 ) + 1 , 2 ): # While i divides n x = 0 while (n % i = = 0 ): x + = 1 n = n / i ans = ans * (x + 1 ) # This condition is to handle the # case when n is a prime number > 2 if (n > 2 ): ans = ans * 2 return ans def getTotalCount(n, k): k_count = countDivisors(k) # Count the total elements that # have divisors exactly equal # to as that of k's count = 0 for i in range ( 1 , n): if (k_count = = countDivisors(i)): count + = 1 # Exclude k from the result if it # is smaller than n. if (k < n): count = count - 1 return count # Driver code if __name__ = = '__main__' : n, k = 500 , 6 print (getTotalCount(n, k)) # This code is contributed # by 29AjayKumar |
C#
// C# implementation of the approach using System; public class GFG{ // Function to return the count of the // divisors of a number static int countDivisors( int n) { // Count the number of // 2s that divide n int x = 0, ans = 1; while (n % 2 == 0) { x++; n = n / 2; } ans = ans * (x + 1); // n must be odd at this point. // So we can skip one element for ( int i = 3; i <= Math.Sqrt(n); i = i + 2) { // While i divides n x = 0; while (n % i == 0) { x++; n = n / i; } ans = ans * (x + 1); } // This condition is to // handle the case when // n is a prime number > 2 if (n > 2) ans = ans * 2; return ans; } static int getTotalCount( int n, int k) { int k_count = countDivisors(k); // Count the total elements // that have divisors exactly equal // to as that of k's int count = 0; for ( int i = 1; i < n; i++) if (k_count == countDivisors(i)) count++; // Exclude k from the result if it // is smaller than n. if (k < n) count = count - 1; return count; } // Driver code public static void Main() { int n = 500, k = 6; Console.WriteLine(getTotalCount(n, k)); } } // This code is contributed by 29AjayKumar |
PHP
<?php //PHP implementation of the approach // Function to return the count of the // divisors of a number function countDivisors( $n ) { // Count the number of // 2s that divide n $x = 0; $ans = 1; while ( $n % 2 == 0) { $x ++; $n = $n / 2; } $ans = $ans * ( $x + 1); // n must be odd at this point. // So we can skip one element for ( $i = 3; $i <= sqrt( $n ); $i = $i + 2) { // While i divides n $x = 0; while ( $n % $i == 0) { $x ++; $n = $n / $i ; } $ans = $ans * ( $x + 1); } // This condition is to // handle the case when // n is a prime number > 2 if ( $n > 2) $ans = $ans * 2; return $ans ; } function getTotalCount( $n , $k ) { $k_count = countDivisors( $k ); // Count the total elements // that have divisors exactly equal // to as that of k's $count = 0; for ( $i = 1; $i < $n ; $i ++) if ( $k_count == countDivisors( $i )) $count ++; // Exclude k from the result if it // is smaller than n. if ( $k < $n ) $count = $count - 1; return $count ; } // Driver code $n = 500; $k = 6; echo getTotalCount( $n , $k ); #This code is contributed by Sachin.. ?> |
Javascript
<script> //Javascript implementation of the approach // Function to return the count of the // divisors of a number function countDivisors(n) { // Count the number of // 2s that divide n var x = 0, ans = 1; while (n % 2 == 0) { x++; n = n / 2; } ans = ans * (x + 1); // n must be odd at this point. // So we can skip one element for ( var i = 3; i <= Math.sqrt(n); i = i + 2) { // While i divides n x = 0; while (n % i == 0) { x++; n = n / i; } ans = ans * (x + 1); } // This condition is to // handle the case when // n is a prime number > 2 if (n > 2) ans = ans * 2; return ans; } function getTotalCount( n, k) { var k_count = countDivisors(k); // Count the total elements // that have divisors exactly equal // to as that of k's var count = 0; for ( var i = 1; i < n; i++) if (k_count == countDivisors(i)) count++; // Exclude k from the result if it // is smaller than n. if (k < n) count = count - 1; return count; } var n = 500, k = 6; document.write(getTotalCount(n, k)); // This code is contributed by SoumikMondal </script> |
Output
148
Complexity Analysis:
- Time Complexity: O(n * sqrt(k)), where n is the maximum number to check for divisors and sqrt(k) is the maximum number of iterations for the loop that checks divisors of n.
- Auxiliary Space: O(1)
Optimization:
The above solution can be optimized using Sieve technique. Please refer Count number of integers less than or equal to N which has exactly 9 divisors for details.