Algoritmul lui Euclid ne poate ajuta să determinăm, având 2 numere, cel mai mare divizor comun, printr-o metodă simplă şi eficientă din punctul de vedere al consumului de resurse.

„Un număr întreg d se numește cel mai mare divizor comun a numerelor întregi a și b dacă și numai dacă pentru orice divizor comun c al lui a și b, d este un divizor al lui c.

În cazul în care impunem condiția d>0 este relativ simplu de verificat dacă d este unic. Acest număr se notează cu c.m.m.d.c(a,b), sau mai simplu: (a,b).

Folosind principiul bunei ordonări a numerelor naturale, putem deduce că c.m.m.d.c(a,b) este cel mai mic număr pozitiv care poate fi scris ca o combinație liniară a lui a și b, adică cel mai mic număr natural de forma a*x+b*y, unde x,y sunt numere întregi.”

Sursă: Wikipedia

Pseudocod

Di: n, m
De: n

citeşte n, m
┌cât timp n!=m execută
│   ┌dacă n>m
│   │   atunci n←n-m
│   │   altfel m←m-n
│   └■
└■
Scrie n

Limbaj C++

#include <iostream.h>
unsigned int n, m;
main()
{
cin>>n>>m;
while (n=m)
if (n>m) 
n=n-m;
else m=m-n;
Cout<<n;
}