Algorithms - 最大公约数(greatest common divisor)-欧几里得(Euclid) 算法 及 代码

最大公约数(greatest common divisor)-欧几里得(Euclid) 算法

本文地址: http://blog.csdn.net/caroline_wendy/article/details/17012455

最大公约数(欧几里得算法(Euclid's Algorithm))是比较经典的算法; 

主要方法: 递归相除, 求余数, 直至余数为0, 返回最后一个除数, 即可; 这样, 最早的两个数, 就都包含此除数; 

此算法不需要指定大小顺序, 当顺序相反时, 第二次的余数就是较大的数;

代码如下:

/*
 * algorithms.java
 *
 *  Created on: 2013.11.28
 *      Author: Spike
 */

/*eclipse kepler, javase-1.7*/

public class algorithms {
	//最大公约数
	public static int gcd (int p, int q)
	{
		if (q == 0) return p;
		int r = p % q;
		return gcd(q, r);
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int res = gcd(42, 70);
		System.out.println("Hei, the gcd is " + res + ". ");
	}
}