MCD Euclide Python

<

>

<L'algoritmo Euclideo per la ricerca del MCD

start>

ELEMENTI DI EUCLIDE - LIBRO VII - Proposizione 1

Fissati due numeri disuguali, e sottratto continuamente in successione il minore dal maggiore, se il resto non misura mai completamente quello prima di se stesso, fino a che resti una unità, allora i numeri originari saranno primi tra loro

la proposizione Nella versione moderna

Siano a e b due interi positivi di cui si vuole determinare il loro massimo comun divisore. In primo luogo, esistono e sono unici due numeri q e r per i quali: a = bq + r e 0 ≤ r < b Inoltre, MCD(a, b) = MCD(b, r) applicando ripetutamente l’uguaglianza, l’ultimo resto non nullo è il massimo comun divisore di a e b.

APPLICAZIONE

DIAGRAMMA DI FLUSSO

Implementazione dell'algoritmo

a = int(input('Inserisci il primo numero: '))b = int(input('Inserisci il secondo numero: ')) while b > 0: r = a % b a, b = b, r print (a)

Attività completata

<

>