Using euclids algorithm write a c program to calculate GCD and LCM




This C program uses Euclid's algorithm to find the gcd and lcm of the given input.

Euclid algorithm says greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number.

Here in this c program we first check which is the biggest number and assigns it as numerator other as denominator, then uses mod operator inside a while loop to find GCD.

After finding the gcd For LCM we have a well defined formula "lcm = num1 * num2 / gcd".

===================================================================
#include <stdio.h>
 
#include <conio.h>
 
void main()
 
{
 
    int  num1, num2, gcd, lcm, remainder, numerator, denominator;   /* declares the variables gcd, lcm, remainder etc as integers  */ 
 
    clrscr();
 
    printf("Enter two numbers\n");
 
    scanf("%d %d", &num1,&num2);                     /*  accepts two numbers from the user  */
 
    if (num1 > num2) 
 
    {
       numerator = num1;
 
       denominator = num2;
 
    }
 
    else
                                             /* checks and assigns the value for numerator and denominator  */
 
    {
 
       numerator = num2;
 
       denominator = num1;
 
    }
 
    remainder = num1 % num2;                         /* use mod operator to find the remainder  */
 
    while(remainder !=0)
 
    {
 
	 numerator   = denominator;                  /* using Euclid's algorithm to interchange the values of variables  */
 
	 denominator = remainder;
 
	 remainder   = numerator % denominator;
 
    }
 
    gcd = denominator;
 
    lcm = num1 * num2 / gcd;
 
    printf("GCD of %d and %d = %d \n", num1,num2,gcd);   /* after gcd we find out the value of lcm */
 
    printf("LCM of %d and %d = %d \n", num1,num2,lcm);
 
}		/* End of main() */
==================================================================
OUTPUT of C program to find the GCD and LCM of two integers
==================================================================
RUN 1
Enter two numbers
5
15
GCD of 5 and 15 = 5
LCM of 5 and 15 = 15