Suurin yhteinen tekijä
editSuurin 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
editfunction 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
edit- Recursive example
- Pienin yhteinen jaettava (Least common multiple)
- Mod