Here is the Euclid's algorithm (faster and more efficient, as
you don't enumerate all numbers for finding the GCD) :
/***************** START FUNCTION *****/
int Euclid(int m, int n)
{
int t;
while (m > 0)
{
t = m;
m = n % m; /* n mod m */
n = t;
}
return n;
}
/************** END OF FUNCTION ******/
Thus given m (numerator) and n (denominator) it will
return the GCD.
Dividing m and n by this number (GCD) will reduced the
fraction.
for example :
Euclid(5, 15) will return 5. /* then divide both 5 and 15 with 5, you will get 1/3 */
Euclid (16, 20) will return 4. /* dividing both 16 and 20 with 4, you will get 4/5 */
Euclid (4, 8) will return 4.
Euclid (3, 7) will return 1.