Program to Find GCD of Elements in a Given Range

Python Program to Find GCD of Elements in a Given Range

In the previous article, we have discussed Python Program to Sort digits of a Number in Ascending Order
Highest Common Factor (HCF) / Greatest Common Divisor (GCD) :

When at least one of the integers is not zero, the greatest positive integer that evenly divides the numbers without a remainder is called the Highest Common Factor or Greatest Common Divisor.

The GCD of 12 and 16 is, for example, 4.

Given two numbers, n, and m, and the task is to solve the equation, Find the largest integer a(gcd) that is divisible by all integers n, n + 1, n + 2,…, m.

We only need to look at two cases here:

If a = b, the segment is made up of a single number, so the answer is a.
If a = b, then gcd(n, n + 1, n?+ 2,…, m) = gcd(n, n + 1), n + 2,…, m) = gcd(1, n + 2,…, n) = 1.

Examples:

Example1:

Input:

Given First Number =   125
Given Second Number = 125

Output:

The greatest number that divides both 125 and 125 = 125

Example2:

Input:

Given First Number = 5
Given Second Number = 8

Output:

The greatest number that divides both 5 and 8 = 1

Program to Find GCD of Elements in a Given Range in Python.

Below are the ways to Find the largest integer a(gcd) that is divisible by all integers n, n + 1, n + 2,…, m.

Method #1: Using If, Else conditional  Statements (Static Input)

Approach:

  • Give the first number as static input and store it in a variable.
  • Give the second number as static input and store it in another variable.
  • Check if the first number is equal to the second number using the if conditional statement.
  • If the statement is true, then print the first number.
  • If the statement is false, then print 1.
  • The Exit of the Program.

Below is the implementation:

# Give the first number as static input and store it in a variable.
fst_numb = 125
# Give the second number as static input and store it in another variable.
secnd_numb = 125
# Check if the first number is equal to the second number using the if conditional statement.
if(fst_numb == secnd_numb):
  # If the statement is true, then print the first number.
    print("The greatest number that divides both",
          fst_numb, "and", secnd_numb, "=", fst_numb)
else:
  # If the statement is false, then print 1.
    print("The greatest number that divides both",
          fst_numb, "and", secnd_numb, "=", 1)

Output:

The greatest number that divides both 125 and 125 = 125

Method #2: Using If, Else conditional  Statements (User Input)

Approach:

  • Give the first number as user input using the int(input()) function and store it in a variable.
  • Give the second number as user input using the int(input()) function and store it in another variable.
  • Check if the first number is equal to the second number using the if conditional statement.
  • If the statement is true, then print the first number.
  • If the statement is false, then print 1.
  • The Exit of the Program.

Below is the implementation:

# Give the first number as user input using the int(input()) function and store it in a variable.
fst_numb = int(input("Enter some random number = "))
# Give the second number as user input using the int(input()) function and store it in another variable.
secnd_numb = int(input("Enter some random number = "))
# Check if the first number is equal to the second number using the if conditional statement.
if(fst_numb == secnd_numb):
  # If the statement is true, then print the first number.
    print("The greatest number that divides both",
          fst_numb, "and", secnd_numb, "=", fst_numb)
else:
  # If the statement is false, then print 1.
    print("The greatest number that divides both",
          fst_numb, "and", secnd_numb, "=", 1)

Output:

Enter some random number = 5
Enter some random number = 8
The greatest number that divides both 5 and 8 = 1

Explore more instances related to python concepts from Python Programming Examples Guide and get promoted from beginner to professional programmer level in Python Programming Language.