Highly Totient Number | Function to find euler totient number ; Consider all prime factors of n and subtract their multiples from result ; Check if p is a prime factor . ; If yes , then update n and result ; If n has a prime factor greater than sqrt ( n ) ( There can be at - most one such prime factor ) ; Function to find first n highly totient numbers ; Count of Highly totient numbers and value of count of phi of previous numbers ; Store all the values of phi ( x ) upto 10 ^ 5 with frequencies ; If count is greater than count of previous element ; Display the number ; Store the value of phi ; Driver code ; Function call
def phi ( n ) : NEW_LINE INDENT p = 2 NEW_LINE while ( p * p <= n ) : NEW_LINE INDENT if ( n % p == 0 ) : NEW_LINE INDENT while ( n % p == 0 ) : NEW_LINE INDENT n //= p ; NEW_LINE DEDENT result -= ( result // p ) ; NEW_LINE DEDENT p += 1 NEW_LINE DEDENT if ( n > 1 ) : NEW_LINE INDENT result -= ( result // n ) ; NEW_LINE DEDENT return result ; NEW_LINE DEDENT def Highly_Totient ( n ) : NEW_LINE INDENT count = 0 NEW_LINE p_count = - 1 NEW_LINE mp = dict ( ) NEW_LINE i = 1 NEW_LINE while i < 100000 : NEW_LINE INDENT tmp = phi ( i ) NEW_LINE if tmp not in mp : NEW_LINE INDENT mp [ tmp ] = 0 NEW_LINE DEDENT mp [ tmp ] += 1 ; NEW_LINE i += 1 NEW_LINE DEDENT i = 1 NEW_LINE while ( count < n ) : NEW_LINE INDENT if ( ( i in mp ) and mp [ i ] > p_count ) : NEW_LINE INDENT print ( i , end = ' ' ) ; NEW_LINE if ( count < n - 1 ) : NEW_LINE INDENT print ( " , ▁ " , end = ' ' ) ; NEW_LINE DEDENT p_count = mp [ i ] ; NEW_LINE count += 1 NEW_LINE DEDENT i += 1 NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 20 ; NEW_LINE Highly_Totient ( n ) ; NEW_LINE DEDENT