怎么求最大公约数
3个回答
展开全部
求最大公约数，可以有很多种方法。辗转相除法是效率最高的一种。
辗转相除法：以大数除以小数，如果能整除，那么小数就是所求的最大公约数（gcd）。否则就用余数来除刚才的除数；
再用这新除法的余数去除刚才的余数。依此类推，直到一个除法能够整除，这时作为除数的数就是所求的最大公约数。即：gcd（x,y）表示x与y的
最大公约数，有gcd(x,y)=gcd（y,x%y），如此便可把原问题转化为求两个更小数的公约数，直到其中一个数为0，剩下的另外一个数就是两者的最
大公约数。
辗转相除法：以大数除以小数，如果能整除，那么小数就是所求的最大公约数（gcd）。否则就用余数来除刚才的除数；
再用这新除法的余数去除刚才的余数。依此类推，直到一个除法能够整除，这时作为除数的数就是所求的最大公约数。即：gcd（x,y）表示x与y的
最大公约数，有gcd(x,y)=gcd（y,x%y），如此便可把原问题转化为求两个更小数的公约数，直到其中一个数为0，剩下的另外一个数就是两者的最
大公约数。
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
推荐律师服务：
若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询
