Algorithm

  1. Input: Accept two numbers, let's call them num1 and num2.

  2. Initialization: Set a to the larger of the two numbers (num1 and num2), and b to the smaller one.

    Euclid's Algorithm:

    • Repeat the following steps until b becomes zero:
      • Set a temporary variable temp to the value of b.
      • Set b to the remainder when a is divided by b.
      • Set a to the value of temp.
      • Output: The value of a is the HCF/GCD of the original two numbers.

 

Code Examples

#1 Code Example- Linear Quest

Code - Python Programming

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)
Copy The Code & Try With Live Editor

Output

x
–
+
cmd
HCF of 36 and 60 is 12

#2 Code Example- Repeated Subtraction

Code - Python Programming

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)
Copy The Code & Try With Live Editor

Output

x
–
+
cmd
HCF of 36 and 60 is 12

#3 Code Example- Repeated Subtraction using Recursion

Code - Python Programming

# 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))
Copy The Code & Try With Live Editor

Output

x
–
+
cmd
HCF of 36 and 60 is 12

#4 Code Example- Repeated Subtraction with Modulo Operator

Code - Python Programming

# 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))
Copy The Code & Try With Live Editor

Output

x
–
+
cmd
HCF of 36 and 60 is 12

#5 Code Example- Handling Negative Numbers in HCF

Code - Python Programming

# 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))
Copy The Code & Try With Live Editor

Output

x
–
+
cmd
HCF of -36 and 60 is 12
Advertisements

Demonstration

Python Programin g Example to Find HCF or GCD-DevsEnv