Euklidscher Algorithmus mit Hilfe von while-Schleife und modulo-Operator

Skyraz00

Grünschnabel
Hallo,

ich habe Probleme mit der Lösung einer Aufgabe, diese lautet:

Schreiben Sie ein Programm, das den Algorithmus von Euklid zur Bestimmung
des größten gemeinsamen Teilers (ggT) realisiert.
Lesen Sie hierzu zwei ganze Zahlen von der Tastatur ein und bestimmen Sie den ggT der beiden Zahlen mit
Hilfe von while-Schleife und modulo-Operator. Geben Sie die beiden eingelesenen Zahlen und ihren ggT auf
dem Bildschirm aus.
Benutzen Sie den angegebenen Pseudocode als Ausgangspunkt und setzen Sie ihn möglichst
direkt in ein C-Programm um. Verwenden Sie als Variablennamen in Ihrem Programm die entsprechenden Bezeichnungen
aus dem Pseudocode.

Also hier der Pseudo-Code:

r = p modulo q
solange r ungleich 0
p = q
q = r
r = p modulo q
Gib aus: ggT ist q

Trotz mehrer anläufe habe ich die Aufgabe nicht gelöst beckommen, falls mir jemand erklären könnte was ich falsch gemacht habe wäre das sehr hilfreich.
Hier ist mein derzeitiger Ansatz:
C:
#include <stdio.h>

int main(void)
{

    int r;
    int p;
    int q;

    printf("groeßter gemeinsamer Teiler (ggT) zweier natuerlicher Zahlen p und q");
    printf("Geben sie zwei natuerliche Zahlen ein: \n");
    printf("Geben sie deie erste Zahl ein: ");
    scanf_s("%d", &p);
    printf("Geben sie deie erste Zahl ein: ");
    scanf_s("%d", &q);

    r = p % q;

    while (r != 0)
    {
        p = q;
        q = r;
        r = p % q;
       
    }

    printf("Der ggT ist %d.\n", q);
    return 0;

}
 
Zuletzt bearbeitet:

cwriter

Erfahrenes Mitglied
Wenn man sich https://de.wikipedia.org/wiki/Euklidischer_Algorithmus#Iterative_Variante so anschaut, hast du einfach die Variablen ein bisschen vertauscht. Der ggT sollte demnach p sein, und nicht q. Zudem kannst du dir die 2 modulo-statements sparen, indem du zu Beginn des Loop "r = p % q" rechnest und dann statt auf "r != 0" auf "q != 0" vergleichst.

Gruss
cwriter

/EDIT: Oh, der Code ist ja so gegeben - hm. (Er sollte eigentlich auch funktionieren). Kannst du mal ein Beispiel geben, wo es nicht funktioniert? Was genau tut nicht, wie es soll?