The Euclidean Algorithm is a simple method for finding the highest common factor or HCF (also known as greatest common divisor or GCD) of two positive integers. This is an implementation of the algorithm in Python.

Wikipedia has a comprehensive article on the topic here so let's get straight to the coding by creating a new folder, and within it creating an empty file called euclideanalgorithm.py. Open it and enter the following, or you can download the source code as a zip or clone/download the Github repo if you prefer.

euclideanalgorithm.py

Source Code Links

ZIP File
GitHub

def main():

    """
    The Euclidean Algorithm finds the highest common factor
    of two numbers. Here we create lists of number pairs and
    run the algorithm on it, printing out the result and the numbers
    divided by the HCF.
    """

    print("----------------------")
    print("| codedrome.com      |")
    print("| Euclid's Algorithm |")
    print("----------------------\n")

    avalues = (55, 27, 3, 14, 500, 30)
    bvalues = (5, 45, 15, 49, 12, 18)

    for i in range(0, 6):

        hcf = EuclideanHCF(avalues[i], bvalues[i])

        print("HCF of {} and {} = {}".format(avalues[i], bvalues[i], hcf))
        print("{} / {} = {:.0f}".format(avalues[i], hcf, avalues[i] / hcf))
        print("{} / {} = {:.0f}\n".format(bvalues[i], hcf, bvalues[i] / hcf))


def EuclideanHCF(a, b):

    """
    A simple implementation of a simple algorithm.
    """

    while(b != 0):
        temp = b
        b = a % b
        a = temp

    return a


main()

The main function creates two lists containing pairs of numbers to apply the algorithm to. It then iterates the lists, calling the algorithm and printing the result. It also prints each number divided by the HCF as a demonstration or proof.

The EuclideanHCF function replaces b with the modulo (remainder) of a and b, and replaces a with the previous value of b. This is repeated until b reaches 0, leaving a as the required HCF. This is an implementation of the Euclidean division variant of the algorithm which is more efficient than the subtraction method.

Run the program with this command in the terminal:

Running the Program

python3.7 euclideanalgorithm.py

The program output is

Program Output

----------------------
| codedrome.com      |
| Euclid's Algorithm |
----------------------

HCF of 55 and 5 = 5
55 / 5 = 11
5 / 5 = 1

HCF of 27 and 45 = 9
27 / 9 = 3
45 / 9 = 5

HCF of 3 and 15 = 3
3 / 3 = 1
15 / 3 = 5

HCF of 14 and 49 = 7
14 / 7 = 2
49 / 7 = 7

HCF of 500 and 12 = 4
500 / 4 = 125
12 / 4 = 3

HCF of 30 and 18 = 6
30 / 6 = 5
18 / 6 = 3