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 Math . 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
def getCount ( d , n ) : NEW_LINE INDENT no = n // d ; NEW_LINE result = no ; NEW_LINE for p in range ( 2 , int ( pow ( no , 1 / 2 ) ) + 1 ) : NEW_LINE INDENT if ( no % p == 0 ) : NEW_LINE INDENT while ( no % p == 0 ) : NEW_LINE INDENT no //= p ; NEW_LINE DEDENT result -= result // p ; NEW_LINE DEDENT DEDENT if ( no > 1 ) : NEW_LINE INDENT result -= result // no ; NEW_LINE DEDENT return result ; NEW_LINE DEDENT def sumOfGCDofPairs ( n ) : NEW_LINE INDENT res = 0 ; NEW_LINE for i in range ( 1 , int ( pow ( n , 1 / 2 ) ) + 1 ) : NEW_LINE INDENT if ( n % i == 0 ) : NEW_LINE INDENT d1 = i ; NEW_LINE d2 = n // i ; NEW_LINE res += d1 * getCount ( d1 , n ) ; NEW_LINE if ( d1 != d2 ) : NEW_LINE INDENT res += d2 * getCount ( d2 , n ) ; NEW_LINE DEDENT DEDENT DEDENT return res ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 12 ; NEW_LINE print ( sumOfGCDofPairs ( n ) ) ; NEW_LINE DEDENT