Greatest common divisor/fi

Suurin yhteinen tekijä

Suurin yhteinen tekijä on suurin kokonaisluku, jolla voidaan jakaa annetut kaksi kokonaislukua. Jos annetut kokonaisluvut ovat 121 ja 143 niin niiden suurin yhteinen tekijä on 11.

On olemassa monia menetelmiä laskea tämä. Esimerkiksi jakoon perustuva Eukleideen algoritmia käyttävä versio voidaan ohjelmoida näin:

Funcktio 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;

See also

• Recursive example
• Least common multiple
• Mod