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.


Post Contents

  1. GCD in C
  2. GCD using recursion
  3. GCD using while loop
  4. GCD of n numbers
  5. LCM 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;
	}
}

Labels:











Labels