GCD of elements in a given range

0 0 2 minutes read

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 code
n, m = 475, 475
print(rangeGCD(n, m))
   
# This code is contributed by Anant Agarwal.

C#

// GCD of given range
using 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 GCD
function 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:

Time Complexity: O(1)

Auxiliary Space: O(1)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!