Greatest common divisor/pl

│ English (en) │ suomi (fi) │ français (fr) │ polski (pl) │ русский (ru) │

Największy wspólny dzielnik

Największym wspólnym dzielnikiem dwóch liczb całkowitych jest największa liczba całkowita, która dzieli je obie bez reszty. Jeśli liczby wynoszą 121 i 143, to największy wspólny dla nich dzielnik wynosi 11.

Istnieje wiele metod obliczania największego wspólnego dzielnika dwóch liczb. Można na przykład zaprogramować wersję algorytmu Euklidesa opartego na dzieleniu:

function greatestCommonDivisor

function greatestCommonDivisor(a, b: Int64): Int64;
var
  temp: Int64;
begin
  while b <> 0 do
  begin
    temp := b;
    b := a mod b;
    a := temp
  end;
  result := a
end;

function greatestCommonDivisor_euclidsSubtractionMethod(a, b: Int64): Int64;
begin
  // działa tylko z dodatnimi liczbami całkowitymi
  if (a < 0) then a := -a;
  if (b < 0) then b := -b;
  // nie wchodź do pętli warunkowej, ponieważ odjęcie zera sprawi, że nie będzie mogła zostać przerwana
  if (a = 0) then exit(b);
  if (b = 0) then exit(a);
  while not (a = b) do
  begin
    if (a > b) then
     a := a - b
    else
     b := b - a;
  end;
  result := a;
end;

Zobacz także

• Najmniejsza wspólna wielokrotność
• Operator mod
• mpz_gcd in GMP (GNU multiple precision)

zewnętrzne odnośniki

• Przykład rekurencyjny