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:

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

Tai toinen vaihtoehtoinen tapa

function GreatestCommonDivisor_EuclidsSubtractionMethod(a, b: Int64): Int64;
//only works with positive integers
begin
  if (a < 0) then a := -a;
  if (b < 0) then b := -b;
  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;

Katso myös

• Recursive example
• Pienin yhteinen jaettava (Least common multiple)
• Mod

From the Free Pascal wiki, page "Greatest common divisor/fi", as it stood on 2020-02-16 after a change by Trev, out of the wiki's dump of 2024-05-26. Copyright stays with the author who wrote it, according to the old wiki's Licensing page. If you have concerns about this material, message the admin.