Python Höchster gemeinsamer Faktor (HCF / GCD)

Berechnen Sie den höchsten gemeinsamen Faktor (HCF) oder den größten gemeinsamen Teiler (GCD) zweier Zahlen mit dem euklidischen Algorithmus.

Versuchen Sie es im Editor

Übersicht

Der höchste gemeinsame Faktor (HCF), auch bekannt als der größte gemeinsame Teiler (GCD), ist die größte positive ganze Zahl, die zwei oder mehr ganze Zahlen dividiert, ohne einen Rest zu hinterlassen.

Der Euklidische Algorithmus ist eine äußerst effiziente Methode zur Berechnung von HCF. Es besagt, dass der GCD zweier Zahlen auch deren Differenz teilt.

In Python implementieren wir dies iterativ mithilfe einer While-Schleife, in der wir kontinuierlich die größere Zahl durch den Rest ihrer Division ersetzen.

Code- und Ausführungsausgabe

Euklidische Schleifenimplementierung zum Ermitteln von HCF/GCD zweier Zahlen.

hcf_gcd.py

Versuchen Sie es im Editor

def find_gcd(a, b):
    # Euclidean Algorithm
    while b != 0:
        a, b = b, a % b
    return a

print("GCD of 36 and 60 is:", find_gcd(36, 60))
print("GCD of 17 and 5 is: ", find_gcd(17, 5))

Terminal-Ausgabe

GCD of 36 and 60 is: 12
GCD of 17 and 5 is:  1

Schrittweise Umsetzung

Bruchvereinfachung und Mathematik-Engines
Kryptografiealgorithmen (wie die Generierung privater RSA-Schlüssel)
Entwerfen regelmäßiger Veranstaltungspläne

Häufig gestellte Fragen

Verfügt Python über eine integrierte GCD-Funktion?

Ja! Die Standardbibliothek von Python enthält „math.gcd(a, b)“, die unter der Haube eine kompilierte C-Implementierung verwendet.