Algoritme van Euclides ⭐⭐⭐

Wat is het algoritme van Euclides?

Het algoritme van Euclides berekent de Grootste Gemene Deler (GGD) van twee gehele getallen. De GGD is het grootste getal dat beide getallen exact deelt.

Het basisidee: de GGD van a en b is gelijk aan de GGD van b en de rest van a / b. Dit herhaalt zich totdat de rest 0 is, waarna a de GGD bevat.

GGD(12, 8) → GGD(8, 4) → GGD(4, 0) → resultaat: 4

Het algoritme in pseudocode:

zolang b != 0:
    temp = b
    b = a % b
    a = temp
resultaat = a

Opgave

Lees twee gehele getallen a en b en bereken hun GGD met het algoritme van Euclides.

Invoer

Twee gehele getallen op dezelfde regel:

1. a
2. b

Uitvoer

Print de Grootste Gemene Deler van a en b.

Voorbeelden

Invoer:

12 8

Uitvoer:

4

Invoer:

15 5

Uitvoer:

5