Creating an HCF Finder Using Python

ECX 30 Days of Code and Design

Day 11

Euclid's Algorithm (GCD)

The GCD (Greatest Common divisor) of two numbers is the largest number by which both are divisible. E.g.; gcd(42, 18) is 6, since 6 is the highest common factor (HCF—same thing as GCD) of 42 and 18.

Task

Write a program that asks the user for two numbers and computes their GCD using Euclid's algorithm. The process is described below:

First, compute the remainder of dividing the larger number by the smaller one.
Next, replace the larger number with the smaller number, and the smaller number with the remainder.
Repeat this process until the smaller number equals zero. The GCD is the last value of the larger number. See full details.

My Approach

This is the full code. I would explain it in bits throughout this article.

# Greatest common divisor function
def euclidean(big_num, small_num):
    # Make the first argument the larger of both arguments
    if small_num > big_num:
        temp = big_num
        big_num = small_num
        small_num = temp

    # Keep dividing until the remainder is 0
    while small_num > 0:
        # Dummy variable to hold the value of the smallest number
        remainder = small_num
        small_num = big_num % small_num
        big_num = remainder

    print('The greatest common divisor is', big_num)


# Ask users for input
try:
    print(' Greatest Common Divisor Finder '.center(40, '*'))
    print('Enter two positive integer')
    first_num = int(input('First number: '))
    second_num = int(input('Second number: '))

    # Function call
    euclidean(first_num, second_num)
except ValueError:
    print('Invalid input! Input only integers.')

First, we define the function, euclidean(), which is to take two integer arguments. We then check if the second argument is larger than the first. If it is, we switch them (i.e., the first argument is made to take the higher value).

def euclidean(big_num, small_num):
    # Make the first argument the larger of both arguments
    if small_num > big_num:
        temp = big_num
        big_num = small_num
        small_num = temp

Next, we would divide the bigger number by the smaller number, if we get a remainder of zero, our HCF is the value of the smaller number used in the division, else we would equate the smaller number to the value of the remainder while the bigger number would take the value of the smaller number, and we divide again, we keep dividing until we get a remainder of zero. If there exists no HCF between both arguments, one (1) is printed to the screen.

    # Keep dividing until the remainder is 0
    while small_num > 0:
        # Dummy variable to hold the value of the smallest number
        remainder = small_num
        small_num = big_num % small_num
        big_num = remainder

Finally, we ask for the user’s input and call the euclidean() function, wrapping them in a try except block to handle value error.

# Ask users for input
try:
    print(' Greatest Common Divisor Finder '.center(40, '*'))
    print('Enter two positive integer')
    first_num = int(input('First number: '))
    second_num = int(input('Second number: '))

    # Function call
    euclidean(first_num, second_num)
except ValueError:
    print('Invalid input! Input only integers.')

Run code on Replit

The Coding Process