
from collections import Counter

def prime_factors(n):
    """Gibt die Primfaktoren von n als Liste zurück"""
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

def lcm(a, b):
    """Berechnet das kleinste gemeinsame Vielfache (kgV) von a und b"""
    # Zerlege die Zahlen in ihre Primfaktoren
    factors_a = prime_factors(a)
    factors_b = prime_factors(b)
    
    # Erstelle Counter-Objekte, um die Häufigkeiten der Primfaktoren zu zählen
    counter_a = Counter(factors_a)
    counter_b = Counter(factors_b)
    
    # Bestimme die Primfaktoren des kgV
    lcm_factors = counter_a | counter_b  # Vereinigung der beiden Counter (nimmt max. Häufigkeit)
    
    # Berechne das kgV aus den Primfaktoren
    lcm_value = 1
    for factor in lcm_factors:
        lcm_value *= factor ** lcm_factors[factor]
    
    return lcm_value

# Hauptprogramm
def main():
    # Frage die beiden Zahlen ab
    a = int(input("Gib die erste Zahl ein: "))
    b = int(input("Gib die zweite Zahl ein: "))
    
    result = lcm(a, b)
    print(f"Das kleinste gemeinsame Vielfache (kgV) von {a} und {b} ist: {result}")

if __name__ == "__main__":
    main()
