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 function
function CountPairs ( n ) { let k = n ; let imin = 1 ; let ans = 0 ; while ( imin <= n ) { let imax = Math . floor ( n / k ) ; ans += k * ( imax - imin + 1 ) ; imin = imax + 1 ; k = Math . floor ( n / imin ) ; } return ans ; } document . write ( CountPairs ( 1 ) + " " ) ; document . write ( CountPairs ( 2 ) + " " ) ; document . write ( CountPairs ( 3 ) + " " ) ;