Difference between revisions of "Greatest common divisor"
From Lazarus wiki
Jump to navigationJump to search (→Function GreatestCommonDivisor: add version based upon Euclids subtraction method) |
|||
| Line 22: | Line 22: | ||
result := a | result := a | ||
end; | end; | ||
| + | |||
| + | 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; | ||
| + | while not (a = b) do | ||
| + | begin | ||
| + | if (a > b) then | ||
| + | a := a - b | ||
| + | else | ||
| + | b := b - a; | ||
| + | end; | ||
| + | Result := a; | ||
| + | end; | ||
| + | |||
</syntaxhighlight> | </syntaxhighlight> | ||
Revision as of 15:52, 22 March 2015
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
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;
//only works with positive integers
begin
if (a < 0) then a := -a;
if (b < 0) then b := -b;
while not (a = b) do
begin
if (a > b) then
a := a - b
else
b := b - a;
end;
Result := a;
end;