Nejmenším společným násobkem (nsn, least common multiple - zkratka: lcm) přirozených čísel je číslo, které je násobkem každého z čísel
a je minimální.
Nejmenší společný násobek čísel značíme jako:
Výpočet
Rozklad na prvočísla
Nejjednodušším způsobem výpočtu nejmenšího společného násobku čísel je tato čísla rozložit na prvočísla a z rozkladů vybrat prvočinitele v nejvyšších mocninách. Jejich následným vynásobením získáme
.
Příklad
Jaký je nejmenší společný násobek čísel 6, 8 a 15?
Příklad
Jaký je nejmenší společný násobek čísel 140 a 72.
Příklad
Jaký je nejmenší společný násobek čísel 288 a 420?
Výše zmíněný postup si můžeme ilustrovat také pomocí Vennova diagramu, v němž budou čísla 288 a 420 reprezentována množinami svých prvočíselných dělitelů. Jelikož tyto množiny mají společné dělitele (průnik množin) uvedeny právě jednou, tak na diagramu najdeme všechny prvočinitele v jejich nejvyšších mocninách. Vynásobením všech čísel z diagramu tedy získáme nejmenší společný násobek čísel 288 a 420 (tj. 10080).
Euklidův algoritmus
Pro výpočet nejmenšího společného násobku dvou čísel lze také využít přepočtu z největšího společného dělitele. Tato metoda je zejména u velkých čísel výrazně výpočetně jednodušší než rozklad na prvočísla.
Pro efektivní výpočet nejvyššího společného dělitele můžeme použít Euklidův algoritmus.
Příklad
Kód
/**
* 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;
}
/**
* Nejmensi spolecny nasobek cisel "a" a "b"
* @param a cislo "a"
* @param b cislo "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);
}
/**
* Nejvetsi spolecny delitel cisel "a" a "b"
* @param a cislo "a"
* @param b cislo "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;
}
/**
* Nejmensi spolecny nasobek cisel "a" a "b"
* @param $a cislo "a"
* @param $b cislo "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);
}
/**
* Nejvetsi spolecny delitel cisel "a" a "b"
* @param $a cislo "a"
* @param $b cislo "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;
}
Literatura
- POLÁK, Josef. Přehled středoškolské matematiky. 8. vydání. Praha 4 : Prometheus, 2005. 608 s.