C Program to Find Gcd of Two Numbers

gcd program in C. C program to find gcd of two numbers in C: The following C program finds the gcd of two integers (numbers) using non-recursive function i.e. without using recursion. The HCF or GCD of two numbers is the largest number that can exactly divide both the numbers without leaving any remainder.

C program to find gcd of two numbers

C program to find gcd of two numbers

/* GCD of two numbers in C */

#include<stdio.h>

int main()
{
	int i, gcd, num1, num2;

	printf("\n Enter two numbers:- ");
	scanf(" %d %d", &num1, &num2);

	for(i=1; i <= num1 && i <= num2; ++i)
	{
		if(num1%i==0 && num2%i==0)
			gcd = i;
	}

	printf("\n G.C.D of %d and %d is %d", num1, num2, gcd);

	return 0;
}

/* Output of above code:-

 Enter two numbers:- 10 20
 G.C.D of 10 and 20 is 10

*/

C program to find gcd of two numbers using recursion

/* C program to find gcd of two numbers using recursive function */

#include<stdio.h>

int calculate_GCD(int num1, int num2)
{
	if (num2 != 0)
		return calculate_GCD(num2, num1%num2);
	else 
		return num1;
}

int main()
{
   int num1, num2;

   printf("\n Enter two integers:- ");
   scanf("%d %d", &num1, &num2);

   printf("\n HCF or GCD of %d and %d is %d.", num1, num2, calculate_GCD(num1, num2));

   return 0;
}

/* Output of above code:-

 Enter two integers:- 5 10
 HCF or GCD of 5 and 10 is 5.

*/

C program to find gcd of two numbers using while loop

/* GCD of two numbers in C */

#include<stdio.h>

int main()
{
	int i=1, gcd, num1, num2;

	printf("\n Enter two numbers:- ");
	scanf(" %d %d", &num1, &num2);

	while(i <= num1 && i <= num2;)
	{
		++i;
		if(num1%i==0 && num2%i==0)
			gcd = i;
	}

	printf("\n G.C.D of %d and %d is %d", num1, num2, gcd);

	return 0;
}

/* Output of above code:-

 Enter two numbers:- 10 20
 G.C.D of 10 and 20 is 10

*/

gcd of n numbers in C

/* C program to find GCD of n numbers using function*/

#include<stdio.h>

int calculate_GCD(int num1, int num2)
{
	if (num2 != 0)
		return calculate_GCD(num2, num1%num2);
	else 
		return num1;
}

int main()
{ 
	int i,j,size,a[100],hcf; 
    
	printf("Enter how many numbers :"); 
	scanf("%d",&size); 
    
	for(i=0;i<size;i++) 
	{ 
		printf("Enter a Number :");
		scanf("%d",& a[i]); 
	} 

	for(i=0;i<size-1;i++) 
	{ 
		hcf=calculate_GCD(a[i],a[i+1]);
		a[i+1]=hcf; 
	}

	printf("\n GCD of %d and %d is %d", a[i], a[i+1], hcf); 
                   
}

/* Output of above code:-

Enter how many numbers:- 5
Enter a Number : 5
Enter a Number : 10
Enter a Number : 15
Enter a Number : 40
Enter a Number : 100
GCD of input numbers is 5

*/
For most of the times we are asked calculate LCM (Lowest Common Multiple) along with the GCD. The following function calculates the LCM of two numbers num1, and num2.

C programming function to find LCM of two numbers

/* function to find LCM of two numbers in C*/

int find_lcm(int num1, int num2)
{
	int n;

	n = (num1 > num2) ? num1 : num2;

	while (1)
	{
		if(n%num1==0 && n%num2==0)
			return n;
	++n;
	}
}