Euklidischer Algorithmus

Der Algorithmus kann wegen der Beziehung

ggT(a,b) * kgV(a,b) = ab

zwischen dem größten gemeinsamen Teilers (ggT) und dem kleinsten gemeinsamen Vielfachen (kgV) zweier Zahlen a und b auch zur Berechnung des kleinsten gemeinsamen Vielfachen verwendet werden.

program Euklid(input, output);

    var
        a, b, c, dummy: integer;

    procedure init; begin
        writeln('Auffinden des groessten gemeinsamen Teilers zweier Zahlen');
        writeln('mittels des Euklidschen Algorithmus');
        writeln;
        writeln('Geben Sie zwei ganze Zahlen ein.');
        readln(a, b);
        if a < b then begin
            dummy := a;
            a     := b;
            b     := dummy
        end; {if}
        c := 1;
    end; {init}

    begin {Euler}
        init;
        while c<>0 do begin
            c := a mod b;
            a := b;
            b := c
        end; {while}
        writeln('Der groesste gemeinsame Teiler ist ', a, '.');
    end. {Euler}