java 算法 求最大公约数

本人菜鸟一枚，突然之间，偶得上帝灵光闪现，突然感觉自己日子过的太轻松，然后，自杀式的买了一本算法书，从今天开始了地狱般的生活；
算法第一章讲的是，欧几里得算法求其目的就是找到两个数的最大公约数，然后，我马上关上书，喝了一杯茶，脑海中回想着，这都是啥？？对于一个数学从来都没有及格的我来说，想放弃
吐槽完毕，说正题，何为最大公约数，直接百度，谷歌，360，通过一系列的查询，来个官方版的

这。。。。是啥？没看懂
其实，最大公约数，即为能够同时被两个整数除的最大的数，还不懂？上图

如果还不懂，请关闭本页面，然后，打开百度，找个视频看一下吧！我无能为力了。
欧几里得算法：又称辗转相除法，用于计算两个正整数，a,b 的最大公约数，计算原理依赖于下面的定理
定理：gcd(a,b) = gcd(b,a mod b)(a>b 且 a mod b 不为 0)
有人会问，mod 是啥？这个是求余啊！ _MOD_是求余运算符，例如 a mod b=c，表明 a 除以 b 余数为 c
证明：a 可以表示成 a = kb +r 则 r=a mod b
假设 d 是 a,b 的一个公约数，则有 d|a ,d|b 而，r=a-kb 因此 d|r
因此 d 也是(b,a mod b)的公约数
因此(a,b)和(b,a mod b)的公约数是一样的，最大的公约数也必然相等

看懂没？我也没咋看懂

分析一下吧，
假设 x>y x 和 y 的最大公约数用 f(x,y)表示
假设 x/y = a
x%y = b
所以 ay+b = x
因为 a 为 x 除以的整数部分，b 为 x 除以 y 的余数部分，所以 ay+b = x
将上面的调换一下 b= x-a*y
因为 x 和 y 都能被 f(x,y)整数 所以 f(x,y)是 x 和 y 的最大公约数
所以 b 也同样能被 f(x,y)整除 即 x 和 y 的最大公约数 f(x,y)它是 b 的约数，所以求 x 和 y 的最大公约数也就相当于求 y 和 b 的最大公约数（因为，这里 x>y 而且 x%y 肯定小于 y，所以，这样一来，我们的范围缩小了）
所以 欧几里得公式也就这么来了
f(x,y) = f(y,x%y)
所以，这个算法就是不停的迭代，直到找出 x%y=0 的时候，停止迭代，那个时候，最大的公约数就是 y 了

下面为，书中的一个求最大公约数的案例

/**
 * 算法分析： 
 * 计算两个非负数p和q的最大公约数，若q是0，则最大的公约数是p，否则，p除q，得到余数r，p和q最      
 * 大公约数即为q和r的最大公约数 
 * Created by huxd on 2017/9/14. 
 */
 
	//欧几里得算法
 public  static int gcd(int p ,int q){
	 if(q == 0) return p;
	 int r = p%q;
	 return gcd(q,r);
}
​

实际代码

package Test1;
import java.util.*;
public class Tset1 {

public static void (String[] args) {
Scanner scan = new Scanner(System.in);// 接收控制台输入的信息

  System.out.print("请输入第一个整数：");
 int x = scan.nextInt(); // 取出控制台输入的信息

  System.out.print("请输入第二个整数：");
 int y = scan.nextInt(); // 取出控制台输入的信息

  System.out.println(gcd(x, y));// 调用maxCommonDivisor()方法
  }

	public static int gcd(int x, int y) {

		// 防止输入为0
  if (x == 0 || y == 0) {
			return 0;
  }
		//添加一个保证 x>y
  if (x < y) {
			int temp = x;
  temp = y;
  y = x;
  }
		//算法实现
  if (x % y == 0) {
			return y;
  } else {
			return gcd(y, x % y);
  }
	}
}
​