欧几里德算法-求最贵族约数

欧几里德算法--求最大公约数

欧几里德算法又称为辗转相除法，两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。如44和8的最大公约数是4，而44-8=36和8的最大公约数也是4.

/**
 * @author Bangwen Chen
 *	Description:求最大公约数，同样的思想可用于求两数是否互素（即m和n的最大公约数是否为1）
 * 2013年9月30日
 */
public class EuclideanAlgorithm {

	public static void main(String[] args) {
		System.out.println(new EuclideanAlgorithm().RecursiveMethod(44,8));
		
		System.out.println(new EuclideanAlgorithm().ModMethod(44,8));

	}
	

	public int RecursiveMethod(int m,int n ){
		if(n==0){
			return n;
		}
		return RecursiveMethod(n,m%n);
	}
	public int ModMethod(int m,int n){
		int temp;
		while(n != 0){
			temp = n;
			n = m%n;
			m = temp;
		}
		return m;
	}
}

欧几里德算法-求最贵族约数

相关推荐