Highly Composite Numbers
A number N is highly composite if it has more divisors than any smaller numbers than N.
Few Highly composite numbers are:
1, 2, 4, 6, 12, 24, 36, 48, 60, 120….
Check if N is a Highly Composite number.
Given a number N, the task is to check if N is a Highly Composite Number or not. If N is a Highly Composite Number, then print “Yes”. Else print “No”.
Examples:
Input: N = 60
Output: Yes
60 is a highly composite because it has 12 divisors
and none of the numbers up to 59 has 12 or more divisors.Input: N = 18
Output: No
Approach:
- Find the count of divisors of N
- Now, in a loop from 1 to less than N, check for every i that if several divisors of i are more than the count of divisors of N, then return false.
- Otherwise, return true at the end.
Below is the implementation of the above approach:
C++
// C++ implementation for checking // Highly Composite Number #include <bits/stdc++.h> using namespace std; // Function to count the number // of divisors of the N int divCount( int n) { // sieve method for prime calculation bool hash[n + 1]; memset (hash, true , sizeof (hash)); for ( int p = 2; p * p < n; p++) if (hash[p] == true ) for ( int i = p * 2; i < n; i += p) hash[i] = false ; // Traversing through // all prime numbers int total = 1; for ( int p = 2; p <= n; p++) { if (hash[p]) { // calculate number of divisor // with formula total div = // (p1+1) * (p2+1) *.....* (pn+1) // where n = (a1^p1)*(a2^p2).... // *(an^pn) ai being prime divisor // for n and pi are their respective // power in factorization int count = 0; if (n % p == 0) { while (n % p == 0) { n = n / p; count++; } total = total * (count + 1); } } } return total; } // Function to check if a number // is a highly composite number bool isHighlyCompositeNumber( int N) { // count number of factors of N int NdivCount = divCount(N); // loop to count number of factors of // every number less than N for ( int i = 1; i < N; i++) { int idivCount = divCount(i); // If any number less than N has // more factors than N, // then return false if (idivCount >= NdivCount) return false ; } return true ; } // Driver code int main() { // Given Number N int N = 12; // Function Call if (isHighlyCompositeNumber(N)) cout << "Yes" ; else cout << "No" ; return 0; } |
Java
// Java implementation for checking // Highly Composite Number import java.util.*; class GFG{ // Function to count the number // of divisors of the N static int divCount( int n) { // sieve method for prime calculation boolean []hash = new boolean [n + 1 ]; Arrays.fill(hash, true ); for ( int p = 2 ; p * p < n; p++) if (hash[p] == true ) for ( int i = p * 2 ; i < n; i += p) hash[i] = false ; // Traversing through // all prime numbers int total = 1 ; for ( int p = 2 ; p <= n; p++) { if (hash[p]) { // calculate number of divisor // with formula total div = // (p1+1) * (p2+1) *.....* (pn+1) // where n = (a1^p1)*(a2^p2).... // *(an^pn) ai being prime divisor // for n and pi are their respective // power in factorization int count = 0 ; if (n % p == 0 ) { while (n % p == 0 ) { n = n / p; count++; } total = total * (count + 1 ); } } } return total; } // Function to check if a number // is a highly composite number static boolean isHighlyCompositeNumber( int N) { // count number of factors of N int NdivCount = divCount(N); // loop to count number of factors of // every number less than N for ( int i = 1 ; i < N; i++) { int idivCount = divCount(i); // If any number less than N has // more factors than N, // then return false if (idivCount >= NdivCount) return false ; } return true ; } // Driver code public static void main(String[] args) { // Given Number N int N = 12 ; // Function Call if (isHighlyCompositeNumber(N)) System.out.print( "Yes" ); else System.out.print( "No" ); } } // This code is contributed by gauravrajput1 |
Python3
# Python3 implementation for checking # Highly Composite Number # Function to count the number # of divisors of the N def divCount(n): # Sieve method for prime calculation Hash = [ True for i in range (n + 1 )] p = 2 while ((p * p) < n): if bool ( Hash [p]): i = p * 2 while i < n: Hash [i] = False i + = p p + = 1 # Traversing through # all prime numbers total = 1 for P in range ( 2 , n + 1 ): if ( bool ( Hash [P])): # Calculate number of divisor # with formula total div = # (p1+1) * (p2+1) *.....* (pn+1) # where n = (a1^p1)*(a2^p2).... # *(an^pn) ai being prime divisor # for n and pi are their respective # power in factorization count = 0 if (n % P = = 0 ): while (n % P = = 0 ): n = n / / P count + = 1 total = total * (count + 1 ) return total # Function to check if a number # is a highly composite number def isHighlyCompositeNumber(N): # Count number of factors of N NdivCount = divCount(N) # Loop to count number of factors of # every number less than N for i in range (N): idivCount = divCount(i) # If any number less than N has # more factors than N, # then return false if (idivCount > = NdivCount): return bool ( False ) return bool ( True ) # Driver code # Given Number N N = 12 # Function Call if ( bool (isHighlyCompositeNumber(N))): print ( "Yes" ) else : print ( "No" ) # This code is contributed by divyeshrabadiya07 |
C#
// C# implementation for checking // Highly Composite Number using System; class GFG{ // Function to count the number // of divisors of the N static int divCount( int n) { // sieve method for prime calculation bool []hash = new bool [n + 1]; for ( int i = 0; i < n + 1; i++) hash[i] = true ; for ( int p = 2; p * p < n; p++) if (hash[p] == true ) for ( int i = p * 2; i < n; i += p) hash[i] = false ; // Traversing through // all prime numbers int total = 1; for ( int p = 2; p <= n; p++) { if (hash[p]) { // calculate number of divisor // with formula total div = // (p1+1) * (p2+1) *.....* (pn+1) // where n = (a1^p1)*(a2^p2).... // *(an^pn) ai being prime divisor // for n and pi are their respective // power in factorization int count = 0; if (n % p == 0) { while (n % p == 0) { n = n / p; count++; } total = total * (count + 1); } } } return total; } // Function to check if a number // is a highly composite number static bool isHighlyCompositeNumber( int N) { // count number of factors of N int NdivCount = divCount(N); // loop to count number of factors of // every number less than N for ( int i = 1; i < N; i++) { int idivCount = divCount(i); // If any number less than N has // more factors than N, // then return false if (idivCount >= NdivCount) return false ; } return true ; } // Driver code public static void Main(String[] args) { // Given Number N int N = 12; // Function Call if (isHighlyCompositeNumber(N)) Console.Write( "Yes" ); else Console.Write( "No" ); } } // This code is contributed by shikhasingrajput |
Javascript
<script> // Javascript implementation for checking // Highly Composite Number // Function to count the number // of divisors of the N function divCount( n) { // sieve method for prime calculation let hash = Array(n+1).fill( true ); for ( let p = 2; p * p < n; p++) if (hash[p] == true ) for ( i = p * 2; i < n; i += p) hash[i] = false ; // Traversing through // all prime numbers let total = 1; for ( p = 2; p <= n; p++) { if (hash[p]) { // calculate number of divisor // with formula total div = // (p1+1) * (p2+1) *.....* (pn+1) // where n = (a1^p1)*(a2^p2).... // *(an^pn) ai being prime divisor // for n and pi are their respective // power in factorization let count = 0; if (n % p == 0) { while (n % p == 0) { n = n / p; count++; } total = total * (count + 1); } } } return total; } // Function to check if a number // is a highly composite number function isHighlyCompositeNumber( N) { // count number of factors of N let NdivCount = divCount(N); // loop to count number of factors of // every number less than N for ( let i = 1; i < N; i++) { let idivCount = divCount(i); // If any number less than N has // more factors than N, // then return false if (idivCount >= NdivCount) return false ; } return true ; } // Driver code // Given Number N let N = 12; // Function Call if (isHighlyCompositeNumber(N)) document.write( "Yes" ); else document.write( "No" ); // This code contributed by Rajput-Ji </script> |
Output:
Yes
Time Complexity: O(n*n*log(log(n))
Auxiliary Space: O(n)
Reference: http://www.numbersaplenty.com/set/highly_composite_number/