#include<stdio.h>
#include<stdlib.h>
#include<time.h>

/* Funktionsprototypen */
int ggT_k(int, int);
int ggT_m(int, int);
int ggT_r(int, int, int);
int kgV(int, int);

/* klassischer ggT */
int ggT_k(int zahl1, int zahl2) {
	int rest = 1;

	printf("\n  UP: Zahl1: %4d, Zahl2: %4d", zahl1, zahl2);

	/* Sonderfall: Eine der Zahlen ist 0 */
	if (!zahl1 || !zahl2)
		return (zahl1 + zahl2);

	if (zahl1 != zahl2)
		do {
			rest = (zahl1>zahl2) ? (zahl1-zahl2) : (zahl2-zahl1);
			if (zahl1 > zahl2)
				zahl1 = zahl2;
			zahl2 = rest;

			printf("\n  UP: Zahl1: %4d, Zahl2: %4d", zahl1, zahl2);
		} while (zahl1 != zahl2);
	else
		rest = zahl1;

	return rest;
}

/* moderner ggT */
int ggT_m(int zahl1, int zahl2) {
	int rest = zahl1 % zahl2;
	printf("\n  UP: Zahl1: %4d, Zahl2: %4d", zahl1, zahl2);

	/* Sonderfall: Eine der Zahlen ist 0 */
	if (!zahl1 || !zahl2)
		return (zahl1 + zahl2);

	if ((rest == 0) && (zahl1 > zahl2))
		return zahl2;

	while (rest) {
		rest  = zahl1 % zahl2;
		zahl1 = zahl2;
		zahl2 = rest;
		printf("\n  UP: Zahl1: %4d, Zahl2: %4d", zahl1, zahl2);
	}

	return zahl1;
}

/* rekursiver ggT */
int ggT_r(int zahl1, int zahl2, int ausgabe) {
	int rest;
	if (ausgabe)
		printf("\n  UP: Zahl1: %4d, Zahl2: %4d", zahl1, zahl2);

	/* Sonderfall: Eine der Zahlen ist 0 */
	if (!zahl1 || !zahl2)
		return (zahl1 + zahl2);

	if ((zahl1 < 0) || (zahl2 < 0))
		return -1;

	rest = zahl1 % zahl2;

	return rest ? ggT_r(zahl2, rest, ausgabe) : zahl2;
}

/* kgV mittels ggT */
int kgV(int zahl1, int zahl2) {
	int rVal = ggT_r(zahl1, zahl2, 0);
	return (rVal != -1 ? ((zahl1 * zahl2) / rVal) : -1);
}

/* Hauptprogramm */
int main(void) {
	/* erst einmal zwei Zahlen generieren */
	int zahl1, zahl2;
	srand(time(0));
	zahl1 = rand() % 9000;
	zahl2 = rand() % 2000;

	/* Funktionen ausprobieren */
	printf("\n\nHP: klassischer ggT von %4d und %4d: %8d\n\n", zahl1, zahl2, ggT_k(zahl1, zahl2));
	printf("\n\nHP:    moderner ggT von %4d und %4d: %8d\n\n", zahl1, zahl2, ggT_m(zahl1, zahl2));
	printf("\n\nHP:  rekursiver ggT von %4d und %4d: %8d\n\n", zahl1, zahl2, ggT_r(zahl1, zahl2, 1));
	printf("\n\nHP:             kgV von %4d und %4d: %8d\n\n", zahl1, zahl2, kgV(zahl1, zahl2));

	/* auf Eingabe warten bevor Terminal schließt */
	getchar();
	return 0;
}