In this section we will see C Program to find the GCD and LCM of two number by Euclid’s algorithm.
GCD – The greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers.
LCM – The least common multiple (LCM) of two numbers is the “smallest non-zero common number” which is a multiple of both the numbers.
For Example :- GCD and LCM of 24 and 40 is 8 and 120
Now let’s see the C Program to find the GCD and LCM of two number by Euclid’s algorithm
C Program
/* Finding GCD and LCM by Euclid's algorithms */
#include <stdio.h>
int gcd(int n1, int n2); /* function prototype */
int main(){
int n1, n2;
printf("Enter two positive integers: ");
scanf("%d%d", &n1, &n2);
printf("\nG.C.D of %d and %d is %d.", n1, n2, gcd(n1,n2));
printf("\nL.C.M of %d and %d is %d\n", n1, n2, (n1*n2)/gcd(n1,n2));
return 0;
}
/* function define as recursion */
int gcd(int n1, int n2){
if (n2 != 0)
return gcd(n2, n1%n2);
else
return n1;
}
Output :-
Conclusion
In this article you have successfully seen how to write a C Program to find the GCD and LCM of two numbers by Euclid’s Method. If you have any doubt then do ask in the comment section.