Euler 's Totient function for all numbers smaller than or equal to n | Java program to compute 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 ; 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
import java . util . * ; class GFG { static void computeTotient ( int n ) { long phi [ ] = new long [ n + 1 ] ; for ( int i = 1 ; i <= n ; i ++ ) for ( int p = 2 ; p <= n ; p ++ ) { if ( phi [ p ] == p ) { phi [ p ] = p - 1 ; for ( int i = 2 * p ; i <= n ; i += p ) { phi [ i ] = ( phi [ i ] / p ) * ( p - 1 ) ; } } } for ( int i = 1 ; i <= n ; i ++ ) System . out . println ( " Totient ▁ of ▁ " + i + " ▁ is ▁ " + phi [ i ] ) ; } public static void main ( String [ ] args ) { int n = 12 ; computeTotient ( n ) ; } }