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