PYTHON: Exercise

Euclid's greatest common divisor algorithm

In mathematics, the Euclidean algorithm, or Euclid's algorithm, is an efficient method to find out the largest number that will divide into both of them without leaving a remainder - in other words, it works out the greatest common divisor (GCD) of two integers (whole numbers). It can be used to reduce fractions to their simplest form, and is a part of many other number-theoretic and cryptographic calculations.

It is named after the ancient Greek mathematician Euclid, who first described it in his Elements (c. 300 BC).

It is an example of an algorithm - a step-by-step procedure for performing a calculation according to well-defined rules - and is one of the oldest algorithms in common use.

It is therefore ideal for turning into a computer program!

The Euclidean algorithm proceeds in a series of steps such that the output of each step is used as an input for the next one.

Let k be an integer that counts the steps of the algorithm, starting with zero and q be the quotient.

At step k, r_k will be zero and q_k will be the GCD.

 

You take two positive whole numbers.

You divide the larger one by the smaller one and find the remainder.

You then divide the smaller number by that remainder and find the remainder for that, carrying on this method until there is a zero remainder.

For example:

Find the greatest common divisor of a = 1071 and b = 462.

First we find the 'difference' between them:

a - b = 1071 - 462 = 609

The remainder is still larger than b - so we can actually deduct b twice and q₀ = 2

609 - 462 = 147 - leaving us with a remainder of 147, meaning that r₀ = 147

We now find out how many times we can divide B by this new remainder number:

462 - 147 = 315

315 - 147 = 168

168 - 147 = 21

It turns out we can deduct it three times and be left with a remainder r₁= 21 and q₁ = 3.

We now have to repeat the process with 21 as our quotient and 147 as our initial value

147 - 21 = 126

126 - 21 = 105

105 - 21 = 84

84 - 21 = 63

63 - 21 = 42

42 - 21 = 21

21 - 21 = 0

This time q₂ = 7 and we have the desired zero remainder, so 21 is the greatest common divisor.

 

Now to write the code:

#Explain to the user what we are going to do

print("This program will determine the greatest common divisor (GCD) of two integers")

print("using the Euclidean algorithm")

print("***************************************")

#Ask user to input two different whole numbers (not zero)

number1=input("Input a number greater than zero")

print("***************************************")

number2=input("Input another number greater than zero and different to your first choice") print("***************************************")

#Convert the strings to integers

n=int(number1)

m=int(number2)

#Deduct the smaller number from the larger one then make the remainder the new number - until the remainder is smaller than the other number - you then do the same process to that number....

while n!= m: (this means while n and m are not the same value)

if n>m:

n=n-m

else:

m=m-n

#The GDC could be either m or n as they are both the same - that is why we came out of the while loop!

print ("Their greatest common divisor is", n)