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

質問

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

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

回答No.2

noname#111181 · ベストアンサー

面倒なのでソースコードを書きました。
エラー処理はしていません。

---------------------
<?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 です．";
?>

お礼

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

回答No.1

mtaka2

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

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

最大公約数を求めるアルゴリズム、ユークリッドの互除法について
詳しく知りたい場合は、
http://ja.wikipedia.org/wiki/%E3%83%A6%E3%83%BC%E3%82%AF%E3%83%AA%E3%83%83%E3%83%89%E3%81%AE%E4%BA%92%E9%99%A4%E6%B3%95
をどうぞ。

お礼

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