Mega Code Archive
Getting the greatest common divisor
<![CDATA[
Title: Getting the greatest common divisor
Question: Ever wanted to find the greatest common divisor in a fraction ?
Answer:
Using Euclids algorithm we accomplish this task easily.
This article demonstrates the recursive GreatestCommonDivisor() function.
function gcd(num1, num2: integer): integer;
var
remainder: integer;
begin
remainder := num2 mod num1;
if (remainder 0) then
result := gcd(remainder, num1)
else
result := num1;
end;
{ Example:
to find the greatest common divisor of the fraction 64 over 16 call gcd() like this: gcd(64,16) - remainder is 16 thus it calls itself with the remainder,num1 as parameters. This returns 16 which is the greatest common divisor.
gcd(64,16) = gcd(16,64) = 16
}
]]>