Algoritmo di Euclide: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Formattati C, e Scala |
m →Note |
||
Riga 1:
L''''algoritmo di Euclide''' è un [[algoritmo]] per trovare il [[massimo comun divisore|massimo comune divisore]] (indicato di seguito con MCD) tra due [[numero intero|numeri interi]]. È uno degli algoritmi più antichi conosciuti, essendo presente negli ''[[Elementi (Euclide)|Elementi]]'' di [[Euclide]]<ref>F. Acerbi, ''Euclide, Tutte le opere'', 2007, Bompiani.
{{en}} [[Thomas L. Heath]], ''The Thirteen Books of Euclid's Elements'', 2nd ed. [Facsimile. Original publication: Cambridge University Press, 1925], 1956, [[Dover Publications]]</ref> intorno al [[300 a.C.]]; tuttavia, probabilmente l'algoritmo non è stato 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 (Aristotele)|I topici]]'', 158b, 29-35. L'algoritmo non richiede la [[fattorizzazione]] dei due interi. Dati due [[numero naturale|numeri naturali]] ''a'' e ''b'', si controlla se ''b'' è zero (questa prima fase rientra ovviamente nell'ambito di un uso moderno dell'algoritmo ed era ignorata da Euclide e dai suoi predecessori, che non conoscevano lo zero). Se lo è, ''a'' è il MCD. Se non lo è, si
| |||