Greatest common divisor/fr

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;

Voir aussi

• Recursive example
• plus petit multiple commun
• Mod

From the Free Pascal wiki, page "Greatest common divisor/fr", as it stood on 2020-02-16 after a change by Trev, out of the wiki's dump of 2024-05-26. Copyright stays with the author who wrote it, according to the old wiki's Licensing page. If you have concerns about this material, message the admin.