Informatică Algoritmi
Algoritmul lui Euclid explicat
Algoritmul lui Euclid calculează cel mai mare divizor comun (CMMDC) a două numere întregi. Se bazează pe proprietatea că CMMDC(a,b) = CMMDC(b, a mod b).
Pași algoritmului
- 1 Pasul 1 Ia două numere a și b, cu a ≥ b. Dacă b=0, CMMDC este a.
- 2 Pasul 2 Calculează restul împărțirii lui a la b, notat r = a mod b.
- 3 Pasul 3 Înlocuiește a cu b și b cu r, apoi repetă de la pasul 1 până când b=0.
Exemplu numeric
- Pentru 48 și 18 48 mod 18 = 12, apoi 18 mod 12 = 6, apoi 12 mod 6 = 0. Când b=0, CMMDC=6.
- Pentru 1071 și 462 1071 mod 462 = 147, 462 mod 147 = 21, 147 mod 21 = 0 → CMMDC=21.
- Verificare CMMDC(48,18)=6 deoarece divizorii comuni sunt 1,2,3,6, iar cel mai mare este 6.
Folosește algoritmul pentru numere mari, e mai rapid decât descompunerea în factori.