怎样最快找出两个数的最大公因数?

问题描述:

怎样最快找出两个数的最大公因数?
最好举例说明思路...

辗转相除法:如果两个数有公因数,那么这个公因数也是这两个数的差的公因数.你按照这个精神一定能学好这个知识.不妨设这两个数分别为M和N,且M>N;其公因数为k.则:M=km,N=kn;M-N=(m-n)k.从而将问题转化为较小的一组数:N和M-N求公因数的问题.如此继续,一定能求出k,从而也就定出了两个数的公因数.