GCD of Two Numbers in C Programming

Introduction

In this post, I will teach you to write a program to find GCD of Two Numbers in C programming. The GCD stands for Greatest Common Divisor. GCD can also be called HCF i.e. Highest Common Factor.

Also Read: LCM of Two Numbers in C Programming

Before writing a program in c to find GCD of two numbers, let’s know, what is exactly GCD?

GCD of Two Numbers

As I said, GCD is nothing but Greatest Common Divisor. Suppose, we have two numbers, say a and b, then we need to find the greatest number which divides both a and b. How can we come to know this?

Let’s understand with some examples.

GCD of 6 and 8

Here, we have two numbers i.e. 6 and 8. So, we need to find the gcd of both numbers.

First, we need to find the factors of both these numbers. What is the meaning of factors? Factors are those numbers that divide that number completely.

I am saying here completely that means remainder is 0. So, the factors of 6 are 2, 3 and 6 and that of 8 are 2, 4 and 8. Just compare factors of both the numbers and find the common factors. So, here is the only factor which is common and that is 2. So, 2 is the gcd of 6 and 8. In other words, we can say 2 can divide both, 6 and 8.

Also Read: Switch Case in C Programming

Always remember, 1 is the factor of all the numbers. Therefore, I have not written it here because by default, 1 is there.

Look at another example.

GCD of 20 and 30

Again, use the same technique. Factors of 20 are 2, 4, 5, 10 and the factors of 30 are 2, 3, 5, 6, 10, 15. So, 2, 5 and 10 are the common factors. But we need greatest factor. Therefore, our answer is 10. So, we can say, 10 is the GCD of 20 and 30.

GCD of 5 and 9

Factors of 5 are 1, 5 and that 9 are 1, 9. Only 1 is a common factor. Therefore, GCD of 5 and 9 are 1.

I think, these are enough examples to understand how to find GCD of two numbers and we will use this to write a program in c.

Logic to find GCD of Two Numbers in C Programming

In the above examples, I have explained a very simple method to find GCD of two numbers. But, we have to write a c program to find the GCD of two numbers and this simple logic won’t help. So, I have very good logic to solve this problem.

Also Read: The while loop in C Programming

Suppose, we need to find GCD of 6 and 8. Just follow the following steps:

Divide greater number by smaller number and find the remainder.
If the remainder is 0, then the GCD is a smaller number. But if the remainder is not 0, then repeat step 1. But before that, we need to change the value of greater and smaller.
Just consider our above example, here, a greater number is 8 and the smaller number is 6. Now divide 8 by 6, then the remainder will be 2. So, what to do next?
Assign the value of the variable which contains a smaller number to the variable which contains a greater number and then, assign the value of remainder to the variable which contains a smaller number. This time, the greater number is 6 and a smaller number is 2.
Now, I repeating step 1 here. That means divide greater number by smaller number and this time, the remainder is 0.
Therefore, the smallest number i.e. 2 is the GCD of 6 and 8.
You have repeat steps 1 and 4 until you get remainder is equal to 0.

I hope, you have understood this logic. Now, we will use this logic to write a program in c to find the GCD of two numbers.

C Program to find GCD of two Numbers.

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

int main()
{
    int n1,n2,greater,smaller,n3;
    printf("Enter two numbers\n");
    scanf("%d%d",&n1,&n2);
    if(n1>n2)
    {
        greater=n1;
        smaller=n2;
    }
    else
    {
        greater=n2;
        smaller=n1;
    }
    while(1)
    {
        n3=greater%smaller;
        if(n3==0)
        {
            printf("GCD of %d and %d = %d",n1,n2,smaller);
            break;
        }
        greater=smaller;
        smaller=n3;
    }
    return 0;
}

When you compile and run the above c program, you will be able to find GCD of two numbers. Now, see the following output.

Output

Enter two numbers
6
8
GCD of 6 and 8 is 2

I don’t think, I need to explain this program. Because, if you understood the logic, then I can guarantee that you have understood this program.

Also Read: C Program to Find the Sum of Cubes of Elements in an Array

If you know the Hindi language, then I have made a video on this topic. So, I am sharing that video here and I hope you will like that video too.

Thanks for reading and watching.

GCD of Two Numbers in C