In this tutorial, you will learn how to write a C program to find GCD of two numbers.
What is GCD?
GCD stands for “Greatest common divisor”. GCD of two integer numbers is the largest integer that can exactly divide both the numbers, exactly means that the remainder is zero. It is also called HCF (highest common factor).
For example: The GCD of 15 and 50 is 5 because 5 is the largest integer number that can exactly divide both the numbers.
Example 1: Find GCD of two numbers using for loop and if statement
In this example, we are taking input from the user. User enters the two integer numbers and the program finds the GCD of entered numbers.
The logic that we are using here is pretty straight forward. We are running a for loop from 1 till the highest number between num1 & num2 and we are dividing both the numbers by the loop counter on every iteration. The "i" value that divides both numbers without leaving a remainder is stored in variable gcd. The last “i” value that exactly divides them is stored as the GCD value of these two numbers.
#include <stdio.h>
int main()
{
int num1, num2, i, gcd;
printf("Enter two integers: ");
//Storing user input into num1 and num2
scanf("%d %d", &num1, &num2);
for(i=1; i <= num1 && i <= num2; ++i)
{
// Checks if the current value of i is
// factor of both the integers num1 & num2
if(num1%i==0 && num2%i==0)
gcd = i;
}
printf("GCD of input numbers %d and %d is: %d", num1, num2, gcd);
return 0;
}Output:
Example 2: GCD of two numbers using while loop
This is another way of finding the GCD of two numbers. In this method, smaller integer between the two is subtracted from the larger integer. The subtraction result is then assigned to the variable that is holding the larger integer. This process goes on in the while loop until both the numbers become equal, at that either of these two variables num1 and num2 can be printed as the output. At the end of the loop both num1 and num2 are equal and contains the GCD value.
#include <stdio.h>
int main()
{
int num1, num2;
printf("Enter two integers: ");
//Storing user input into num1 and num2
scanf("%d %d", &num1, &num2);
while(num1!=num2)
{
if(num1 > num2)
num1 -= num2;
else
num2 -= num1;
}
printf("GCD of two entered integers is: %d",num1);
return 0;
}Output:
