Sum of LCM ( 1 , n ) , LCM ( 2 , n ) , LCM ( 3 , n ) , ... , LCM ( n , n ) | Java 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
class GFG { static int n = 1000002 ; static int [ ] phi = new int [ n + 2 ] ; static int [ ] ans = new int [ n + 2 ] ; static void ETF ( ) { for ( int i = 1 ; i <= n ; i ++ ) { phi [ i ] = i ; } for ( int i = 2 ; i <= n ; i ++ ) { if ( phi [ i ] == i ) { phi [ i ] = i - 1 ; for ( int j = 2 * i ; j <= n ; j += i ) { phi [ j ] = ( phi [ j ] * ( i - 1 ) ) / i ; } } } } static int LcmSum ( int m ) { ETF ( ) ; for ( int i = 1 ; i <= n ; i ++ ) { for ( int j = i ; j <= n ; j += i ) { ans [ j ] += ( i * phi [ i ] ) ; } } int answer = ans [ m ] ; answer = ( answer + 1 ) * m ; answer = answer / 2 ; return answer ; } public static void main ( String [ ] args ) { int m = 5 ; System . out . println ( LcmSum ( m ) ) ; } }