Největším společným dělitelem (nsd, greatest common divisor (zkratka: gcd)) přirozených čísel je číslo, které dělí každé z těchto čísel, a je maximální.
Výpočet
Rozklad na prvočísla
Nejjednodušším způsobem výpočtu největšího společného dělitele je rozložit jednotlivá zkoumaná čísla na prvočísla a z nich vybrat prvočinitele v nejmenší společné mocnině (nejmenším z exponentů). Vynásobením prvočinitelů v příslušných mocninách získáme největšího společného dělitele daných čísel.
Příklad
Jaký je nejvyšší společný dělitel čísel 72, 48 a 54?
Příklad
Jaký je nejvyšší společný dělitel čí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ů. V průniku těchto množin nalezneme největšího společného dělitele zmíněných čísel.
Euklidův algoritmus
Rozklad na prvočísla (faktorizace) je z výpočetního hlediska velmi náročný problém. Proto pro efektivní výpočet největšího společného dělitele velkých čísel používáme Euklidův algoritmus.
Princip
Vstupem algoritmu jsou dvě přirozená čísla a
. Algoritmus v každém svém kroku vydělí se zbytkem číslo
číslem
. Pokud zbytek není nulový, tak do
přiřadí číslo
a zbytek po dělení přiřadí do uvolněné proměnné
a celý postup opakuje.
V okamžiku, kdy je zbytek po dělení nulový, je v proměnné uložen největší společný dělitel čísel
a
.
Pro podrobnější výklad si můžete přečíst tento článek.
Příklad
Jaký je největší společný dělitel čísel 133 a 15?
Příklad
Jaký je největší společný dělitel čísel 140 a 15?
Nejmenší společný násobek
Pro získání nejmenšího společného násobku dvou čísel můžeme využít následující přepočet:
Příklad
Jaký je nejmenší společný násobek čísel 140 a 15?
Kód
/**
* Vstup: Čísla a > 0, b > 0
* Výstup: gcd(a, b)
*/
function gcd(a, b)
if a >= b then
m = a
n = b
else
m = b
n = a
while n != 0 do
m = p*n + z
m = n
n = z
return m
/**
* 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");
while (b != 0) {
int tmp = a;
a = b;
b = tmp % b;
}
return a;
}
/**
* Nejvetsi spolecny delitel cisel "a" a "b"
* @param a cislo "a"
* @param b cislo "b"
* @return gcd(a, b)
* @autor Thomas (www.adamjak.net)
*/
int gcd(int a, int b)
{
if (a < 1 || b < 1)
{
printf("a or b is less than 1");
return -1;
}
int r = 0;
do
{
r = a % b;
a = b;
b = r;
} while (b != 0);
return a;
}
/**
* 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;
}
/**
* 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;
}
mgcd(X, X, X). mgcd(X, Y, X) :- Y == 0. mgcd(X, Y, R) :- Y > X, mgcd(Y, X, R). mgcd(X, Y, R) :- X > Y, R1 is X mod Y, mgcd(Y,R1,R).