Given two numbers n and m. Find the biggest integer a(gcd), such that all integers n, n + 1, n + 2, …, m are divisible by a.
Examples:
Input : n = 1, m = 2 Output: 1 Explanation: Here, series become 1, 2. So, the greatest no which divides both of them is 1. Input : n = 475, m = 475 Output : 475 Explanation: Here, series has only one term 475. So, greatest no which divides 475 is 475.
Here, We have to examine only two cases:
- if a = b : the segment consists of a single number, hence the answer is a.
- if a < b : we have gcd(n, n + 1, n?+ 2, …, m) = gcd(gcd(n, n + 1), n + 2, …, m) = gcd(1, n + 2, …, n) = 1.
C++
// GCD of given range#include <bits/stdc++.h>using namespace std; int rangeGCD(int n, int m){ return (n == m)? n : 1;} int main(){ int n = 475; int m = 475; cout << rangeGCD(n, m); return 0;} |
Java
// GCD of given range import java.io.*; class GFG { static int rangeGCD(int n, int m) { return (n == m) ? n : 1; } public static void main(String[] args) { int n = 475; int m = 475; System.out.println(rangeGCD(n, m)); }} // This code is contributed by Ajit. |
Python3
# GCD of given range def rangeGCD(n, m): return n if(n == m) else 1 # Driver coden, m = 475, 475print(rangeGCD(n, m)) # This code is contributed by Anant Agarwal. |
C#
// GCD of given rangeusing System; class GFG { static int rangeGCD(int n, int m) { return (n == m) ? n : 1; } public static void Main() { int n = 475; int m = 475; Console.WriteLine(rangeGCD(n, m)); }} // This code is contributed by Anant Agarwal. |
PHP
<?php// PHP program for // GCD of given range // function returns the GCDfunction rangeGCD($n, $m){ return ($n == $m)? $n : 1;} // Driver Code $n = 475; $m = 475; echo rangeGCD($n, $m); // This code is contributed by anuj_67.?> |
Javascript
<script>// GCD of given range function rangeGCD( n, m) { return (n == m) ? n : 1; } var n = 475; var m = 475; document.write(rangeGCD(n, m));</script> |
Output:
475
Time Complexity: O(1)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

… [Trackback]
[…] Here you will find 89634 additional Information on that Topic: geeksforgeeks.org/gcd-of-elements-in-a-given-range/ […]
… [Trackback]
[…] Find More Info here to that Topic: geeksforgeeks.org/gcd-of-elements-in-a-given-range/ […]
… [Trackback]
[…] Find More Information here on that Topic: geeksforgeeks.org/gcd-of-elements-in-a-given-range/ […]
… [Trackback]
[…] Find More Information here to that Topic: geeksforgeeks.org/gcd-of-elements-in-a-given-range/ […]
… [Trackback]
[…] Find More Information here on that Topic: geeksforgeeks.org/gcd-of-elements-in-a-given-range/ […]