php实现丑数

丑数定义

丑数是指只包含质因数2、3或5的正整数。1通常被视为第一个丑数。例如，前10个丑数为1, 2, 3, 4, 5, 6, 8, 9, 10, 12。

判断丑数的方法

要判断一个数是否为丑数，可以不断将其除以2、3、5，直到无法整除为止。如果最终结果为1，则该数是丑数；否则不是。

function isUgly($num) {
    if ($num <= 0) {
        return false;
    }
    $factors = [2, 3, 5];
    foreach ($factors as $factor) {
        while ($num % $factor == 0) {
            $num = $num / $factor;
        }
    }
    return $num == 1;
}

生成第n个丑数

要生成第n个丑数，可以使用动态规划的方法。维护三个指针分别对应乘以2、3、5的最小丑数，每次选择最小的乘积作为下一个丑数。

function nthUglyNumber($n) {
    $uglyNumbers = array_fill(0, $n, 0);
    $uglyNumbers[0] = 1;
    $i2 = $i3 = $i5 = 0;
    $nextMultipleOf2 = 2;
    $nextMultipleOf3 = 3;
    $nextMultipleOf5 = 5;

    for ($i = 1; $i < $n; $i++) {
        $nextUglyNumber = min($nextMultipleOf2, $nextMultipleOf3, $nextMultipleOf5);
        $uglyNumbers[$i] = $nextUglyNumber;

        if ($nextUglyNumber == $nextMultipleOf2) {
            $i2++;
            $nextMultipleOf2 = $uglyNumbers[$i2] * 2;
        }
        if ($nextUglyNumber == $nextMultipleOf3) {
            $i3++;
            $nextMultipleOf3 = $uglyNumbers[$i3] * 3;
        }
        if ($nextUglyNumber == $nextMultipleOf5) {
            $i5++;
            $nextMultipleOf5 = $uglyNumbers[$i5] * 5;
        }
    }
    return $uglyNumbers[$n - 1];
}

示例用法

// 判断一个数是否为丑数
var_dump(isUgly(6)); // 输出: bool(true)
var_dump(isUgly(14)); // 输出: bool(false)

// 获取第n个丑数
echo nthUglyNumber(10); // 输出: 12

注意事项

• 输入为负数或0时，直接返回false。
• 动态规划方法的时间复杂度为O(n)，空间复杂度为O(n)。