# Find pair with maximum GCD for integers in range 2 to N

Given a number** N**, the task is to find a pair of integers in the range **[2, N]** with maximum GCD.**Examples:**

Input:N = 10Output:5Explaination:

Maximum possible GCD between all possible pairs is 5 which occurs for the pair (10, 5).Input:N = 13Output:6Explaination:

Maximum possible GCD between all possible pairs is 6 which occurs for the pair (12, 6).

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the

DSA Self Paced Courseat a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please referComplete Interview Preparation Course.In case you wish to attend

live classeswith experts, please referDSA Live Classes for Working ProfessionalsandCompetitive Programming Live for Students.

**Approach:**

Follow the steps below to solve the problem:

- If
**N**is even, return the pair**{N, N / 2}**.

Illustration:

IfN = 10, Maximum possible GCD for any pair is 5( for the pair {5, 10}).

IfN = 20, Maximum possible GCD for any pair is 10( for the pair {20, 10}).

- If
**N**is odd, then return the pair**{N – 1, (N – 1) / 2}**.

Illustration:

IfN = 11, Maximum possible GCD for any pair is 5( for the pair {5, 10}).

IfN = 21, Maximum possible GCD for any pair is 10( for the pair {20, 10}).

- Below is the implementation of the above approach:

## C++

`// C++ Program to find a pair of` `// integers less than or equal` `// to N such that their GCD` `// is maximum` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to find the required` `// pair whose GCD is maximum` `void` `solve(` `int` `N)` `{` ` ` `// If N is even` ` ` `if` `(N % 2 == 0) {` ` ` `cout << N / 2 << ` `" "` ` ` `<< N << endl;` ` ` `}` ` ` `// If N is odd` ` ` `else` `{` ` ` `cout << (N - 1) / 2 << ` `" "` ` ` `<< (N - 1) << endl;` ` ` `}` `}` `// Driver Code` `int` `main()` `{` ` ` `int` `N = 10;` ` ` `solve(N);` ` ` `return` `0;` `}` |

## Java

`// Java program to find a pair of` `// integers less than or equal` `// to N such that their GCD` `// is maximum` `class` `GFG{` `// Function to find the required` `// pair whose GCD is maximum` `static` `void` `solve(` `int` `N)` `{` ` ` ` ` `// If N is even` ` ` `if` `(N % ` `2` `== ` `0` `)` ` ` `{` ` ` `System.out.print(N / ` `2` `+ ` `" "` `+` ` ` `N + ` `"\n"` `);` ` ` `}` ` ` ` ` `// If N is odd` ` ` `else` ` ` `{` ` ` `System.out.print((N - ` `1` `) / ` `2` `+ ` `" "` `+` ` ` `(N - ` `1` `) + ` `"\n"` `);` ` ` `}` `}` `// Driver Code` `public` `static` `void` `main(String[] args)` `{` ` ` `int` `N = ` `10` `;` ` ` ` ` `solve(N);` `}` `}` `// This code is contributed by Amit Katiyar` |

## Python3

`# Python3 Program to find a pair ` `# of integers less than or equal` `# to N such that their GCD` `# is maximum` `# Function to find the required` `# pair whose GCD is maximum` `def` `solve(N):` ` ` ` ` `# If N is even` ` ` `if` `(N ` `%` `2` `=` `=` `0` `):` ` ` `print` `(N ` `/` `/` `2` `, N)` ` ` ` ` `# If N is odd` ` ` `else` `:` ` ` `print` `((N ` `-` `1` `) ` `/` `/` `2` `, (N ` `-` `1` `))` ` ` `# Driver Code` `N ` `=` `10` `solve(N)` `# This code is contributed by divyamohan123` |

## C#

`// C# program to find a pair of` `// integers less than or equal` `// to N such that their GCD` `// is maximum` `using` `System;` `class` `GFG{` `// Function to find the required` `// pair whose GCD is maximum` `static` `void` `solve(` `int` `N)` `{` ` ` ` ` `// If N is even` ` ` `if` `(N % 2 == 0)` ` ` `{` ` ` `Console.Write(N / 2 + ` `" "` `+` ` ` `N + ` `"\n"` `);` ` ` `}` ` ` ` ` `// If N is odd` ` ` `else` ` ` `{` ` ` `Console.Write((N - 1) / 2 + ` `" "` `+` ` ` `(N - 1) + ` `"\n"` `);` ` ` `}` `}` `// Driver Code` `public` `static` `void` `Main(String[] args)` `{` ` ` `int` `N = 10;` ` ` ` ` `solve(N);` `}` `}` `// This code is contributed by shivanisinghss2110` |

## Javascript

`<script>` `// JavaScript program to find a pair of` `// integers less than or equal` `// to N such that their GCD` `// is maximum` ` ` `// Function to find the required` ` ` `// pair whose GCD is maximum` ` ` `function` `solve(N) {` ` ` `// If N is even` ` ` `if` `(N % 2 == 0) {` ` ` `document.write(N / 2 + ` `" "` `+ N + ` `"<br/>"` `);` ` ` `}` ` ` `// If N is odd` ` ` `else` `{` ` ` `document.write((N - 1) / 2 + ` `" "` `+ (N - 1) + ` `"<br/>"` `);` ` ` `}` ` ` `}` ` ` `// Driver Code` ` ` ` ` `var` `N = 10;` ` ` `solve(N);` `// This code is contributed by todaysgaurav` `</script>` |

**Output:**

5 10

**Time Complexity:**O(1)**Auxiliary Space:**O(1)