De oud-Griekse wiskundige Euclides heeft rond 300 v.C. een algoritme bedacht om de grootste gemene deler (ggd) van twee getallen te berekenen. Het algoritme steunt op het herhaaldelijk toepassen van de eigenschap:
De grootste gemene deler van \(\mathsf{grootste\_getal}\) en \(\mathsf{kleinste\_getal}\) is gelijk aan de grootste gemene deler van \(\mathsf{kleinste\_getal}\) en de rest bij deling van \(\mathsf{grootste\_getal}\) door \(\mathsf{kleinste\_getal}\).
Schrijf een programma dat vraagt naar twee natuurlijke getallen. Het programma berekent en toont de grootste gemene deler van deze getallen.
Invoer:
Geef een eerste natuurlijk getal: 876868698293
Geef een tweede natuurlijk getal: 51454235
Uitvoer:
7