Greatest common divisor/pl

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

Największy wspólny dzielnik

The greatest common divisor of two integers is the largest integer that divides them both. If numbers are 121 and 143 then greatest common divisor is 11.

There are many methods to calculate this. For example, the division-based Euclidean algorithm version may be programmed:

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