Euler 's Totient function for all numbers smaller than or equal to n | Computes and prints totient of all numbers smaller than or equal to n . ; Create and initialize an array to store phi or totient values ; indicates not evaluated yet and initializes for product formula . ; Compute other Phi values ; If phi [ p ] is not computed already , then number p is prime ; Phi of a prime number p is always equal to p - 1. ; Update phi values of all multiples of p ; Add contribution of p to its multiple i by multiplying with ( 1 - 1 / $p ) ; Print precomputed phi values ; Driver Code
< ? php function computeTotient ( $ n ) { for ( $ i = 1 ; $ i <= $ n ; $ i ++ ) $ phi [ $ i ] = $ i ; for ( $ p = 2 ; $ p <= $ n ; $ p ++ ) { if ( $ phi [ $ p ] == $ p ) { $ phi [ $ p ] = $ p - 1 ; for ( $ i = 2 * $ p ; $ i <= $ n ; $ i += $ p ) { $ phi [ $ i ] = ( $ phi [ $ i ] / $ p ) * ( $ p - 1 ) ; } } } for ( $ i = 1 ; $ i <= $ n ; $ i ++ ) echo " Totient ▁ of ▁ " , $ i , " ▁ is ▁ " , $ phi [ $ i ] , " STRNEWLINE " ; } $ n = 12 ; computeTotient ( $ n ) ; ? >