C program to implement Euclidean algorithm

Problem

Implement Euclidean algorithm to find the greatest common divisor (GCD) and least common multiple (LCM) of two integers and convert the results Output together with the given integer.

Solution

The solution to implement Euclidean algorithm to find the greatest common divisor (GCD) and least common multiple (LCM) of two integers is as follows-

Find GCD The logic with LCM is as follows -

if(firstno*secondno!=0){
   gcd=gcd_rec(firstno,secondno);
   printf("</p><p>The GCD of %d and %d is %d</p><p>",firstno,secondno,gcd);
   printf("</p><p>The LCM of %d and %d is %d</p><p>",firstno,secondno,(firstno*secondno)/gcd);
}

The function called is as follows-

int gcd_rec(int x, int y){
   if (y == 0)
      return x;
   return gcd_rec(y, x % y);
}

Program

The following is a C program for implementing the Euclidean algorithm to Find the greatest common divisor (GCD) and least common multiple (LCM) of two integers -

Live demonstration

#include<stdio.h>
int gcd_rec(int,int);
void main(){
   int firstno,secondno,gcd;
   printf("Enter the two no.s to find GCD and LCM:");
   scanf("%d%d",&firstno,&secondno);
   if(firstno*secondno!=0){
      gcd=gcd_rec(firstno,secondno);
      printf("</p><p>The GCD of %d and %d is %d</p><p>",firstno,secondno,gcd);
      printf("</p><p>The LCM of %d and %d is %d</p><p>",firstno,secondno,(firstno*secondno)/gcd);
   }
   else
      printf("One of the entered no. is zero:Quitting</p><p>");
   }
   /*Function for Euclid&#39;s Procedure*/
   int gcd_rec(int x, int y){
   if (y == 0)
      return x;
   return gcd_rec(y, x % y);
}

Output

When the above program is executed, it will produces the following results -

Enter the two no.s to find GCD and LCM:4 8

The GCD of 4 and 8 is 4

The LCM of 4 and 8 is 8

The above is the detailed content of C program to implement Euclidean algorithm. For more information, please follow other related articles on the PHP Chinese website!