Alle Herausforderungen
Einfach 1 gelöst 50.0% Erfolgsquote

Größter gemeinsamer Teiler

Finde die größte Zahl, die beide Werte teilt.

Das lernst du

  • Den euklidischen Algorithmus mit Resten anwenden
  • Eine mathematische Regel in eine Schleife übersetzen
  • Verstehen, warum der Algorithmus schnell ist

Problem

Gib den größten gemeinsamen Teiler von a und b zurück. Euklids Algorithmus ersetzt wiederholt (a, b) durch (b, a mod b), bis b gleich 0 ist.

Implementiere gcd(a, b).

Eingabe

a: Die erste Zahl. b: Die zweite Zahl.

Ausgabe

Gib gcd(a, b) zurück. gcd(0, 0) ist 0.

Einschränkungen

0 ≤ a, b ≤ 10¹⁸

Beispiele

Beispiel 1
Eingabe:
a = 48
b = 18

Erwartete Ausgabe:
expected = 6
Eingabe:
long long a = 48;
long long b = 18;

Erwartete Ausgabe:
long long expected = 6;
Eingabe:
long a = 48;
long b = 18;

Erwartete Ausgabe:
long expected = 6;

Erläuterung

48 mod 18 = 12, 18 mod 12 = 6, 12 mod 6 = 0, daher ist die Antwort 6.

Beispiel 2
Eingabe:
a = 17
b = 5

Erwartete Ausgabe:
expected = 1
Eingabe:
long long a = 17;
long long b = 5;

Erwartete Ausgabe:
long long expected = 1;
Eingabe:
long a = 17;
long b = 5;

Erwartete Ausgabe:
long expected = 1;

Erläuterung

17 und 5 haben keinen gemeinsamen Teiler außer 1.

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Der gcd ändert sich nicht, wenn du ein Paar durch den Restschritt ersetzt.

Hinweis 2

Tausche die Rollen der beiden Zahlen immer wieder, bis die zweite null wird.

Hinweis 3

Achte darauf, den Fall zu behandeln, in dem beide Eingaben null sind.

Erwartete Komplexität

Zeit O(log min(a, b)), zusätzlicher Speicher O(1)

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

# Coder Sprache Zeit Speicher KI-Bewertung Lösung
1 HJhettory Jurash Python 970 ms - 3/5 Code ansehen

Von anderen lernen

Community-Lösungen

Achtung Spoiler: 1 vollständige Lösung unten Versuche es zuerst selbst zu lösen. Du kannst trotzdem einen Blick auf den Code und die KI-Reviews anderer Entwickler werfen. Melde dich an und löse die Aufgabe, um an der Diskussion teilzunehmen.