Given an integer N greater than 2, the task is to find an element M such that GCD(N, M) is maximum.
Examples:
Input: N = 10
Output: 5
Explanation:
gcd(1, 10), gcd(3, 10), gcd(7, 10), gcd(9, 10) is 1,
gcd(2, 10), gcd(4, 10), gcd(6, 10), gcd(8, 10) is 2,
gcd(5, 10) is 5 which is maximum.Input: N = 21
Output: 7
Explanation:
gcd(7, 21) is maximum among all the integers from 1 to 21.
Naive Approach: The simplest approach is to loop through all the numbers in the range [1, N-1] and find GCD of each number with N. The number which given maximum GCD with N is the required result.
Time Complexity: O(N)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, we observe that the GCD of two numbers will be definitely one of its divisors in the range [1, N-1]. And, GCD will be maximum if the divisor is maximum.
Therefore, the idea is to find all the divisors of N and store a maximum of those divisors which is the required result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the integer M// such that gcd(N, M) is maximumint findMaximumGcd(int n){ // Initialize a variable int max_gcd = 1; // Find all the divisors of N and // return the maximum divisor for (int i = 1; i * i <= n; i++) { // Check if i is divisible by N if (n % i == 0) { // Update max_gcd if (i > max_gcd) max_gcd = i; if ((n / i != i) && (n / i != n) && ((n / i) > max_gcd)) max_gcd = n / i; } } // Return the maximum value return max_gcd;}// Driver Codeint main(){ // Given Number int N = 10; // Function Call cout << findMaximumGcd(N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find the integer M// such that gcd(N, M) is maximumstatic int findMaximumGcd(int n){ // Initialize a variable int max_gcd = 1; // Find all the divisors of N and // return the maximum divisor for(int i = 1; i * i <= n; i++) { // Check if i is divisible by N if (n % i == 0) { // Update max_gcd if (i > max_gcd) max_gcd = i; if ((n / i != i) && (n / i != n) && ((n / i) > max_gcd)) max_gcd = n / i; } } // Return the maximum value return max_gcd;}// Driver Codepublic static void main(String[] args){ // Given Number int N = 10; // Function Call System.out.print(findMaximumGcd(N));}}// This code is contributed by Amit Katiyar |
Python3
# Python3 program for the above approach# Function to find the integer M # such that gcd(N, M) is maximumdef findMaximumGcd(n): # Initialize variables max_gcd = 1 i = 1 # Find all the divisors of N and # return the maximum divisor while (i * i <= n): # Check if i is divisible by N if n % i == 0: # Update max_gcd if (i > max_gcd): max_gcd = i if ((n / i != i) and (n / i != n) and ((n / i) > max_gcd)): max_gcd = n / i i += 1 # Return the maximum value return (int(max_gcd))# Driver Code if __name__ == '__main__': # Given number n = 10 # Function call print(findMaximumGcd(n)) # This code is contributed by virusbuddah_ |
C#
// C# program for the // above approachusing System;class GFG{// Function to find the // integer M such that // gcd(N, M) is maximumstatic int findMaximumGcd(int n){ // Initialize a variable int max_gcd = 1; // Find all the divisors of // N and return the maximum // divisor for(int i = 1; i * i <= n; i++) { // Check if i is // divisible by N if (n % i == 0) { // Update max_gcd if (i > max_gcd) max_gcd = i; if ((n / i != i) && (n / i != n) && ((n / i) > max_gcd)) max_gcd = n / i; } } // Return the maximum // value return max_gcd;}// Driver Codepublic static void Main(String[] args){ // Given Number int N = 10; // Function Call Console.Write(findMaximumGcd(N));}}// This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript program to implement// the above approach// Function to find the integer M// such that gcd(N, M) is maximumfunction findMaximumGcd(n){ // Initialize a variable let max_gcd = 1; // Find all the divisors of N and // return the maximum divisor for(let i = 1; i * i <= n; i++) { // Check if i is divisible by N if (n % i == 0) { // Update max_gcd if (i > max_gcd) max_gcd = i; if ((n / i != i) && (n / i != n) && ((n / i) > max_gcd)) max_gcd = n / i; } } // Return the maximum value return max_gcd;} // Driver Code // Given Number let N = 10; // Function Call document.write(findMaximumGcd(N));</script> |
5
Time Complexity: O(log2N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
