text: Euler 's Totient Function | C program to calculate Euler ' s ▁ Totient ▁ Function ▁ using ▁ Euler ' s product formula ; Consider all prime factors of n and for every prime factor p , multiply result with ( 1 - 1 / p ) ; 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 ) ; Driver program to test above function
code: #include <stdio.h> NEW_LINE int phi ( int n ) { for ( int p = 2 ; p * p <= n ; ++ p ) { if ( n % p == 0 ) { while ( n % p == 0 ) n /= p ; result *= ( 1.0 - ( 1.0 / ( float ) p ) ) ; } } if ( n > 1 ) result *= ( 1.0 - ( 1.0 / ( float ) n ) ) ; return ( int ) result ; } int main ( ) { int n ; for ( n = 1 ; n <= 10 ; n ++ ) printf ( " phi ( % d ) ▁ = ▁ % d STRNEWLINE " , n , phi ( n ) ) ; return 0 ; }