How to find Greatest Common Divisor ( GCD ) of two numbers in C

Greatest Common Divisor ( GCD ) or Highest Common Factor ( HCF ) or Greatest Common Factor ( GCF ) of two numbers is the greatest positive integer that perfectly divides both the numbers. You can find more about GCD of two numbers on Wikipedia. In this tutorial, I will show you a very simple way to find GCD of two numbers using C language.

You can also find GCD of two numbers using Euclid’s Method in C language which is explained here.

Algorithm:

1. Let a and b be the two numbers whose GCD you want to find.
2. Let temp be any temporary number, initially set to the bigger number among a and b.
3. Check whether temp perfectly divides both a and b or not.
4. If it is, then temp is the GCD of a and b, otherwise move to step 5.
5. Increment the value of temp and move to step 3.

Instructions:

1. Use only the following header file in C program.
   

   #include <stdio.h>

2. In main, ask the user to input two numbers whose GCD he/she wants to find.
   

   int a,b, temp;
   printf("Enter two numbers whose GCD you want to find : ");
   scanf("%d%d", &a, &b);

3. Find the GCD of these two numbers a and b using the user defined function findGCD which will return GCD of these two number and print its value.
   

   temp = findGCD(a, b);
   printf("GCD of %d and %d is %d", a, b, temp);

4. In findGCD function, define a temporary variable gcd and assign it value of the smaller number among a and b(i.e. if a > b then gcd = b, otherwise gcd = a). No using a while loop which will run untill gcd perfectly divides both a and b, and increment the value of gcd in this loop. And finally return the value of variable gcd.
   

   int findGCD(int a, int b)
   {
       int gcd = a > b ? b : a;
       while(a % gcd != 0 || b % gcd != 0)
       {
           gcd--;
       }
       return gcd;
   }

Here are some screenshots of sample programs.

GCD of two numbers using C

GCD of two numbers using C

You can download the sample code from here.