LCM Algorithm

The LCM Algorithm, or Least Common Multiple Algorithm, is a mathematical technique used to find the smallest multiple that is evenly divisible by two or more numbers, known as the least common multiple (LCM). LCM is an essential operation in various mathematical applications, particularly in number theory, fractions, and solving problems involving the synchronization of events. The LCM of two numbers is determined by finding the smallest multiple that is a common multiple of both numbers, which means that the LCM will be divisible by each of these numbers without a remainder. The concept can be extended to find the LCM of multiple numbers as well. There are several methods to find the LCM of two or more numbers, including prime factorization, listing multiples, and division methods. One popular and efficient method is using the Euclidean algorithm for finding the greatest common divisor (GCD) and then applying the formula LCM(a, b) = |a * b| / GCD(a, b). This method ensures a lower computational complexity, making it suitable for larger numbers and programming applications. In the context of fractions, the LCM is used to find the least common denominator (LCD), making it easier to add or subtract fractions with different denominators. Overall, the LCM Algorithm is a fundamental mathematical tool with a wide range of applications in various disciplines.
// C program to find LCM of two numbers  
/*
	suppose we have two numbers a and b.
	Property: Since product of LCM and GCD of two numbers are equal to product of that number itself.
	i.e, LCM(a,b)*GCD(a,b)=a*b.
	So,here we first find the GCD of two numbers and using above property we find LCM of that two numbers.
*/
#include <stdio.h>  
  
// Recursive function to return gcd of a and b  
int gcd(int a, int b)  
{  
    if (a == 0) 
        return b;  
    return gcd(b % a, a);  
}  
  
// Function to return LCM of two numbers  
int lcm(int a, int b)  
{  
    return (a*b)/gcd(a, b);  
}  
  
// Driver program  
int main()  
{  
    int a,b;
    printf("Enter two numbers to find their LCM \n");
    scanf("%d%d",&a,&b);
    printf("LCM of %d and %d is %d ", a, b, lcm(a, b));  
    return 0;  
}  
/*
Test Case1:
a=15,b=20
LCM(a,b)=60
Test Case2:
a=12,b=18
LCM(a,b)=36
*/

LANGUAGE:

DARK MODE: