约分方法与最大公约数

约分

用两个数分别除以这两个数的最大公约数

求最大公约数

辗转相除法

int gcd(int a, int b) 
{
    int r;
    while (b != 0) 
    {
        r = a % b; 
        a = b; 
        b = r;
    }
    return a;
}

更相减损术

int gcd(int a,int b)
{
	if(a==b)
		return a;
	if(a>b)
		return gcd(a-b,b);
	else
		return gcd(b-a,a);
}

差别

后者避免大数取模运算，但运算次数更多