最大公约数之欧几里得算法证明与java实现

1 算法的自然语言描述

计算两个非负整数 p 和 q 的最大公约数：若 q 是0，则最大公约数为 p 。否则，将 p 除以 q 得到的余数 r ， p 和 q 的最大公约数即为 q 和 r 的最大公约数。

2 算法证明

注：gcd（a， b）即为 a 与 b 的最大公约数

3 算法java实现

public class gcd {

	public static void main(String[] args) {
		System.out.println("最大公约数为：" + getgcd(15, 6));
	}
	
	public static int getgcd(int p, int q){
		System.out.println("p:" + p + " q:" + q);
		if(q == 0) return p;
		int r = p % q;
		return getgcd(q, r);
	}
	
}

注：算法思想与实现主要参考谢云路译的《算法》（第四版）。