(おさらいを兼ねて)数が2個の場合

最大公約数

2数の剰余が0になったら、『割られる数』＝『最大公約数』・・・①
そうでなければ2数を『割る数』と『2数の剰余』として①を再度計算

ということらしいので、以下のような処理が多いかと思います。

math.php

function gcd($a, $b) {
    if ($b === 0)
        return $a;

    return gcd($b, $a % $b);
}

echo gcd(1071, 1029); // 21

最小公倍数

最小公倍数を見ると、2数に限っては

『最小公倍数』と『最大公約数』を掛け合わせると、2数の積になる

という性質があるみたいですね～。

つまるところ、『2数の積』を『最大公約数』で割ったものが『最小公倍数』
ということなので、gcd関数を流用して以下のような感じに。

math.php

function gcd($a, $b) {
    if ($b === 0)
        return $a;

    return gcd($b, $a % $b);
}

function lcm($a, $b) {
    return $a * $b / gcd($a, $b);
}

echo lcm(1071, 1029); // 52479

数が3個以上の場合は？

本題はこっち。

まず調べる数が不定なので、引数を配列に変更してみます。

次にアルゴリズム部分ですが、数が増えたとは言っても
変数a,b,cについて

『aとbとcの最大公約数』　＝　『aとbの最大公約数』と『c』　の最大公約数
『aとbとcの最小公倍数』　＝　『aとbの最小公倍数』と『c』　の最小公倍数

という関係になるので、やはり再帰にすれば問題はなさそうです。

というわけで

クラスにしたりなんだりを経て、できあがったものがこちらです！
(キュー〇ー3分クッキングのテーマに乗せて)
※gitに移しました

法則に沿っているだけなので、コードの実装の詳細は省きますが
テクニックっぽいものとしては以下です。

必要に応じて参照渡しで


// 値渡し
ini_set('memory_limit', '1024M');
echo  MathAppend::gcd(array_fill(0,6500,1)); // Fatal error: Allowed memory size of 1073741824 bytes exhausted...

// 参照渡し
ini_set('memory_limit', '16M');
echo  MathAppend::gcd(array_fill(0,13000,1)); // 1

使用メモリを1/64にして、更に要素数を倍にしても余裕で処理できる！　すごい！

calcGCD/calcLCMの中で、配列長を変更しているため
値渡しだとその都度新しい配列が生成されてしまうので
特に要素数が多い場合、参照渡しにしないと厳しいです。

getGCD/getLCMの方も参照渡しを試してはみたのですが、
処理時間が増加するという結果になったのでお蔵入りに。

配列からの値の取り出し方

2数を取得する際、indexを0と1でベタ書きできるので
コード中のarray_popの部分は、最初array_shiftで作ってました。
が、


$a = array();
for ($i=1;$i<=6500;$i++) {
    $a[] = $i;
}

// array_shift
$s = microtime(true);
MathAppend::gcd($a);
echo (microtime(true) - $s); // 2.04~2.05secくらい

// array_pop
$s = microtime(true);
MathAppend::gcd($a);
echo (microtime(true) - $s); // 1.94~1.95secくらい

と、処理時間にそれなりの差が出るようなのでarray_popに変更しました。

array_shiftが『全要素が前詰めされる』のに対して
array_popだと『最後の1要素がなくなる』だけですしね！

まとめ

更にメモリ消費を抑えたり、処理時間を減らしたりなどのコード面の課題や
実はもっと単純なアルゴリズムがあるかも！　などの数学面の課題もありますが～

数学アルゴリズムをコードに落とすのって意外と楽しいです。

みんなもアルゴリズム使ってね！

3つ以上の数の最大公約数と最小公倍数