Python Program to Find the gcd of Two Numbers

Introduction

Greatest Common Divisor is the full form of gcd. The greatest common divisor, or GCD, of two numbers, is a value that can exactly divide the two digits and is used to determine the HCF (Highest Common Factor).

The Goal of the Article

1. This post will teach you how to use Python to determine the GCD of two numbers.
2. This article explains the mathematical definition of GCD and shows how to use Python to implement it.
3. We will go over different ways to use
   • gcd() function
   • recursion
   • loops
   • Euclidean Algorithmto compute the GCD of two values.
4. In GCD, managingnegative numbers

Overview of GCD of Two Digits in Python

The mathematical term GCD (Greatest Common Divisor) describes finding the biggest common factor between two values. The greatest positive integer that divides two or more numbers that aren't all zeros is called the GCD.

HCF is another name for GCD (Highest Common factor).

We will demonstrate how to compute the GCD of two digits in this example. Example: The numbers 4 and 10 are both presents. What are 4 and 10's GCD/HCF?

We will talk about the greatest common factor that divides two integers as we review the notion of GCD. The biggest common factor between 4 and 10 is 2.

GCD Calculation with the gcd() Function

The GCD of two digits can be calculated in a number of ways. Utilizing the math module's gcd() function is one of the techniques.

Note: To use the gcd() function to determine the gcd of two numbers. The math module must be imported. Themathmodule will raise an import error if it is not imported.

Syntax: GCD function syntax is as follows:

math.gcd(x, y)

Parameters:

The GCD/HCF for the non-negative integer x "x" must be calculated.

Another non-negative number whose GCD/HCF we must calculate is y 'y'.

The highest common factor, or GCD of x,y, will be returned by the math.gcd() function as a non-negative integer as the return type.

Remark: If we entered both x and y as 0, then. If we use any other data type than int, the function will throw a TypeError and return 0.

For example:

# GCD method can be found in the math module.
import math


# Let's now determine the gcd of two numbers.
a = 50
b = 10
HCF = math.gcd(a,b)


print(f"The GCD of {a} and {b} is {HCF}.")

Output:

The GCD of 50 and 6 is 2.

Recursion is Used to Determine the GCD

The GCD of two numbers will now be calculated using the recursion technique.

For example:

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)


print(gcd(100,3))

Output:

1

Explanation: let’s consider a and b are two variables. Firstly, create a function which is gcd() and passed two arguments. Then in the first condition, if “b” is equal to 0 then return the value of “a” otherwise call gcd() function in which the first argument is "b" and the second argument is "x%y". Finally, print in which call the function with a valid argument.

Calculating the GCD using the Euclidean Algorithm

The most effective approach for calculating the GCD of two digits is the Euclidean Algorithm.

Thus, according to the Euclidean method, we must first store the larger and smaller numbers before dividing the larger number by the lower number and storing the result.

Divide the stored remainder by a smaller integer, then continue the operation until the remaining equals 0.

Example: The numbers 24 and 54 are given. We now divide 54%24 to get 6 and store 6, in accordance with the Euclidean Algorithm. Divide 24%6 now to get 0. We now have no remaining. Consequently, the GCD of 24 and 54 is 6, which is our finding.

Using LOOPS:

For example:

a = 56
b = 108
while b:
a, b = b, a%b
print(a)

Output:

4

Using Recursion:

For example:

def gcd(a, b):
    if a == b or b == 0:
        return a
    if a == 0:
        return b


    else:
        if a>b:
            return gcd(a-b, b)
        else:
            return gcd(a, b-a)


print(gcd(27,90))

Output:

9

Using Loops to Calculate the GCD:

For example:

a = 24
b = 100
n = min(a, b)


HCF = 0
for j in range(1,n+1):
    if a%j == 0 and b%j == 0:
HCF = j


print (HCF)

Output:

4

Explanation:

The HCF (highest common factor) of two digits always resides between 1 and the minimum of two numbers, which is why n stores the least value of a and b values. The lowest value of two digits can thus be stored in n.

Due to the for loop's exclusive use of n+1, it will execute for n+1 times. Verify that both values may be divided by the present value at each step. If the present value of the for loop divides both values, the present value of the for loop will be HCF. The HCF (highest common factor) of a and b will be returned by our software following the successful completion of the for a loop.

In GCD, managing negative numbers:

Since the GCD of two integers can never be negative, if any of the numbers are negative, change them to positive by multiplying them by -1.

Return and if b is equal to 0.

Otherwise, call the method for value b, a%b, recursively, and return.

Code:

# This technique raises the bar for repeated subtraction.
# Use the Euclidean algorithm's modulo operator effectively
def get_GCD(a, b):
    return b == 0 and a or get_GCD(b, a % b)




num_1 = -42
num_2 = 50


# Changing a negative number to a positive if the user enters one
# GCD is the largest real integer that divides both numbers, according to its definition.
# -42&50: GCD = 12 (as greatest num that divides both)
# -42& -50: GCD = 12 (as greatest num that divides both)
num_1 >= 0 and num_1 or -num_1
num_2 >= 0 and num_2 or -num_2


print("GCD of", num_1, "and", num_2, "is", get_GCD(num_1, num_2))

Output:

GCD of -42 and 50 is 2

Conclusion

A mathematical instrument called GCD provides information on the greatest common factor between two numbers.

To determine the gcd of two numbers, we can use the developed gcd() method, which is accessible in the math module.

One of the most used algorithms, the Euclidean Algorithm, can be used to determine the GCD.