Difference between revisions of "Greatest common divisor"
From Lazarus wiki
Jump to navigationJump to searchm (Replace superfluous link with more detailed examples) |
|||
| (6 intermediate revisions by 4 users not shown) | |||
| Line 1: | Line 1: | ||
| + | {{Greatest common divisor}} | ||
| + | |||
The greatest common divisor of two integers is the largest integer that divides them both. | 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. | 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 | + | There are many methods to calculate this. |
| − | + | For example, the division-based Euclidean algorithm version may be programmed: | |
| − | |||
| − | <syntaxhighlight> | + | == <syntaxhighlight lang="pascal" inline>function greatestCommonDivisor</syntaxhighlight> == |
| − | function | + | <syntaxhighlight lang="pascal"> |
| + | function greatestCommonDivisor(a, b: Int64): Int64; | ||
var | var | ||
temp: Int64; | temp: Int64; | ||
| Line 18: | Line 20: | ||
a := temp | a := temp | ||
end; | end; | ||
| − | result := a | + | result := a; |
| − | end; | + | end; |
| + | function greatestCommonDivisor_euclidsSubtractionMethod(a, b: Int64): Int64; | ||
| + | begin | ||
| + | // only works with positive integers | ||
| + | if (a < 0) then a := -a; | ||
| + | if (b < 0) then b := -b; | ||
| + | // don't enter loop, since subtracting zero won't break condition | ||
| + | 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; | ||
</syntaxhighlight> | </syntaxhighlight> | ||
| − | == | + | == see also == |
| + | |||
| + | * [[Least common multiple|least common multiple]] | ||
| + | * [[Mod|<syntaxhighlight lang="pascal" inline>mod</syntaxhighlight> operator]] | ||
| + | * <syntaxhighlight lang="pascal" inline>mpz_gcd</syntaxhighlight> in [[gmp|GMP]] (GNU multiple precision) | ||
| + | |||
| + | == external references == | ||
| − | * [ | + | * [https://rosettacode.org/wiki/Greatest_common_divisor#Pascal_.2F_Delphi_.2F_Free_Pascal Recursive example] |
| − | |||
| − | |||
[[Category:Mathematics]] | [[Category:Mathematics]] | ||
| − | |||
Latest revision as of 01:16, 14 December 2023
│
English (en) │
suomi (fi) │
français (fr) │
polski (pl) │
русский (ru) │
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;
begin
// only works with positive integers
if (a < 0) then a := -a;
if (b < 0) then b := -b;
// don't enter loop, since subtracting zero won't break condition
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;
see also
- least common multiple
modoperatormpz_gcdin GMP (GNU multiple precision)
