Cu algoritmul lui Euclid putem calcula cel mai mare divizor comun (CMMDC) a două numere, fără să fie nevoie să descompunem numerele în factori.
Comentarii:
Algoritmul lui Euclid este una dintre cele mai surprinzătoare teoreme din matematică. Ne permite să calculăm cel mai mare divizor comun, fără să ştim care sunt toţi divizorii! Este ca şi cum ne-ar spune direct care este cel mai înalt munte din România fără să-i măsoare pe toţi.
Algoritmul lui Euclid este o metodă foarte rapidă.
Comparaţie: dorim să calculăm CMMDC (a, b) unde a şi b au fiecare câte 10 cifre.
Metoda 1 : descompunem numerele în factori
Fără folosirea unui calculator, descompunerea în factori a unui număr de 10 cifre, poate dura o lună întreagă.
Descompunerea lui a : durează maxim 1 lună
Descompunerea lui b : durează maxim 1 lună
Aflarea CMMDC : câteva minute.
În cel mai nefericit caz, metoda clasică durează 2 luni.
Metoda 2 : folosim algoritmul lui Euclid
În cel mai nefericit caz, aflăm CMMDC în 2 ore.
Dacă a şi b au câte 1000 de cifre, descompunerea în factori, folosind cel mai performant calculator existent pe planetă, durează miliarde de miliarde de miliarde de miliarde de miliarde de ani.
Folosind algoritmul lui Euclid, calculul CMMDC a doua numere, de cate 1000 cifre fiecare, durează mai puţin de o secundă pe un calculator PC de performanţă medie.