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 C.

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.c. Open it and enter the following, or you can download the source code as a zip or clone/download from Github.

Source Code Links

ZIP File
GitHub

euclideanalgorithm.c

#include<stdio.h>
#include<stdlib.h>

//--------------------------------------------------------
// FUNCTION PROTOTYPES
//--------------------------------------------------------
int EuclideanHCF(int a, int b);

//--------------------------------------------------------
// FUNCTION main
//--------------------------------------------------------
int main(int argc, char* argv[])
{
    puts("-----------------------");
    puts("| codedrome.com       |");
    puts("| Euclidean Algorithm |");
    puts("-----------------------\n");

    int avalues[] = {55, 27, 3, 14, 500, 30};
    int bvalues[] = {5, 45, 15, 49, 12, 18};

    for(int i = 0; i < 6; i++)
    {
        int hcf = EuclideanHCF(avalues[i], bvalues[i]);

        printf("HCF of %d and %d = %d\n", avalues[i], bvalues[i], hcf);

        printf("%d / %d = %d\n", avalues[i], hcf, avalues[i] / hcf);

        printf("%d / %d = %d\n\n", bvalues[i], hcf, bvalues[i] / hcf);
    }

    return EXIT_SUCCESS;
}

//--------------------------------------------------------
// FUNCTION EuclideanHCF
//--------------------------------------------------------
int EuclideanHCF(int a, int b)
{
    int temp;

    while(b != 0)
    {
        temp = b;

        b = a % b;

        a = temp;
    }

    return a;
}

The main function creates two arrays of integers forming pairs of numbers to apply the algorithm to. It then iterates the arrays, 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.

We can now compile and run the program by running the following in the terminal.

Compile and Run

gcc euclideanalgorithm.c -std=c11 -lm -o euclideanalgorithm

./euclideanalgorithm

The program output is

Program Output

-----------------------
| codedrome.com       |
| Euclidean 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