Highly Composite Numbers | 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 ; Given Number N ; Function Call
def divCount ( n ) : NEW_LINE INDENT Hash = [ True for i in range ( n + 1 ) ] NEW_LINE p = 2 NEW_LINE while ( ( p * p ) < n ) : NEW_LINE INDENT if bool ( Hash [ p ] ) : NEW_LINE INDENT i = p * 2 NEW_LINE while i < n : NEW_LINE INDENT Hash [ i ] = False NEW_LINE i += p NEW_LINE DEDENT DEDENT p += 1 NEW_LINE DEDENT total = 1 NEW_LINE for P in range ( 2 , n + 1 ) : NEW_LINE INDENT if ( bool ( Hash [ P ] ) ) : NEW_LINE INDENT count = 0 NEW_LINE if ( n % P == 0 ) : NEW_LINE INDENT while ( n % P == 0 ) : NEW_LINE INDENT n = n // P NEW_LINE count += 1 NEW_LINE DEDENT total = total * ( count + 1 ) NEW_LINE DEDENT DEDENT DEDENT return total NEW_LINE DEDENT def isHighlyCompositeNumber ( N ) : NEW_LINE INDENT NdivCount = divCount ( N ) NEW_LINE for i in range ( N ) : NEW_LINE INDENT idivCount = divCount ( i ) NEW_LINE if ( idivCount >= NdivCount ) : NEW_LINE INDENT return bool ( False ) NEW_LINE DEDENT DEDENT return bool ( True ) NEW_LINE DEDENT N = 12 NEW_LINE if ( bool ( isHighlyCompositeNumber ( N ) ) ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT