辗转相除求最大公因数（greatest common factor）欧几里得 博客分类： php 辗转相最大公因数欧几里得算法

 

 

/**
 * 得到最大公因数
 *
 */
function getGreatestCommonFactor($a, $b){
	if($a < 0 || $b < 0){
		return false;
	}
	if($b > $a){
		return getGreatestCommonFactor($b, $a);
	}else{
		if($a % $b == 0){
			return $b;
		}else{
			return getGreatestCommonFactor($b, $a % $b);
		}
	}
}