Find the greatest common divisor in a given range

The question states that we need to find the GCD within a given range. We will get two positive integers x and y and two integers p and q in the range [p,q]. We need to find the GCD (greatest common divisor) of the numbers x and y that fall in the range [p,q]. GCD, known in mathematics as the greatest common divisor, is the largest positive integer that divides two given positive integers. The given integer must not be zero. For any two positive integers x and y, it is expressed as gcd(x,y).

For example, we have two positive integers 6 and 9. The greatest common divisor gcd(6,9) will be 3 because it is the largest number that divides these two numbers.

But in this problem, we need to find the greatest common divisor of two given positive integers within a specified range. Let us understand this problem through an example. We will be given 4 numbers as input x and y to find the gcd of these numbers and two numbers indicating the range of gcd i.e. [p,q].

Input: x=8, y=12, p=1, q=3

Output: 2

Explanation - Since the greatest common divisor of the given two numbers x and y is 4. But 4 is not in the range [1,3]. The greatest common divisor in the range [1,3] is 2, which is our desired output.

Input: x=17, y=15, a=5, b=10

Output:-1

Explanation - The greatest common divisor of the numbers 17 and 15 is 1. Because 1 is not in the given range [5,10]. When there is no common divisor in the given range, we need to print -1 as output.

algorithm

The algorithm we use to solve the problem is very simple and mathematically related. First, we will find the gcd (greatest common divisor) of the numbers x and y. In C, there is a built-in function called gcd() which returns the greatest common divisor of numbers as output.

grammar

int divisor=gcd(x,y);

We can also use the efficient method of Euclidean's algorithm to find the gcd of two numbers. Both work at the same time, and the time complexity is O(log(min(x,y)).

Now, we can use simple laws of arithmetic to conclude that the number divided by the gcd of two numbers will also be divided by the two numbers themselves . So, iterating from i=1 to sqrt(gcd(x,y)) in a for loop will help us get all the common divisors of the number.

Then, check if each i up to sqrt(gcd(x,y)) i divides gcd(x,y). If i divides gcd(x,y), then we can say that gcd(x,y)/i will also be the divisor of gcd, thus concluding that it is also the common divisor of the numbers x and y.

Let us understand this concept through an example. Suppose x and y are 32 and 48 respectively. gcd(18,27) is 16. So in this case, we will iterate from i=1 to i<=4, which is sqrt(16). Let us consider i=2. Here I divide by gcd(18,27), which is 16/2, which equals 8. So gcd(x,y)/i also divides gcd(x,y) to get i. <=4，即 sqrt(16)。让我们考虑 i=2。这里我除以 gcd(18,27)，即 16/2，等于 8。因此 gcd(x,y)/i 也会除 gcd(x,y) 得到 i。

Note - If the number n divided by any number x gives y, which can be expressed as $\frac{n}{x}\:=\:y$ then y will divide n by x $ (x\:\times\:y\:=\:n)$.

This algorithm may be the most effective way to solve this problem. While following this algorithm, we will constantly check if the common denominator is in the range [a,b]. If not, we will use the max() function to continuously update the divisor in the variable to get the greatest common divisor in the range.

max() function syntax

int m = max(a,b);

It returns the maximum value of a and b.

method

Here is the approach we will follow -

• Initialize a function to calculate the greatest common divisor within a given range.

• Calculate the gcd of two given positive numbers x and y.

• Initialization variable name ans = -1.

• Iterate from i=1 to i<=sqrt(gcd(x,y)) in the for loop and constantly check whether i divides gcd(x,y). <=sqrt(gcd(x,y)) 并不断检查 i 是否整除 gcd(x,y)。

• If (gcd(x,y)%i)=0, check whether i is in the range [a,b] and whether to use the max() function to store it in ans so that we can get the maximum The common denominator lies within this range.

• Also check whether gcd/i is within the range. If it is within the range, use the max() function again to update the value of ans.

• Return ans after completing all iterations in the for loop.

Example

Implementation of this method in C -

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;

// to calculate gcd of two numbers using Euclidean algorithm
int gcd(int a, int b){
   if(a == 0)
   return b;
   return gcd(b % a, a);
}

//function to calculate greatest common divisor in the given range [a,b]
int build(int x, int y, int a, int b) {

   //using C++ inbuilt library to calculate gcd of given numbers
   int z = gcd(x, y); //we can use euclidean algorithm too as an alternative
   int ans = -1; //storing -1 for the case when no common divisor lies in the range
   for(int i = 1; i<=sqrt(z); i++) { //iterating until sqrt(z) because either of two factors
      //of a number must be less than square root of the number
      if(z % i == 0) {
         if(i >= a && i <= b) //checking it i lies in the range
         ans = max(ans, i); //storing maximum value
         if((z / i) >= a && (z / i) <= b)
         ans = max(ans, z / i);
      }
   }
   return ans;
}
int main() {
   int x, y, a, b;
   x=24, y=42, a=3, b=9;
   cout << build(x, y, a, b) <<" is the gcd that lies in range ["<<a<<","<<b<<"]"<<endl;
   return 0;
}

Output

6 is the gcd that lies in range [3,9]

Time complexity: O(log(min(x,y)) sqrt(z)), where z is the greatest common divisor of two numbers x and y.

Space complexity: O(1), because no additional space is used.

in conclusion

We discussed ways to solve the gcd problem for two numbers in the range [a,b]. This is how we can solve the above problem in C using various different functions.

I hope you found this article helpful and clarified all your concepts related to this problem.

The above is the detailed content of Find the greatest common divisor in a given range. For more information, please follow other related articles on the PHP Chinese website!