Implementazioni di algoritmi/Algoritmo di Euclide

L'algoritmo di Euclide è un algoritmo per trovare il massimo comun divisore (indicato di seguito con MCD) tra due numeri interi. È uno degli algoritmi più antichi conosciuti, essendo presente negli Elementi di Euclide intorno al 300 a.C.; tuttavia l'algoritmo non è stato probabilmente scoperto da Euclide, ma potrebbe essere stato conosciuto anche 200 anni prima. Certamente era conosciuto da Eudosso di Cnido intorno al 375 a.C.; Aristotele (intorno al 330 a.C.) ne ha fatto cenno ne I topici, 158b, 29-35. L'algoritmo non richiede la fattorizzazione dei due interi.

Dati due numeri naturali a e b, si controlla se b è zero. Se lo è, a è il MCD. Se non lo è, si divide a / b e si assegna ad r il resto della divisione (operazione indicata con "a modulo b" più sotto). Se r = 0 allora si può terminare affermando che b è il MCD cercato altrimenti occorre assegnare a = b e b = r e si ripete nuovamente la divisione. L'algoritmo può essere anche espresso in modo naturale utilizzando la ricorsione in coda.

Implementazioni

C/C++/Java

versione ricorsiva

int mcd(int a, int b) {
  if (b == 0)
    return a;  
  else
    return mcd(b, a % b); 
}

versione non ricorsiva

int mcd(int a, int b) {
  int t;
  while (b != 0) {
    t = b;
    b = a % b;
    a = t;
  }
  return a;
}

Python

versione ricorsiva

def mcd(a,b):
  if b==0:
    return a
  else:
    return mcd(b,(a%b))

versione non ricorsiva

def mcd(a, b):
  while b:
    a, b = b, a%b
  return a

MATLAB/Octave

versione ricorsiva

function val = mcd(a, b):
  if b == 0
    val = a;
  else
    val = mcd(b, rem(a,b))
  end

versione non ricorsiva

function val = mcd(a, b):
  if b == 0
    val = a;
  else
    temp = a;
    a = b;
    b = rem(temp,b);
  end

Visual Basic .NET

versione non ricorsiva

    Function MCD(ByVal a As Integer, ByVal b As Integer) As Integer
        Dim m As Decimal
        While b <> 0
            m = a Mod b
            a = b
            b = m
        End While
        Return a
    End Function