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
function computeTotient ( n ) { let phi = new Array ( n + 1 ) ; for ( let i = 1 ; i <= n ; i ++ ) phi [ i ] = i ; for ( let p = 2 ; p <= n ; p ++ ) { if ( phi [ p ] == p ) { phi [ p ] = p - 1 ; for ( let i = 2 * p ; i <= n ; i += p ) { phi [ i ] = parseInt ( phi [ i ] / p , 10 ) * ( p - 1 ) ; } } } for ( let i = 1 ; i <= n ; i ++ ) document . write ( " " + i + " " + phi [ i ] + " " ) ; } let n = 12 ; computeTotient ( n ) ;