Difference between revisions of "Greatest common divisor"

From Lazarus wiki
Jump to navigationJump to search
m
m (Replace superfluous link with more detailed examples)
Line 25: Line 25:
 
== See also ==
 
== See also ==
  
* [https://www.youtube.com/watch?v=_-sAsp1WlhY| Pascal - Basic Maths 3 - Greatest Common Divisor (gcd) using Euclid's Algorithm ]
+
* [http://rosettacode.org/wiki/Greatest_common_divisor#Pascal_.2F_Delphi_.2F_Free_Pascal Recursive example]
 
* [[Least common multiple]]
 
* [[Least common multiple]]
 
* [[Mod]]
 
* [[Mod]]

Revision as of 13:42, 10 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;

See also