C program to find GCD of two integers

      GCD (Greatest Common Divisor) or HCF (Highest Common Factor) of two numbers is the largest number that divides both of them. For example, GCD of 20 and 28 is 4 and GCD of 98 and 56 is 14. This program checks for a number that perfectly divides the given two numbers starting from 2. If it finds a number then that number will be the GCD of two numbers otherwise 1 is the GCD of two numbers as 1 divides all the numbers.

gcd of two numbers program in c



Source Code :

#include<stdio.h>
int GCD(int,int);
int main(void)
{
	int nOne, nTwo, n;
	printf("\n Enter two numbers: ");
	scanf("%d %d", &nOne, &nTwo);         // Step 1 
	n=GCD(nOne,nTwo);                    // Step 2
	printf("\n GCD of %d and %d is %d \n",	nOne,nTwo,n); //Step 4
	return 0;
}
int GCD(int x,int y)
{
	int result=1, k=2;
	while(k<=x && k<=y)               //Step3
	{
	   if(x%k==0 && y%k == 0)      //Step3(i)
	       result=k;
	   k++;                      //Step3(ii)
	}
	return result;
}


edit-code-image

Sample Test cases:

1.   Enter two numbers: 3 4
     GCD of 3 and 4 is 1

2.   Enter two numbers: 5 25
     GCD of 5 and 25 is 5

3.   Enter two numbers: 0 1
     GCD of 0 and 1 is 1

Explanation for GCD of two numbers:

Step 1 : The two numbers are read from the user using scanf() function.

Step 2 : The GCD function is called from the main program with two numbers as arguments.

Step 3 : The while loop is iterated until ‘k'(i.e., GCD) is less than or equal to any of the given two numbers.

Step 3(i) : This step checks whether ‘k’ divides the two numbers perfectly or not. If it divides, then that number will be the GCD of two numbers.

Step 3(ii) : Otherwise the while loop is moved to next natural number.

Step 4 : Finally the GCD of two numbers is printed on the output screen.

More Insights:

More Information.

2. Finding GCD

Explore C Programs:C Programs