Implementierung der GCD-Operation in Python

1. Verwenden Sie Rekursion, um den Code für die GCD in Python zu implementieren
2. Verwenden Sie eine for-Schleife, um den Code für den größten gemeinsamen Teiler in Python zu implementieren
3. Verwenden Sie den euklidischen Algorithmus, um den Code für den größten gemeinsamen Teiler in Python zu implementieren
4. Verwenden Sie die Funktion math.gcd(), um den größten gemeinsamen Teiler in Python zu berechnen

Der größte gemeinsame Teiler (GCD), auch als Höchster gemeinsamer Faktor (HCF) zweier Werte bezeichnet, ist die größte Zahl, die die beiden gegebenen Zahlen teilt. Der größte gemeinsame Teiler kann auch in Python berechnet und implementiert werden.

Dieses Tutorial zeigt die verschiedenen Methoden zum Implementieren des Codes für den größten gemeinsamen Teiler in Python.

Verwenden Sie Rekursion, um den Code für die GCD in Python zu implementieren

Eine Funktion, die sich im Funktionsdefinitionsblock selbst aufruft, wird als Rekursion bezeichnet. Rekursion kann verwendet werden, um eine Funktion zu erstellen, die den GCD von zwei Zahlen berechnet. Dieser Prozess ist sehr nützlich, um die Länge des Codes zu reduzieren und ist praktisch, um unnötige Funktionsaufrufe zu minimieren.

Der folgende Code verwendet Rekursion, um den Code für den größten gemeinsamen Teiler in Python zu implementieren.

def gcd1(x, y):
    if y == 0:
        return x
    else:
        return gcd1(y, x % y)


x = 72
b = 60

print("The gcd is : ", end="")
print(gcd1(72, 60))

Das obige Programm liefert das folgende Ergebnis.

Ausgabe:

The gcd is : 12

Verwenden Sie eine for-Schleife, um den Code für den größten gemeinsamen Teiler in Python zu implementieren

Eine einfache for-Schleife und die if-else-Anweisung können dabei helfen, dieselbe Aufgabe wie die anderen Methoden in diesem Artikel zu erfüllen.

Der folgende Code verwendet eine for-Schleife, um den Code für den größten gemeinsamen Teiler in Python zu implementieren.

def gcd2(a, b):

    if a > b:
        small = b
    else:
        small = a
    for i in range(1, small + 1):
        if (a % i == 0) and (b % i == 0):
            gcd = i

    return gcd


a = 72
b = 60

print("The gcd is : ", end="")
print(gcd2(72, 60))

Der obige Code liefert das folgende Ergebnis.

Ausgabe:

The gcd is : 12

Verwenden Sie den euklidischen Algorithmus, um den Code für den größten gemeinsamen Teiler in Python zu implementieren

Der euklidische Algorithmus ist eine weitere Technik, die in der Lage ist, schnell den größten gemeinsamen Teiler zweier Zahlen zu berechnen.

Der euklidische Algorithmus wird auf zwei Hauptfaktoren definiert.

• Die GCD ändert sich nicht, wenn eine kleinere Zahl eine größere Zahl subtrahiert. Daher finden wir schließlich den GCD bei fortgesetzter Subtraktion des größeren Wertes unter den beiden Zahlen.
• Wenn wir die kleinere Zahl dividieren, anstatt hier zu subtrahieren, stoppt der Algorithmus automatisch, wenn der Rest 0 gefunden wird.

Das folgende Programm unten verwendet den euklidischen Algorithmus, um den Code für den größten gemeinsamen Teiler in Python zu implementieren.

def gcd3(p, q):

    while q:
        p, q = q, p % q

    return p


p = 72
q = 60

print("The gcd is : ", end="")
print(gcd3(72, 60))

Der Code liefert das folgende Ergebnis.

Ausgabe:

The gcd is : 12

Verwenden Sie die Funktion math.gcd(), um den größten gemeinsamen Teiler in Python zu berechnen

Anstatt eine benutzerdefinierte Funktion zu erstellen, können wir jetzt einfach die vordefinierte Funktion math.gcd() verwenden, um die GCD von zwei Zahlen zu berechnen. Das Modul math muss in den Python-Code importiert werden, um die Funktion gcd() nutzen zu können.

Der folgende Code verwendet die Funktion math.gcd(), um den größten gemeinsamen Teiler in Python zu berechnen.

import math

a = math.gcd(72, 60)
print(a)

Das obige Programm liefert das folgende Ergebnis.

Ausgabe:

12

In Python 3.5 und höher ist die Funktion gcd im Modul math enthalten. In früheren Python-Versionen war die Funktion gcd im Modul fractions enthalten. Ab Python 3.5 ist es jedoch veraltet.