Greatest common divisor/fr
From Free Pascal wiki
Jump to navigationJump to search
│
English (en) │
suomi (fi) │
français (fr) │
polski (pl) │
русский (ru) │
Le plus grand diviseur commun (PGDC) de deux entiers est le plus grand entier qui les divise les deux. Si les nombres sont 121 et 143 alors le PGDC est 11 (121=11x11 et 143=11*13)
Il existe plusieurs méthodes pour le calculer. P.ex., l'algorithme d'Euclide basé sur la division peut être implémenté.
Fonction 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;
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;