给你打个比喻吧：你英雄救美了，美女想要回报你，你想要1000块感谢费，然而美女却想要以身相许????，懂了吧，同样都是回报，只是用了不一样的形式，辗转相除法也是这样，你两个数的最大公约数不容易求，我就用另外两个简略的数来解决。
废话不多说，看定理。
定理：
辗转相除 能够求最大公约数，顾名思义，重复的除，最终失去两数的最大公约数。
首先咱们来剖析下定理：
定理：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。最大公约数（Greatest Common Divisor）缩写为GCD。
gcd(a,b) = gcd(b,a mod b) (无妨设a>b 且r=a mod b ,r不为0)
文字不好了解，举个实例：
134 / 18 = 7 ... 8
18 / 8 = 2 ... 2
8 / 2 = 4 ... 0
看清了吧，是不是和定理截然不同，所以咱们要找最大公约数，而134 /18的和8 / 2的最大公约数相等，所以咱们只需要求出8 / 2的最大公约数，是不是就是结尾说的换了两个数再求，而咱们要晓得，因为两数相除，余数为0，其除数必然为最大公约数，所以这里的2也就是咱们要找的138 / 18 的最大公约数。至于证实，百度搜寻，都有。次要证实思路就是，有a/b余r一式， 先假如y为a，b的公约数，再证实b,r的公约数也为y。
思路：
通过定理咱们晓得，要计算两数最大公约数，咱们只须要始终递归就行了，直到余数为0，最大公约数就是较小的那个数（除数）。递归置信大家都理解过吧，必然有一进口，保障程序进行或返回，那么这里的进口条件就是下面例子的2，即余数为0。程序就是先找出输出参数谁打谁小，再判断余数是否为0（进口），再递归。代码用java写的，其实没啥差异，也没用api，思路都一样，格局不一样罢了。
代码：
所以咱们开始写代码了：
private static void method4(int m, int n, int ji) { //相比拟两个数，把较小的那个数赋值给smallNum; int smallNum = (m > n ? n:m); int bigNum = (m > n ? m:n); if ( n < 0 || m < 0 ){ System.out.println("输出有错，完结了"); }else{ //余数为0，smallNum就是那个最大公约数 if (bigNum % smallNum == 0){ System.out.println("最小公倍数"+(ji / smallNum)+" 最大公约数"+smallNum); //我写了几种办法，不便调用，所以返回的空 return; } method4(smallNum,bigNum % smallNum, ji); } }通过定理咱们晓得较小数为除数吧，所以咱们间接每次递归时，就把较小那个值找进去。而后把它变成除数，不就行了吗。
什么你还没学递归，不要紧，我还有一种办法，就是while循环，while循环就不必判断谁大谁小了，因为小数%大数=小数自身，代码搞起来：
private static void method2(int m ,int n,int ji) { while(true){ if ((m = m % n) == 0){ System.out.println("最大公约数"+n); System.out.println("最小公倍数"+(ji / n)); System.exit(0); } if ((n = n % m) == 0) { System.out.println("最大公约数"+m); System.out.println("最小公倍数"+(ji / m)); System.exit(0); } } }其实我还有一种枚举的算法，就不写了。当然求解最大公倍数，辗转相除还不是最优，还有更优，大家能够搜搜看。如果有工夫，我在补充其余的算法。