# Größter gemeinsamer Teiler - Python



## Arcoz (23. September 2008)

Hi Tutorial Community,
habe folgendes Problem:

Muss am Freitag mit Python ein Programm vorstellen, 
was den Größtmöglichen Teiler ausgibt.

Habe schon im Internet danach gesucht,
allerdings dürfen wir keine "Import" Funktion benutzen.
Daher kein "Math" Scrypt oder sonstiges.

Allein mit einer While-Schleife und der zuordnung der Variablen.

Im Internet bin ich auf folgenden Code gestoßen:


```
while y > 0:
    Rest = x % y
    x = y
    y = Rest
```

Nun weiß ich nicht ob der Code genau stimmt,
bzw. Versteh ich den Code nicht, 
warum die Variablem immer neu zugeordnet werden.

Kann mir dabei jemand helfen,
entweder ein Code zu schreiben
oder falls der vorhandene Stimmt,
erklären wie dieser Funktioniert?


Ich hoffe ihr könnt mir helfen

Mit freundlichen Grüßen
Arcoz


----------



## Matthias Reitinger (23. September 2008)

Hallo,

das sieht nach dem modernen euklidischen Algorithmus aus.

Grüße,
Matthias


----------



## Arcoz (23. September 2008)

Matthias Reitinger hat gesagt.:


> Hallo,
> 
> das sieht nach dem modernen euklidischen Algorithmus aus.
> 
> ...



Ja das ist der Euklidischer Algorithmus,
das ist das auch nicht das Problem,
nur das ganze in Python umzusetzen damit komm ich nicht klar.

Kann mir jemand Tipps dazu geben?


----------



## Matthias Reitinger (23. September 2008)

Arcoz hat gesagt.:


> Ja das ist der Euklidischer Algorithmus,
> das ist das auch nicht das Problem,


Warum schreibst du dann, dass du den Code nicht verstehst und du ihn erklärt haben willst?



Arcoz hat gesagt.:


> nur das ganze in Python umzusetzen damit komm ich nicht klar.


Den Quellcode hast du doch schon im Ursprungsbeitrag reingestellt.

Um ehrlich zu sein verstehe ich jetzt nicht mehr so ganz, wo dein Problem liegt...


----------



## Arcoz (23. September 2008)

Den Code habe ich im Internet gefunden,
da viele das gleiche Problem haben.

Allerdings geht es nicht darum das Programm abzugeben,
es wird geschaut ob es funktioniert und das wars,
sondernd ich muss das Programm wierklich Schritt für Schritt erklären.

Nur verstehe ich nicht wie der code funktioniert.
Warum x = y ist usw.

Der Lehrer will, das ich mich noch vorne stelle und
dann anfange, Schritt für Schritt, warum ich diese Befehle benutzt habe,
was in dem Moment mit der Ursprungszahl passiert usw.

Am besten ich vergess den Code oben und fang von vorne an.

1. Zuerst müssen 2 Zahlen her, z.B 1071 und 1021
2. Nun geht es ab in die whileschleife.
3. Hier hakt es nun schon.


```
a = 1071
b = 1021

while ()
```

Will es nicht nur fertig haben, sondernd kapieren :suspekt:

Hoffe ihr versteht das und könnt mir, (und wenn es nur Tipps sind) helfen


----------



## Matthias Reitinger (23. September 2008)

Hast du dir den Wikipedia-Artikel schon durchgelesen? Da ist doch eigentlich alles schön erklärt.


----------



## Arcoz (23. September 2008)

Ja erklärt schon,
nur das ganze in Python umzusetzen 
ist für mich nicht gerade einfach.

Das man die Zahlen (größere von kleinere)
gegenseitig voneinander abzieht um so an den Teiler zu kommen,
ergibt ja auch sinn. 
Nur wie schreibt man das ganze in Python?

Brauche denke ich nur eine kleine Starthilfe,
sodass ich es selber schreiben kann.

Nur finde ich keinen anfang


----------



## Sukrim (3. Oktober 2008)

Wikipedia beschreibt das doch schon recht gut...

Du teilst die eine Zahl durch die andere und schaust was an Rest bleibt und schreibst das sinnigerweise in die Variable "Rest"
"Rest = x % y"
Dann merkt man sich man die Zahl da das ja der potenzielle Kandidat für den ggT ist...
"x = y"
...und nimmt y neu an mit dem Wert von "Rest"
"y = Rest"

Ist y jetzt 0, ist der ggT gefunden (und steht in x festgeschrieben) - ist er es nicht, gibt es noch einen Rest und man beginnt von vorne, indem man schaut, wieviel bei der Division übrig bleibt, dann merkt man sich das wieder wodurch man dividiert hat und schaut ob der Rest _jetzt_ 0 ist... usw.


----------

