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

1 算法的自然语言描述

计算两个非负整数 pq 的最大公约数:若 q 是0,则最大公约数为 p 。否则,将 p 除以 q 得到的余数 rpq 的最大公约数即为 qr 的最大公约数。

2 算法证明

注:gcd(a, b)即为 a 与 b 的最大公约数
最大公约数之欧几里得算法证明与java实现

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);
	}
	
}

注:算法思想与实现主要参考谢云路译的《算法》(第四版)。