# Count number of pairs (A <= N, B <= N) such that gcd (A , B) is B

• Difficulty Level : Hard
• Last Updated : 09 Mar, 2021

Given a number n. We need find the number of ordered pairs of a and b such gcd(a, b) is b itself
Examples :

Input : n = 2
Output : 3
(1, 1) (2, 2) and (2, 1)

Input : n = 3
Output : 5
(1, 1) (2, 2) (3, 3) (2, 1) and (3, 1)

Naive approach : gcd(a, b) = b means b is a factor of a. So total number of pairs will be equal to sum of divisors for each a = 1 to n. Please refer find all divisors of a natural number for implementation.
Efficient approach : gcd(a, b) = b means that a is a multiple of b. So total number of pairs will be sum of number of multiples of each b (where b varies from 1 to n) which are less than or equal to n.
For a number i, number of multiples of i is less than or equal to floor(n/i). So what we need to do is just sum the floor(n/i) for each i = 1 to n and print it. But more optimizations can be done. floor(n/i) can have atmost 2*sqrt(n) values for i >= sqrt(n). floor(n/i) can vary from 1 to sqrt(n) and similarly for i = 1 to sqrt(n) floor(n/i) can have values from 1 to sqrt(n). So total of 2*sqrt(n) distinct values

let floor(n/i) = k
k <= n/i < k + 1
n/k+1 < i <= n/k
floor(n/k+1) < i <= floor(n/k)
Thus for given k the largest value of i for
which the floor(n/i) = k is floor(n/k)
and all the set of i for which the
floor(n/i) = k are consecutive

## CPP

 // C++ implementation of counting pairs// such that gcd (a, b) = b#include using namespace std; // returns number of valid pairsint CountPairs(int n){    // initialize k    int k = n;     // loop till imin <= n    int imin = 1;     // Initialize result    int ans = 0;     while (imin <= n) {         // max i with given k floor(n/k)        int imax = n / k;         // adding k*(number of i with        // floor(n/i) = k to ans        ans += k * (imax - imin + 1);         // set imin = imax + 1 and k = n/imin        imin = imax + 1;        k = n / imin;    }     return ans;} // Driver functionint main(){    cout << CountPairs(1) << endl;    cout << CountPairs(2) << endl;    cout << CountPairs(3) << endl;    return 0;}

## Java

 // Java implementation of counting pairs// such that gcd (a, b) = bclass GFG {         // returns number of valid pairs    static int CountPairs(int n) {                 // initialize k        int k = n;             // loop till imin <= n        int imin = 1;             // Initialize result        int ans = 0;             while (imin <= n) {                 // max i with given k floor(n/k)            int imax = n / k;                     // adding k*(number of i with            // floor(n/i) = k to ans            ans += k * (imax - imin + 1);                     // set imin = imax + 1            // and k = n/imin            imin = imax + 1;            k = n / imin;        }             return ans;    }         // Driver code    public static void main(String[] args) {        System.out.println(CountPairs(1));        System.out.println(CountPairs(2));        System.out.println(CountPairs(3));    }} // This code is contributed by Anant Agarwal.

## Python3

 # Python implementation of counting# pairs such that gcd (a, b) = b # returns number of valid pairsdef CountPairs(n):         # initialize k    k = n     # loop till imin <= n    imin = 1     # Initialize result    ans = 0     while(imin <= n):         # max i with given k floor(n / k)        imax = n / k         # adding k*(number of i with        # floor(n / i) = k to ans        ans += k * (imax - imin + 1)         # set imin = imax + 1 and        # k = n / imin        imin = imax + 1        k = n / imin     return ans     # Driver codeprint(CountPairs(1))print(CountPairs(2))print(CountPairs(3)) # This code is contributed by Anant Agarwal.

## C#

 // C# implementation of counting// pairs such that gcd (a, b) = busing System; class GFG {         // returns number of valid pairs    static int CountPairs(int n)    {                 // initialize k        int k = n;             // loop till imin <= n        int imin = 1;             // Initialize result        int ans = 0;             while (imin <= n) {                 // max i with given            // k floor(n / k)            int imax = n / k;                     // adding k * (number of i             // with floor(n / i) = k            // to ans            ans += k * (imax - imin + 1);                     // set imin = imax + 1            // and k = n / imin            imin = imax + 1;            k = n / imin;        }             return ans;    }         // Driver code    public static void Main(String []args)    {        Console.WriteLine(CountPairs(1));        Console.WriteLine(CountPairs(2));        Console.WriteLine(CountPairs(3));    }} // This code is contributed by vt_m.



## Javascript



Output :

1
3
5

This article is contributed by Ayush Jha. If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to contribute@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.