Größter gemeinsamer Teiler (GCD)
Gegeben sind zwei positive ganze Zahlen
a und b. Ihre Aufgabe ist, den größten gemeinsamen Teiler dieser beiden Zahlen zu bestimmen. Der größte gemeinsame Teiler ist die Zahl, die sowohl a als auch b teilt und zugleich die größte aller möglichen Teiler ist.Beachten Sie, dass der größte gemeinsame Teiler einer beliebigen Zahl und 0 derselben Zahl entspricht.
Eingabe
Die einzige Zeile der Eingabe enthält zwei ganze Zahlen
a und b (0 ≤ a, b ≤ ).Ausgabe
Das Programm soll den größten gemeinsamen Teiler von
a und b ausgeben.Beispiele
Eingabe | Ausgabe |
8 12 | 4 |
54 24 | 6 |
17 16 | 1 |
0 13 | 13 |
Erläuterung
- 8 → 1, 2, 4, 8 |||| 12 → 1, 2, 3, 4, 6, 12 ⇒ der größte gemeinsame Teiler ist 4
- 54 → 1, 2, 3, 6, 9, 18, 27, 54 |||| 24 → 1, 2, 3, 4, 6, 12, 24 ⇒ der größte gemeinsame Teiler ist 6
- 17 → 1, 17 |||| 16 → 1, 2, 4, 8, 16 ⇒ der größte gemeinsame Teiler ist 1
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB