Highly Totient Number | Java program to find highly totient numbers ; 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
import java . util . * ; class GFG { static int phi ( int n ) { for ( int p = 2 ; p * p <= n ; ++ p ) { if ( n % p == 0 ) { while ( n % p == 0 ) n /= p ; result -= result / p ; } } if ( n > 1 ) result -= result / n ; return result ; } static void Highly_Totient ( int n ) { int count = 0 , p_count = - 1 ; HashMap < Integer , Integer > mp = new HashMap < Integer , Integer > ( ) ; for ( int i = 1 ; i < 100000 ; i ++ ) { if ( mp . containsKey ( phi ( i ) ) ) { mp . put ( phi ( i ) , mp . get ( phi ( i ) ) + 1 ) ; } else { mp . put ( phi ( i ) , 1 ) ; } } int i = 1 ; while ( count < n ) { if ( mp . containsKey ( i ) && mp . get ( i ) > p_count ) { System . out . print ( i ) ; if ( count < n - 1 ) System . out . print ( " , ▁ " ) ; p_count = mp . get ( i ) ; count ++ ; } i ++ ; } } public static void main ( String [ ] args ) { int n = 20 ; Highly_Totient ( n ) ; } }