Python program to find HCF of Two Numbers

September 29, 2022

HCF of Two Numbers

Here, in this section we will discuss how to find HCF of two numbers in python. HCF means (Highest Common Factor) also known as GCD (Greatest Common Divisor).

x is called HCF of a & b two conditions :

  • x can completely divide both a & b leaving remainder 0
  • No, other number greater than x can completely divide both a & b
virtual in Python

What's on the Page

  • Method 1: Linear Quest to find HCF
  • Method 2: Euclidean Algorithm: Repeated Subtraction
  • Method 3: Recursive Euclidean Algorithm: Repeated Subtraction
  • Method 4: Modulo Recursive Euclidean Algorithm: Repeated Subtraction
  • Method 5: Handling Negative Numbers in HCF

Method 1 : Linear Quest

Algorithm

  • Initialize HCF = 1
  • Run a loop in the iteration of (i) between [1, min(num1, num2)]
  • Note down the highest number that divides both num1 & num2
  • If i satisfies (num1 % i == 0 and num2 % i == 0) then new value of HCF is i
  • Print value of HCF

Method 1 : Python Code

Run 
num1 = 36
num2 = 60
hcf = 1

for i in range(1, min(num1, num2)):
    if num1 % i == 0 and num2 % i == 0:
        hcf = i
print("Hcf of", num1, "and", num2, "is", hcf)

Output

HCF of 36 and 60 is 12

Lowest Common Multiple (LCM)

 

Binary to Decimal to conversion

Octal to Decimal conversion

Hexadecimal to Decimal conversion

Method 2 : Repeated Subtraction

Algorithm

  • Run a while loop until num1 is not equals to num2
  • If num1>num2 then num1 = num1 – num2
  • Else num2 = num2 – num1
  • After the loop ends both num1 & num2 stores HCF

Method 2 : Python Code

Run 
num1 = 36
num2 = 60
a = num1
b = num2

while num1 != num2:
    if num1 > num2:
        num1 -= num2
    else:
        num2 -= num1

print("Hcf of", a, "and", b, "is", num1)

Output

HCF of 36 and 60 is 12

Method 3 : Repeated Subtraction using Recursion

Algorithm

  • Checked whether any of the input is 0 then return sum of both numbers
  • If both input are equal return any of the two numbers
  • If num1 is greater than the num2 then Recursively call findHCF(num1 – num2, num2)
  • Else Recursively call findHCF(num1, num2-num1)

Method 3 : Python Code

Run 
# Recursive function to return HCF of two number
def findHCF(num1, num2):
    
    # Everything divides 0
    if num1 == 0 or num2 == 0:
        return num1 + num2
    
    # base case
    if num1 == num2:
        return num1
    
    # num1>num2
    if num1 > num2:
        return findHCF(num1 - num2, num2)
    else:
        return findHCF(num1, num2 - num1)


num1 = 36
num2 = 60

print("Hcf of", num1, "and", num2, "is", findHCF(num1, num2))

Output

HCF of 36 and 60 is 12

Method 4 : Repeated Subtraction with Modulo Operator using Recursion

Algorithm

  • If b is equals to 0 return a
  • Else recursively call the function for value b, a%b and return 

Method 4 : Python Code

Run 
# This method improves complexity of repeated subtraction
# By efficient use of modulo operator in euclidean algorithm
def getHCF(a, b):
    return b == 0 and a or getHCF(b, a % b)


num1 = 36
num2 = 60

print("Hcf of", num1, "and", num2, "is", getHCF(num1, num2))
‘

Output

HCF of 36 and 60 is 12

Method 5 : Handling Negative Numbers in HCF

Algorithm

If any of the number is negative then convert it to positive by multiplying it with -1 as according to the proper definition HCF of two numbers can never be negative.

  • If b is equals to 0 return a
  • Else recursively call the function for value b, a%b and return 

Method 5 : Python Code

Run 
# This method improves complexity of repeated subtraction
# By efficient use of modulo operator in euclidean algorithm
def getHCF(a, b):
    return b == 0 and a or getHCF(b, a % b)


num1 = -36
num2 = 60

# if user enters negative number, we just changing it to positive
# By definition HCF is the highest positive number that divides both numbers
# -36 & 60 : HCF = 12 (as highest num that divides both)
# -36 & -60 : HCF = 12 (as highest num that divides both)
num1 >= 0 and num1 or -num1
num2 >= 0 and num2 or -num2

print("Hcf of", num1, "and", num2, "is", getHCF(num1, num2))

Output

HCF of -36 and 60 is 12

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get Prime

15 comments on “Python program to find HCF of Two Numbers”


  • mani

    #HCF
    n,a= 60,36
    l=[]
    b=[]
    for i in range(1,n):
    if n%i==0:
    l.append(i)
    continue
    for j in range(1,a):
    if a%j == 0:
    b.append(j)
    continue
    d = [value for value in l if value in b]
    print(f”HCF of {n} & {a} is {max(d)}”)

1 2