/* M ximo Divisor Comum
	Via factoriza‡„o em primos.
	PP, 99.03													*/

#include <stdio.h>

main()
{	int x, y, fx[30], fy[30], mdc, m,n, xo, yo, i;
	int cfx, cfy, f, div, cd;
	int primo;

	clrscr();

	printf("Valor de x:");	scanf("%d", &x);
	printf("Valor de y:");	scanf("%d", &y);

	xo = x;
	yo = y;

	printf("Factoriza‡„o de x=%i:", x);
	cfx = 0;
   f = 0;
	primo = 2;

	do
	{	if (x%primo==0)
		{	fx[cfx] = primo;
			cfx++;	x = x/primo;	printf(" %i ", primo);
		}
		else
		{ 	f++;
			do
			{	primo = primo+1;
				div = 2;
				cd = 0;
				do
				{ if (primo%div==0) cd =1;
				  else div++;
				} while ((cd==0)&(div<primo/2));
			} while(cd==1);
			printf(" %i? ", primo);
		};
	} while (x!=1);
	printf(". %i divisores.\n", cfx);

	printf("Factoriza‡„o de y=%i:", y);
	primo = 2;
	cfy = 0;
	f=0;
	do
	{	if (y%primo==0)
		{	fy[cfy] = primo;
			cfy++;
			y = y/primo;
			printf(" %i ", primo);
		}
		else
		{ 	f++;
			do
			{	primo = primo+1;
				div = 2;
				cd = 0;
				do
				{ if (primo%div==0) cd =1;
				  else div++;
				} while ((cd==0)&(div<primo/2));
			} while(cd==1);
			printf(" %i? ", primo);
		};
	} while (y!=1);
	printf(". %i divisores.\n", cfy);

	/* Determina‡„o do MDC */
	printf("\nFactores de x=%i:", xo);
	for (i=0; i<cfx; i++) printf(" %i", fx[i]);
	printf("\nFactores de y=%i:", yo);
	for (i=0; i<cfy; i++) printf(" %i", fy[i]);

	mdc =1;
	m=n=0;
	printf("\n%i %i",cfx, cfy);

	do
	{
		printf("\n%3i %3i:%3i %3i", m,n,fx[m], fy[n]);
		if (fx[m]==fy[n])
		{	mdc = mdc*fx[m];
			m++;
			n++;
			printf("->%4i", mdc);
		}
		else
		{	if (fx[m]<fy[n]) m++;
			else n++;
		}
	} while ((m<cfx) & (n<cfy));

	printf("\nm.d.c =%d", mdc);
}