The least common multiple of positive integers is a number, which is is a multiple of all given integers and is minimal. We denote the least common multiple of numbers
as
Computing the least common multiple
Prime factorization
The easiest way to get the least common multiple of numbers is to express them as a product of prime numbers (factorize them). If we multiply together all prime numbers used in these products in their highest power, we get the least common multiple.
Example
Find the least common multiple of 6, 8, 15.
Example
Find the least common multiple of 140 and 17.
Example
Find the least common multiple of 288 and 420?
We can illustrate the above mentioned approach using the Venn's diagram. In the Venn's diagram the numbers 288 and 420 are represented as a sets of their prime factors. The factors, which they share in common, are placed in the intersection of these sets. Hence the diagram shows all prime factors of numbers 288 and 420 in their highest power – we can find their least common multiple by simply multiplying all displayed prime factors together.
Euclidean algorithm
Much more effective way to get the least common multiple of two numbers is to multiply them and divide the result by their greatest common divisor. The greatest common divisor may be computed by the Euclidean algorithm, which is very fast, because it does not require factorization of the given numbers.
Example
Code
/**
* Returns least common multiple of two numbers
* @param a number 1
* @param b number 2
* @return lcm(a, b)
*/
public static int lcm(int a, int b) {
if (a == 0 || b == 0) {
return 0;
}
return (a * b) / gcd(a, b);
}
/**
* Returns greatest common divisor of the given numbers
* @param a number 1
* @param b number 2
* @return gcd(a, b)
*/
public static int gcd(int a, int b) {
if (a < 1 || b < 1) {
throw new IllegalArgumentException("a or b is less than 1");
}
int remainder = 0;
do {
remainder = a % b;
a = b;
b = remainder;
} while (b != 0);
return a;
}
/**
* Least common multiple of numbers "a" and "b"
* @param a number "a"
* @param b number "b"
* @return lcm(a, b)
* @autor Thomas (www.adamjak.net)
*/
public static int lcm(int a, int b)
{
if (a == 0 || b == 0)
{
return 0;
}
return (a * b) / gcd(a, b);
}
/**
* Greatest common divisor of numbers "a" and "b"
* @param a number "a"
* @param b number "b"
* @return gcd(a, b)
* @autor Thomas (www.adamjak.net)
*/
public static int gcd(int a, int b)
{
if (a < 1 || b < 1)
{
throw new ArgumentException("a or b is less than 1");
}
int r = 0;
do
{
r = a % b;
a = b;
b = r;
} while (b != 0);
return a;
}
/**
* Least common multiple of numbers "a" and "b"
* @param $a number "a"
* @param $b number "b"
* @return lcm(a, b)
* @autor Thomas (www.adamjak.net)
*/
function lcm($a, $b) {
if ($a == 0 || $b == 0) {
return 0;
}
return ($a * $b) / gcd($a, $b);
}
/**
* Least common multiple of numbers "a" and "b"
* @param $a number "a"
* @param $b number "b"
* @return gcd(a, b)
* @autor Thomas (www.adamjak.net)
*/
function gcd($a, $b) {
if ($a < 1 || $b < 1) {
die("a or b is less than 1");
}
$r = 0;
do {
$r = $a % $b;
$a = $b;
$b = $r;
} while ($b != 0);
return $a;
}
Sources
- POLÁK, Josef. Přehled středoškolské matematiky. 8th edition. Praha 4 : Prometheus, 2005. 608 p.