PHP finds common multiples of consecutive numbers-PHP Tutorial-php.cn

Table of Contents

Reply content:

Home

Backend Development

PHP Tutorial

PHP finds common multiples of consecutive numbers

Jul 06, 2016 pm 01:51 PM

php

Why are there 60 minutes in an hour instead of 100 minutes? This is caused by historical habits. But it's not purely accidental: 60 is an excellent number, and it has many factors.
In fact, it is a multiple of every number from 1 to 6. That is, 1,2,3,4,5,6 can all divide 60.

We want to find the smallest integer that can divide every number from 1 to n.

Don’t underestimate this number, it may be very large, for example, n=100, then the number is:
69720375229712477164533808935312303556800

Please write a program to find the least common multiple of 1~n for n (n<100) input by the user.

For example: User input: 6 Program output: 60

User input: 10 Program output: 2520

Please use PHP to implement this method. It is best if you can explain the idea first

Reply content:

Why are there 60 minutes in an hour instead of 100 minutes? This is caused by historical habits. But it's not purely accidental: 60 is an excellent number, and it has many factors.
In fact, it is a multiple of every number from 1 to 6. That is, 1,2,3,4,5,6 can all divide 60.

We want to find the smallest integer that can divide every number from 1 to n.

Don’t underestimate this number, it may be very large, for example, n=100, then the number is:
69720375229712477164533808935312303556800

Please write a program to find the least common multiple of 1~n for n (n<100) input by the user.

For example: User input: 6 Program output: 60

User input: 10 Program output: 2520

Please use PHP to implement this method. It is best if you can explain the idea first

The general idea is: first find the least common multiple of two numbers (in which the euclidean division method is used to find the greatest common divisor of the two numbers, and then use the formula to get the least common multiple), then find the least common multiple of the next number, and so on Until the last number. .

The code is as follows: (It should be noted that if the int type of php is too large, it will cause overflow)

<code>function xmzenger($n)
{
    //1和2的最小公倍数
    $res = 2;
    for ($i=1; $i &lt;= $n; $i++) { 
        //$res为$a之前的数的最小公约数，赋予$b继续和$a求最小公倍数
        $a = $i;
        $b = $res;
        //$c为两数的乘积
        $c = $a * $b;
        //交换值使$a总是比$b大
        if($a &lt; $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);</code>

Copy after login

Statement of this Website

The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn