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:
69720375229712477164533808935312303556800Please 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
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:
69720375229712477164533808935312303556800Please 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 <= $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);</code>