Algoritmo di Euclide: differenze tra le versioni

Versione delle 11:59, 9 apr 2024

Versione delle 11:13, 13 giu 2024

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)Topici|I topici]]'', 158b, 29-35. L'algoritmo non richiede la [[fattorizzazione]] dei due interi.

Dati due [[numero naturale|numeri naturali]] <math>a</math> e <math>b</math>, l'algoritmo prevede che si controlli se <math>b</math> è zero. Se lo è, <math>a</math> è il MCD. Se non lo è, si

Riga 15:

== Pseudocodice ==

Una scrittura in [[pseudocodice]] dell'algoritmo (in cui «mod» indica il resto della divisione intera) è la seguente<ref>{{Cita web|url=https://www.treccani.it/enciclopedia/algoritmo-di-euclide_(Enciclopedia-della-Matematica)/|titolo=Euclide, algoritmo di - Treccani|sito=Treccani|lingua=it|accesso=2023-12-27}}</ref>:<syntaxhighlight>

inizia

leggi (a, b)

mentre bleggi >(a, 0 fai:b)

mentre b > r0 <- mod(a, b)fai:

a r <- mod(a, b)

b a <- rb

fine ciclo b <- r

fine ciclo
scrivi (a, "è il massimo comun divisore cercato")

finisci.

</syntaxhighlight>

==Dimostrazione della correttezza dell'algoritmo==