Count number of pairs ( A <= N , B <= N ) such that gcd ( A , B ) is B | returns number of valid pairs ; initialize k ; loop till imin <= n ; Initialize result ; max i with given k floor ( n / k ) ; adding k * ( number of i with floor ( n / i ) = k to ans ; set imin = imax + 1 and k = n / imin ; Driver code
def CountPairs ( n ) : NEW_LINE INDENT k = n NEW_LINE imin = 1 NEW_LINE ans = 0 NEW_LINE while ( imin <= n ) : NEW_LINE INDENT imax = n / k NEW_LINE ans += k * ( imax - imin + 1 ) NEW_LINE imin = imax + 1 NEW_LINE k = n / imin NEW_LINE DEDENT return ans NEW_LINE DEDENT print ( CountPairs ( 1 ) ) NEW_LINE print ( CountPairs ( 2 ) ) NEW_LINE print ( CountPairs ( 3 ) ) NEW_LINE