Dados dos enteros positivos a y b y un rango [bajo, alto] . La tarea es encontrar el máximo común divisor de a y b que se encuentran en el rango dado. Si no existe ningún divisor en el rango, imprima -1.
Ejemplos:
Input : a = 9, b = 27, low = 1, high = 5 Output : 3 3 is the highest number that lies in range [1, 5] and is common divisor of 9 and 27. Input : a = 9, b = 27, low = 10, high = 11 Output : -1
La idea es encontrar el Máximo Común Divisor MCD(a, b) de a y b. Ahora observa, el divisor de MCD(a, b) es también el divisor de a y b. Entonces, iteraremos un ciclo i de 1 a sqrt (GCD (a, b)) y verificaremos si divido GCD (a, b). Además, observe si i es divisor de MCD(a, b) entonces MCD(a, b)/i también será divisor. Entonces, para cada iteración, si i divide GCD(a, b), encontraremos el máximo de i y GCD(a, b)/i si se encuentran en el rango.
A continuación se muestra la implementación de este enfoque:
C++
// CPP Program to find the Greatest Common divisor
// of two number which is in given range
#include <bits/stdc++.h>
using namespace std;
// Return the greatest common divisor
// of two numbers
int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Return the greatest common divisor of a
// and b which lie in the given range.
int maxDivisorRange(int a, int b, int l, int h)
{
int g = gcd(a, b);
int res = -1;
// Loop from 1 to sqrt(GCD(a, b).
for (int i = l; i * i <= g && i <= h; i++)
// if i divides the GCD(a, b), then
// find maximum of three numbers res,
// i and g/i
if (g % i == 0)
res = max({res, i, g / i});
return res;
}
// Driven Program
int main()
{
int a = 3, b = 27, l = 1, h = 5;
cout << maxDivisorRange(a, b, l, h) << endl;
return 0;
}
Java
// Java Program to find the Greatest Common
// divisor of two number which is in given
// range
import java.io.*;
class GFG {
// Return the greatest common divisor
// of two numbers
static int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Return the greatest common divisor of a
// and b which lie in the given range.
static int maxDivisorRange(int a, int b,
int l, int h)
{
int g = gcd(a, b);
int res = -1;
// Loop from 1 to sqrt(GCD(a, b).
for (int i = l; i * i <= g && i <= h; i++)
// if i divides the GCD(a, b), then
// find maximum of three numbers res,
// i and g/i
if (g % i == 0)
res = Math.max(res,
Math.max(i, g / i));
return res;
}
// Driven Program
public static void main (String[] args)
{
int a = 3, b = 27, l = 1, h = 5;
System.out.println(
maxDivisorRange(a, b, l, h));
}
}
// This code is contributed by anuj_67.
Python3
# Python3 Program to find the # Greatest Common divisor # of two number which is # in given range # Return the greatest common # divisor of two numbers def gcd(a, b): if(b == 0): return a; return gcd(b, a % b); # Return the greatest common # divisor of a and b which # lie in the given range. def maxDivisorRange(a, b, l, h): g = gcd(a, b); res = -1; # Loop from 1 to # sqrt(GCD(a, b). i = l; while(i * i <= g and i <= h): # if i divides the GCD(a, b), # then find maximum of three # numbers res, i and g/i if(g % i == 0): res = max(res,max(i, g/i)); i+=1; return int(res); # Driver Code if __name__ == "__main__": a = 3; b = 27; l = 1; h = 5; print(maxDivisorRange(a, b, l, h)); # This code is contributed by mits
C#
// C# Program to find the Greatest Common
// divisor of two number which is in given
// range
using System;
class GFG {
// Return the greatest common divisor
// of two numbers
static int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Return the greatest common divisor of a
// and b which lie in the given range.
static int maxDivisorRange(int a, int b,
int l, int h)
{
int g = gcd(a, b);
int res = -1;
// Loop from 1 to sqrt(GCD(a, b).
for (int i = l; i * i <= g && i <= h; i++)
// if i divides the GCD(a, b), then
// find maximum of three numbers res,
// i and g/i
if (g % i == 0)
res = Math.Max(res,
Math.Max(i, g / i));
return res;
}
// Driven Program
public static void Main ()
{
int a = 3, b = 27, l = 1, h = 5;
Console.WriteLine(
maxDivisorRange(a, b, l, h));
}
}
// This code is contributed by anuj_67.
PHP
<?php
// PHP Program to find the
// Greatest Common divisor
// of two number which is
// in given range
// Return the greatest common
// divisor of two numbers
function gcd($a, $b)
{
if ($b == 0)
return $a;
return gcd($b, $a % $b);
}
// Return the greatest common
// divisor of a and b which
// lie in the given range.
function maxDivisorRange($a, $b,
$l, $h)
{
$g = gcd($a, $b);
$res = -1;
// Loop from 1 to
// sqrt(GCD(a, b).
for ($i = $l; $i * $i <= $g and
$i <= $h; $i++)
// if i divides the GCD(a, b),
// then find maximum of three
// numbers res, i and g/i
if ($g % $i == 0)
$res = max($res,
max($i, $g / $i));
return $res;
}
// Driver Code
$a = 3; $b = 27;
$l = 1; $h = 5;
echo maxDivisorRange($a, $b, $l, $h);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// JavaScript Program to find the Greatest Common
// divisor of two number which is in given
// range
// Return the greatest common divisor
// of two numbers
function gcd(a , b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
// Return the greatest common divisor of a
// and b which lie in the given range.
function maxDivisorRange(a , b , l , h) {
var g = gcd(a, b);
var res = -1;
// Loop from 1 to sqrt(GCD(a, b).
for (i = l; i * i <= g && i <= h; i++)
// if i divides the GCD(a, b), then
// find maximum of three numbers res,
// i and g/i
if (g % i == 0)
res = Math.max(res, Math.max(i, g / i));
return res;
}
// Driven Program
var a = 3, b = 27, l = 1, h = 5;
document.write(maxDivisorRange(a, b, l, h));
// This code is contributed by todaysgaurav
</script>
Producción:
3