Highly Totient Number | CPP 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; 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 ; } void Highly_Totient ( int n ) { int count = 0 , p_count = -1 , i = 1 ; map < int , int > mp ; for ( int i = 1 ; i < 100000 ; i ++ ) mp [ phi ( i ) ] ++ ; while ( count < n ) { if ( mp [ i ] > p_count ) { cout << i ; if ( count < n - 1 ) cout << " , ▁ " ; p_count = mp [ i ] ; count ++ ; } i ++ ; } } int main ( ) { int n = 20 ; Highly_Totient ( n ) ; return 0 ; }