Question

用c语言，怎么对一个分数约分成最简分数

除了辗转相除法求出最大公约数，别的方法怎么做，还有怎么求时间和空间复杂度，求给我个思路。谢谢

Answer 1

群举法，把两个数a,b从1到较小的数用for（i=1;i<=a;i++）整出来，然后用if（a%i==0&&b%i==0）判断两个数求余是否为零，如果为零，就让两个数除以这个符合的i值，a=a/i,b=b/i，然后继续重新循环，知道从1到a没有符合的数字为止！！！

Answer 2

群举法，把两个数a,b从1到较小的数用for（i=1;i<=a;i++）整出来，然后用if（a%i==0&&b%i==0）判断两个数求余是否为零，如果为零，就让两个数除以这个符合的i值，a=a/i,b=b/i，然后继续重新循环，知道从1到a没有符合的数字为止！！！

Answer 3

还有更像减损数 即用大的数减小的 一直循环直到为0，此时的减数即为最大公约数