Simple C Program for GCD (GCF) of two Numbers

Here is a simple C program to find the GCD of two numbers. The program makes use of Euclid's GCD algorithm.

C Program to Find GCD

Let's start off with a definition of GCD. GCD stands for Greatest Common Divisor. GCD of two numbers is the greatest number that completely divides both numbers.
There are numerous algorithms to find the GCD (or GCF) of two numbers. The most efficient of these is Euclid's GCD Algorithm, formulated by Greek Mathematician Euclid.

Euclid's GCD Algorithm

Euclid's GCD Algorithm can seem confusing at first sight but you'll definitely appreciate its simplicity and effectiveness once you get it. The beauty of Euclid's Algorithm is how it gives the GCD in least possible steps.
Euclid's Algorithm makes use of successive division of two numbers. The process can be broken down into distinct steps as follows.

1. Divide the larger number by the smaller number.
2. Now divide the divisor (from the previous division) with the remainder.
3. Continue the process until the remainder becomes equal.

For example, we take two numbers 12 and 18.
The first division takes 18 as the dividend and 12 as the divisor which gives 6 as the remainder. The second division makes 12 the dividend and 6 the divisor. The remainder comes out to be zero in the last division, which marks the end of the process. Now, 6 is the GCD.
Let's implement this idea with a simple C program using loops.

#include <stdio.h>
void smallgreat(int,int,int *,int *);
int main(void)
{
    int num1, num2, small,rem = 1, great;
    printf("Enter first number: ");
    scanf("%d",&num1);
    printf("Enter Second Number: ");
    scanf("%d",&num2);
    smallgreat(num1,num2, &small, &great);
    while(rem != 0)
    {
        rem = great % small;
        great = small;
        small = rem;
    }
    printf("\nGCD = %d", great);
    return 0;
}
void smallgreat(int a, int b, int *small, int *great)
{
    if(a>b)
    {
        *small = b;
        *great = a;
    }
    else
    {
        *small = a;
        *great = b;
    }
}

Our program consists of two functions. The function smallgreat() gives us the smaller and greater of the two numbers. Our program execution starts in the function main(). The two numbers are obtained from user using scanf(). We define for int variables num1, num2, small, great and rem. The user entered numbers are stored in num1 and num2. Variable small is used to keep the smaller of the two numbers, similarly great is used to keep the greater. The variable rem stores the remainder of divisions.
The core component of this program is the while loop which performs the successive divisions. The loop keeps performing the divisions until the rem becomes zero. Once the loop terminates,
Voila!!! you have your GCD.