Sum of LCM ( 1 , n ) , LCM ( 2 , n ) , LCM ( 3 , n ) , ... , LCM ( n , n ) | PHP implementation of the approach ; Euler totient Function ; Function to return the required LCM sum ; Summation of d * ETF ( d ) where d belongs to set of divisors of n ; Driver code
< ? php $ n = 10002 ; $ phi = array_fill ( 0 , $ n + 2 , 0 ) ; $ ans = array_fill ( 0 , $ n + 2 , 0 ) ; function ETF ( ) { global $ phi , $ n ; for ( $ i = 1 ; $ i <= $ n ; $ i ++ ) { $ phi [ $ i ] = $ i ; } for ( $ i = 2 ; $ i <= $ n ; $ i ++ ) { if ( $ phi [ $ i ] == $ i ) { $ phi [ $ i ] = $ i - 1 ; for ( $ j = 2 * $ i ; $ j <= $ n ; $ j += $ i ) { $ phi [ $ j ] = ( int ) ( ( $ phi [ $ j ] * ( $ i - 1 ) ) / $ i ) ; } } } } function LcmSum ( $ m ) { ETF ( ) ; global $ ans , $ n , $ phi ; for ( $ i = 1 ; $ i <= $ n ; $ i ++ ) { for ( $ j = $ i ; $ j <= $ n ; $ j += $ i ) { $ ans [ $ j ] += ( $ i * $ phi [ $ i ] ) ; } } $ answer = $ ans [ $ m ] ; $ answer = ( $ answer + 1 ) * $ m ; $ answer = ( int ) ( $ answer / 2 ) ; return $ answer ; } $ m = 5 ; echo LcmSum ( $ m ) ; ? >