Alle Herausforderungen
Einfach 1 gelöst 14.3% Erfolgsquote

Kleinstes gemeinsames Vielfaches

Finde die kleinste positive Zahl, die durch beide Werte teilbar ist.

Das lernst du

  • Das kgV aus dem ggT berechnen
  • Überlauf vermeiden, indem man vor dem Multiplizieren teilt
  • Eine Funktion in einer anderen wiederverwenden

Problem

Gib das kleinste gemeinsame Vielfache von a und b zurück, also die kleinste positive Zahl, die durch beide teilbar ist. lcm(a, b) = a / gcd(a, b) × b.

Implementiere lcm(a, b).

Eingabe

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

Ausgabe

Gib lcm(a, b) zurück.

Einschränkungen

1 ≤ a, b ≤ 1.000.000.000

Beispiele

Beispiel 1
Eingabe:
a = 4
b = 6

Erwartete Ausgabe:
expected = 12
Eingabe:
long long a = 4;
long long b = 6;

Erwartete Ausgabe:
long long expected = 12;
Eingabe:
long a = 4;
long b = 6;

Erwartete Ausgabe:
long expected = 12;

Erläuterung

Vielfache von 4: 4, 8, 12…; Vielfache von 6: 6, 12…; das erste gemeinsame ist 12.

Beispiel 2
Eingabe:
a = 7
b = 7

Erwartete Ausgabe:
expected = 7
Eingabe:
long long a = 7;
long long b = 7;

Erwartete Ausgabe:
long long expected = 7;
Eingabe:
long a = 7;
long b = 7;

Erwartete Ausgabe:
long expected = 7;

Erläuterung

Das kgV einer Zahl mit sich selbst ist die Zahl: 7.

So gehst du vor

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

Hinweis 1

Nutze die Beziehung zwischen gcd und lcm statt nach Vielfachen zu suchen.

Hinweis 2

Berechne zuerst den gcd und kombiniere dann die beiden Zahlen sorgfältig.

Hinweis 3

Teile vor dem Multiplizieren, um das Risiko eines Überlaufs zu verringern, auch bei großen Eingaben.

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 1,017 ms - 4/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.