#include <stdio.h>

main()
{
	int n; /* first input */
	int m; /* second input */
	int t; /* stores gcd */

	/* Read inputs */
	printf("Input n and m: ");
	scanf("%d %d", &n, &m);

	/* Compute gcd using Euclid's algo and output it */
	t = compute_gcd_Euclid(n ,m);
	printf("The gcd is: %d\n", t);

	/* Compute gcd using algo based on definition, and output it */
	t = compute_gcd(n ,m);
	printf("The gcd is: %d\n", t);
}


/* Computes the gcd of two numbers using the definition of gcd:
 * The largest number dividing both the input numbers. The function
 * returns the gcd.
 */
int compute_gcd(int n, int m)
{
	int t;

	for (t = n; 1; t--)
		if ((n % t == 0) && (m % t == 0)) /* t is the gcd */
			return t;
}

/* Computes the gcd using Eucild's algorithm */
int compute_gcd_Euclid(int n, int m)
{
	int t;

	for (; 1; ) {

		if (n < m) { /* Swap to make n at least as large as m */
			t = m;
			m = n;
			n = t;
		}

		if (n % m == 0) /* m is the gcd */
			return m;
		else /* replace n by n (mod m) */
			n = n % m;
	}
}