Finden des größten gemeinsamen Teilers in Java

1. Übersicht

In der Mathematik ist die GCD von zwei Ganzzahlen, die nicht Null sind, die größte positive Ganzzahl, die jede der Ganzzahlen gleichmäßig teilt.

In diesem Tutorial werden drei Ansätze betrachtet, um den Greatest Common Divisor (GCD) von zwei ganzen Zahlen zu finden. Weiter werden wir uns ihre Implementierung in Java ansehen.

2. Brute Force

Bei unserem ersten Ansatz iterieren wir von 1 bis zur kleinsten angegebenen Zahl und prüfen, ob die angegebenen Ganzzahlen durch den Index teilbar sind. Der größte Index, der die angegebenen Zahlen teilt, ist die GCD der angegebenen Zahlen:

int gcdByBruteForce(int n1, int n2) { int gcd = 1; for (int i = 1; i <= n1 && i <= n2; i++) { if (n1 % i == 0 && n2 % i == 0) { gcd = i; } } return gcd; }

Wie wir sehen können, ist die Komplexität der obigen Implementierung O (min (n1, n2)), da wir n- mal (entsprechend der kleineren Zahl) über die Schleife iterieren müssen , um die GCD zu finden.

3. Euklids Algorithmus

Zweitens können wir den Euklid-Algorithmus verwenden, um die GCD zu finden. Der Algorithmus von Euclid ist nicht nur effizient, sondern auch leicht zu verstehen und mithilfe der Rekursion in Java leicht zu implementieren.

Euklids Methode hängt von zwei wichtigen Theoremen ab:

  • Erstens, wenn wir die kleinere Zahl von der größeren Zahl subtrahieren, ändert sich die GCD nicht . Wenn wir also die Zahl weiter subtrahieren, erhalten wir schließlich ihre GCD
  • Zweitens, wenn die kleinere Zahl die größere Zahl genau teilt, ist die kleinere Zahl die GCD der beiden gegebenen Zahlen.

Beachten Sie in unserer Implementierung, dass wir Modulo anstelle von Subtraktion verwenden, da es im Grunde viele Subtraktionen gleichzeitig gibt:

int gcdByEuclidsAlgorithm(int n1, int n2) { if (n2 == 0) { return n1; } return gcdByEuclidsAlgorithm(n2, n1 % n2); }

Beachten Sie auch, wie wir n2 an der Position von n1 verwenden und den Rest an der Position von n2 im rekursiven Schritt des Algorithmus verwenden .

Ferner ist die Komplexität des Euklid-Algorithmus O (Log min (n1, n2)), was im Vergleich zu der zuvor gesehenen Brute-Force-Methode besser ist.

4. Steins Algorithmus oder binärer GCD-Algorithmus

Schließlich können wir den Stein-Algorithmus, auch als binärer GCD-Algorithmus bekannt , verwenden, um die GCD von zwei nicht negativen ganzen Zahlen zu ermitteln. Dieser Algorithmus verwendet einfache arithmetische Operationen wie arithmetische Verschiebungen, Vergleiche und Subtraktionen.

Steins Algorithmus wendet wiederholt die folgenden grundlegenden Identitäten in Bezug auf GCDs an, um GCD von zwei nicht negativen ganzen Zahlen zu finden:

  1. gcd (0, 0) = 0, gcd (n1, 0) = n1, gcd (0, n2) = n2
  2. Wenn n1 und n2 beide gerade ganze Zahlen sind, dann ist gcd (n1, n2) = 2 · gcd (n1 / 2, n2 / 2) , da 2 der gemeinsame Teiler ist
  3. Wenn n1 eine gerade ganze Zahl und n2 eine ungerade ganze Zahl ist, dann ist gcd (n1, n2) = gcd (n1 / 2, n2) , da 2 nicht der gemeinsame Teiler ist und umgekehrt
  4. Wenn n1 und n2 beide ungerade ganze Zahlen sind und n1> = n2 , dann ist gcd (n1, n2) = gcd ((n1-n2) / 2, n2) und umgekehrt

Wir wiederholen die Schritte 2 bis 4, bis n1 gleich n2 oder n1 = 0 ist . Die GCD ist (2n) * n2 . Hier ist n die Häufigkeit, mit der 2 in n1 und n2 gemeinsam gefunden wird, während Schritt 2 ausgeführt wird:

int gcdBySteinsAlgorithm(int n1, int n2) { if (n1 == 0) { return n2; } if (n2 == 0) { return n1; } int n; for (n = 0; ((n1 | n2) & 1) == 0; n++) { n1 >>= 1; n2 >>= 1; } while ((n1 & 1) == 0) { n1 >>= 1; } do { while ((n2 & 1) == 0) { n2 >>= 1; } if (n1 > n2) { int temp = n1; n1 = n2; n2 = temp; } n2 = (n2 - n1); } while (n2 != 0); return n1 << n; }

Wir können sehen, dass wir arithmetische Verschiebungsoperationen verwenden, um durch 2 zu dividieren oder zu multiplizieren. Außerdem verwenden wir Subtraktion, um die gegebenen Zahlen zu reduzieren.

Die Komplexität von Steins Algorithmus bei n1> n2 ist O ((log 2 n1) 2) . wenn n1 <n2 ist, ist es O ((log 2 n2) 2).

5. Schlussfolgerung

In diesem Tutorial haben wir uns verschiedene Methoden zur Berechnung der GCD von zwei Zahlen angesehen. Wir haben diese auch in Java implementiert und einen kurzen Blick auf ihre Komplexität geworfen.

Wie immer ist der vollständige Quellcode unserer Beispiele hier wie immer auf GitHub verfügbar.