Highly Composite Numbers | C ++ implementation for checking Highly Composite Number ; Function to count the number of divisors of the N ; sieve method for prime calculation ; Traversing through all prime numbers ; 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 ; Function to check if a number is a highly composite number ; count number of factors of N ; loop to count number of factors of every number less than N ; If any number less than N has more factors than N , then return false ; Driver code ; Given Number N ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int divCount ( int n ) { 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 ; int total = 1 ; for ( int p = 2 ; p <= n ; p ++ ) { if ( hash [ p ] ) { int count = 0 ; if ( n % p == 0 ) { while ( n % p == 0 ) { n = n / p ; count ++ ; } total = total * ( count + 1 ) ; } } } return total ; } bool isHighlyCompositeNumber ( int N ) { int NdivCount = divCount ( N ) ; for ( int i = 1 ; i < N ; i ++ ) { int idivCount = divCount ( i ) ; if ( idivCount >= NdivCount ) return false ; } return true ; } int main ( ) { int N = 12 ; if ( isHighlyCompositeNumber ( N ) ) cout << " Yes " ; else cout << " No " ; return 0 ; }