Sum of GCD of all numbers upto N with N itself | Function to Find Sum of GCD of each numbers ; Consider all prime factors of no . and subtract their multiples from result ; Check if p is a prime factor ; If yes , then update no and result ; If no has a prime factor greater than sqrt ( n ) then at - most one such prime factor exists ; Return the result ; Finding GCD of pairs ; Calculate the divisors ; Return count of numbers from 1 to N with GCD d with N ; Check if d1 and d2 are equal then skip this ; Driver code
function getCount ( d , n ) { let no = Math . floor ( n / d ) ; let result = no ; for ( let p = 2 ; p * p <= no ; ++ p ) { if ( no % p == 0 ) { while ( no % p == 0 ) no = Math . floor ( no / p ) ; result = Math . floor ( result - result / p ) ; } } if ( no > 1 ) result = Math . floor ( result - result / no ) ; return result ; } function sumOfGCDofPairs ( n ) { let res = 0 ; for ( let i = 1 ; i * i <= n ; i ++ ) { if ( n % i == 0 ) { let d1 = i ; let d2 = Math . floor ( n / i ) ; res += d1 * getCount ( d1 , n ) ; if ( d1 != d2 ) res += d2 * getCount ( d2 , n ) ; } } return res ; } let n = 12 ; document . write ( sumOfGCDofPairs ( n ) ) ;