/*
 * Maxim comu divisor per Algorisme d’Euclides
 * MCD(a,0)=a
 * MCD(a,b) = MCD(b,a%b)
 * Prova-ho amb nums grans com ara [a: 654 b: 2322]
 */
#include <stdio.h>
main() {
	int a, b, old_a;

	printf("MCD(a,b):\n");
	printf("a: ");scanf("%d", &a);
	printf("b: ");scanf("%d", &b);
	while(b) {
		old_a = a;
		a = b;
		b = old_a % b;
		printf("a = %d\tb = %d\n", a, b);
	}
	printf("MCD = %d\n", a);
}

/*
$ ./a.out 
MCD(a,b):
a: 654
b: 2322
a = 2322	b = 654
a = 654	b = 360
a = 360	b = 294
a = 294	b = 66
a = 66	b = 30
a = 30	b = 6
a = 6	b = 0
MCD = 6
$ ./a.out 
MCD(a,b):
a: 25
b: 10
a = 10	b = 5
a = 5	b = 0
MCD = 5
$ ./a.out 
MCD(a,b):
a: 10
b: 25
a = 25	b = 10
a = 10	b = 5
a = 5	b = 0
MCD = 5
$ 
*/