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

Facebook にシェア
Delicious にシェア
LINEで送る
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:




  • This entry was posted in PHP and tagged . Bookmark the permalink.

    コメントを残す

    メールアドレスが公開されることはありません。