Algorithmensammlung: Zahlentheorie: Euklidischer Algorithmus
Aus Wikibooks
Algorithmensammlung: Zahlentheorie
-
- Euklidischer Algorithmus
Inhaltsverzeichnis |
[Bearbeiten] Euklidischer Algorithmus
Mit dem Euklidischen Algorithmus kann man den größten gemeinsamen Teiler zweier Zahlen herausfinden. Für eine genaue Beschreibung siehe 
Euklidischer Algorithmus.
[Bearbeiten] Implementierungen
[Bearbeiten] C
- a und b sind die beiden Zahlen von denen man den größten Teiler haben möchte.
int Euklid(int a, int b) { if (a == 0) //Wenn a=0 ist b der kleinste Teiler laut Definition { return b; } while(b != 0) //Solange wiederholen, solange b nicht 0 ist. { if (a > b) { a = a - b; //Wenn a größer als b subtrahiere b von a. } else { b = b - a; //In jedem anderen Fall subtrahiere a von b. } } return a; //In a steht jetzt der kleinste gemeinsame Teiler von a und b. }
- Iterative Variante des modernen euklidischen Algorithmus. a muss größer als b sein.
int Euklid(int a, int b) { int c; while(b != 0) { c = a % b; a=b; b=c; } return a; }
[Bearbeiten] Python
def euklid(a, b): while b != 0: a, b = b, a % b return a
