Source Code: Using Loops
The HCF or Highest Common Factor of two numbers is the largest positive integer that divides both the numbers perfectly. HCH is also referred to as GCD or Greatest Common Divisor. Let us learn gcd python here.
For example, the HCF of 9 and 33 is 3.
The GCD Python code will determine the greatest number that perfectly divides the two input numbers. There are various methods to find the HCF of two numbers that can be used. One should know how to work with functions in Python and the concept of recursion to understand the working of the source code.
The program given below calculates the HCF of the two numbers entered by the user with the help of loops. WHILE and FOR loops can be used. Also, to check which of the two numbers entered is smaller, the if…else condition will be used as well.
def calc_hcf (x, y)
if x > y:
smaller = y
else:
smaller = x
for i in range (1, smaller +1)
if ((x % i == 0) and (y % I == 0)):
hcf = i
return hcf
num1 = int (input (“Enter the first number as required: “))
num2 = int (input (“Enter the second number to find the HCF:”))
print (“The HCF of the two numbers entered is, calc_hcf (num1, num2))
Here, the function created for HCF requires two parameters. These are the two numbers that need to be passed so that their HCF can be calculated. The function returns the HCF after complete calculation.
The function first finds which of the two numbers is smaller. In each iteration, both the numbers are divided by all the numbers lying between 1 and the smaller number. If the condition is satisfied, that is, a number is found that divides both the entered numbers perfectly, then it returns as HCF.
Euclidean Algorithm
As per the Euclidean Algorithm, it is found that the HCF of two numbers will also perfectly divide the difference between the two numbers. For the GCD Python code, we first divide the greater number by a smaller number. The smaller number is then divided by the remainder. The process is repeated until the remainder obtained is equal to zero.
Source Code: Using the Euclidean Algorithm
The code to find the GCD of two numbers through the Euclidean Algorithm is provided below.
def calc_hcf (x, y):
while (y):
x, y = y, x % y
return x
hcf = calc_hcf (360, 780)
print (“The HCF of the two numbers is: “, hcf)
Here, the function that is created to calculate the GCD Python first finds the smaller number. Once found, it will then proceed to find the remainder of the greater number divided by the smaller number. The value of a smaller number will be swapped with a larger number and the value of the remainder will be swapped with the smaller number. The process will continue till there is some value of y.
In Python, an in-built function to calculate GCD also exists. With this function, the HCF or GCD of any two positive integers can be calculated without needing any additional code. The function will require two numbers as parameters. These are the numbers for which the GCD needs to be calculated.
The source code for such a program that uses the gcd () function is provided below. Note that the math module will need to be imported to use the gcd () function.
import math
print (“The GCD of the given two numbers is: “)
print (math.gcd (800, 6500))
All the source codes that are given here will provide the same result for any two numbers. Any of these can be used as per the choice of the user.
Questions
How is the GCD calculated in Python?
The GCD Python program can be calculated through various methods. One of them is using the FOR or WHILE loop. Other methods include recursion of the function so that the need of loop is deleted, using the Euclidean Algorithm, and using the in-built gcd () function that is provided in the MATH module of Python.
What is GCD in Python?
GCD or HCF in Python is the largest positive integer that perfectly divides the given two numbers such that the remainder after the division is zero.
Is there a GCD function in Python?
Yes, in Python an in-built GCD function is present. The gcd () function needs two parameters. These parameters are the two numbers whose GCD needs to be calculated.
How do you find the GCD of a list in Python?
The GCD of a list in Python can be calculated by entering each number present in the list in the parameters for the gcd () function. A FOR loop will need to be coded as well so that each element of the list is passed in the parameter of the gcd () function.
Leave a Reply