PHP编程求最大公约数与最小公倍数的方法示例
最大公约数
方法一:辗转相除法
辗转相除法,也叫欧几里得算法,是一种快速求两个正整数最大公约数的方法。其基本思想是用较大数除以较小数,再用出现的余数去除除数,不断重复这个过程,直到余数为零为止,此时的除数即为两个数的最大公约数。
示例代码:
function gcd($a, $b)
{
if ($b == 0) {
return $a;
} else {
return gcd($b, $a % $b);
}
}
echo gcd(30, 42); // 输出6
方法二:更相减损法
更相减损法是用来求两个正整数的最大公约数的另一种方法。其基本思想是不断用两数中较大数减去较小数,然后将所得的差与较小数比较,如果相等,则当前较小数即为最大公约数,否则继续执行减操作,直到两个数相等时结束。
示例代码:
function gcd2($a, $b)
{
while ($a != $b) {
if ($a > $b) {
$a -= $b;
} else {
$b -= $a;
}
}
return $a;
}
echo gcd2(30, 42); // 输出6
最小公倍数
方法一:利用最大公约数求解
求两个正整数的最小公倍数,可以通过它们的最大公约数来求解。最小公倍数等于两数之积除以最大公约数。
示例代码:
function lcm($a, $b)
{
$gcd = gcd($a, $b);
return $a * $b / $gcd;
}
echo lcm(30, 42); // 输出210
方法二:穷举法
方法二是一种效率较低的求解方法,它的基本思想是从两数的较大值开始想要得到的最小公倍数是学生概率和两个数的积。
示例代码:
function lcm2($a, $b)
{
$max = max($a, $b);
while (true) {
if ($max % $a == 0 && $max % $b == 0) {
return $max;
}
$max++;
}
}
echo lcm2(30, 42); // 输出210
以上是求解最大公约数和最小公倍数的两种方法以及相应的示例代码。
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:PHP编程求最大公约数与最小公倍数的方法示例 - Python技术站