最小公倍数をPHPで求めるには

PHPで最小公倍数を求めるプログラムを作りたいのですが、
アルゴリズムをお教えください。

尚、PHPを実行するレンタルサーバーの関係で
gmp関数群は使えません。

No.2 ベストアンサー 回答者： noname#111181 回答日時： 2010/03/14 23:43

面倒なのでソースコードを書きました。

エラー処理はしていません。

---------------------
<?php
//最大公倍数を求める（ユークリッドの互除法）
function gcd($m, $n) {
while ($m % $n != 0) {
$temp = n;
$n = $m % $n;
$m = $temp;
}
return $n;
}

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

//サンプル
$m = 27;
$n = 18;
$l = lcm($m, $n);
echo "$m と $n の最小公倍数は $l です．";
?>

この回答へのお礼

ご回答ありがとうございます。

お礼日時：2010/03/15 15:41

No.1 回答者： mtaka2 回答日時： 2010/03/14 23:17

2数をかけてから最大公約数で割ると、最小公倍数になります。

PHPではありませんが、
http://www12.plala.or.jp/dokugaku/algo/lcm.html
なんかが参考になるでしょう。

最大公約数を求めるアルゴリズム、ユークリッドの互除法について
詳しく知りたい場合は、
http://ja.wikipedia.org/wiki/%E3%83%A6%E3%83%BC% …
をどうぞ。

この回答へのお礼

ご回答ありがとうございます。

お礼日時：2010/03/15 15:42