辗转相除法求两个数的最大公约数
今天看了一个题，就是求两个数的最大公约数和最小公倍数。觉得挺有意思的就自己整了整。
这个题有一种简单易懂的算法，就是先选出两个数较小的那个数，然后较大的数对较小的数取余，并判断余数是否为零，如果不为零则较小的这个数自减，然后较大的数再对其取余知道余数为零为止。当余数为零时较小的数现在就是最小公约数。最小公倍数的求法就比较简单了：两者的积除以最大公约数就是最小公倍数，所以关键还是求最大公约数。
但这种方法，计算量太大，效率低。然后我又上网搜了一下，发现了一种比较高效的算法，就是我们今天的主角：辗转相除法。
首先我们来看一下辗转相除法的基本思想：它也是要先比较两个数的大小，然后在用较大的数对较小的数取余，如果余数不为零，则在用较小的数对上一步得到的余数取余，在判断余数是否为零，如果不为零则在用第一步得到的余数对第二步得到的余数再取余，直到余数为零为止，当余数为零时此时的除数即为最大公约数。
看着是有点绕，咱们举个例子看一下：求12和20的最大公约数 20%12=8 12%8=4 8%4=0 这时就可以得到两数的最大公约数为4，
简而言之，辗转相除法就是不断的用前一个式子的除数对前一个式子的余数取余直到等零为止。此时的除数就是我们要找的最大公约数。
下面是我写的JAVA代码：
import java.util.Scanner; public class Mathes{ public static void main(String[] args){ Scanner input = new Scanner(System.in); System.out.print("请输入第一个数："); int a = input.nextInt(); System.out.print("请输入第二个数："); int b = input.nextInt(); int c = a * b;//求最小公倍数要用到两者之积，我们先将其放在c中保存 int d; //先判断a,b的大小，并把较大的数给a if(b > a){ int temp = a; a = b; b = temp; } //以下代码是对辗转相除法的实现 do{ a = a % b;//把两者的余数赋给a //判断余数是否为零，不等零就接着取余，等零就输出 if(a == 0){ System.out.print("最大公约数为：" + b); System.out.println("\n最小公倍数为：" + c / b); break; } b = b % a; if(b == 0){ System.out.print("最大公约数为：" + a); System.out.println("\n最小公倍数为：" + c / a); break; } }while(true); } }下面是我输入的两组数及其执行结果： 有不当之处，还请大佬多多指教！java小白在此敬上。
