php 求连续数的公倍数

Question

为什么1小时有60分钟，而不是100分钟呢？这是历史上的习惯导致。 但也并非纯粹的偶然：60是个优秀的数字，它的因子比较多。
事实上，它是1至6的每个数字的倍数。即1,2,3,4,5,6都是可以除尽60。

我们希望寻找到能除尽1至n的的每个数字的最小整数。

不要小看这个数字，它可能十分大，比如n=100, 则该数为：
69720375229712477164533808935312303556800

请编写程序，实现对用户输入的 n （n<100）求出1~n的最小公倍数。

例如： 用户输入： 6 程序输出： 60

用户输入： 10 程序输出： 2520

求用php实现此方法，最好能先讲下思路

Answer 1

大概思路是：先求两个数的最小公倍数（其中用到辗转相除法求两个数的最大公约数，再根据公式来得到最小公倍数），再跟下一个数求最小公倍数，依次直到最后一个数。。

代码如下：（需要注意的是php 的int类型过大会溢出的问题）

function xmzenger($n)
{
    //1和2的最小公倍数
    $res = 2;
    for ($i=1; $i <= $n; $i++) { 
        //$res为$a之前的数的最小公约数，赋予$b继续和$a求最小公倍数
        $a = $i;
        $b = $res;
        //$c为两数的乘积
        $c = $a * $b;
        //交换值使$a总是比$b大
        if($a < $b){
            $r = $a;
            $a = $b;
            $b = $r;
        }
        //辗转相除法求两个自然数的最大公约数
        while (true) {
            $r = $a % $b;
            //如果$r为0则$b为最大公约数
            if($r == 0){
                //小学学过的公式：“(a,b)[a,b]=ab(a,b均为整数)”
                $res = $c/$b;
                break;
            }else{
                $a = $b;
                $b = $r;
            }
        }
    }

    return $res;
}

echo xmzenger(10);