[PHP]最小公倍数・最大公約数を求める（ユークリッドの互除法）

by  in PHP
このエントリーをはてなブックマークに追加
Pocket

最小公倍数・最大公約数を求めるにはユークリッドの互除法に基づくアルゴリズムを利用します。
なぜこの式で計算できるのかについては数学に詳しい人に聞いて下さい。 

//最大公約数
function gcd($m, $n){
	if($n > $m) list($m, $n) = array($n, $m);
	
	while($n !== 0){
		$tmp_n = $n;
		$n = $m % $n;
		$m = $tmp_n;
	}
	return $m;
}

//最小公倍数
function lcm($m, $n){
	return $m * $n / gcd($m, $n);
}

参考

Similar Posts:




コメントを残す

メールアドレスが公開されることはありません。 ※ が付いている欄は必須項目です