Sum of LCM ( 1 , n ) , LCM ( 2 , n ) , LCM ( 3 , n ) , ... , LCM ( n , n ) | javascript 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
var n = 1000002 ; var phi = Array ( n + 2 ) . fill ( 0 ) ; var ans = Array ( n + 2 ) . fill ( 0 ) ; function ETF ( ) { 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 ] = ( phi [ j ] * ( i - 1 ) ) / i ; } } } } function LcmSum ( m ) { ETF ( ) ; for ( i = 1 ; i <= n ; i ++ ) { for ( j = i ; j <= n ; j += i ) { ans [ j ] += ( i * phi [ i ] ) ; } } var answer = ans [ m ] ; answer = ( answer + 1 ) * m ; answer = answer / 2 ; return answer ; } var m = 5 ; document . write ( LcmSum ( m ) ) ;