判断一个整数是不是丑数

一个正整数，如果其因子只包含 2、3、5 中的任意一个，那么这个数就是丑数。根据这个定义，我们可以从小到大枚举每一个数，然后判断其是否为丑数，直到找到第 $n$ 个丑数为止。

具体实现方式如下：

1. 特判：如果 $n \leq 0$，直接返回 false。

2. 初始化三个指针 $p_2 = p_3 = p_5 = 0$，表示当前 2、3、5 的倍数要乘以的丑数下标，初始值都为 0。

3. 初始化一个数组 $ugly[n]$，用来存储前 $n$ 个丑数。

4. 将 $ugly[0]=1$，表示第一个丑数为 1。

5. 从 $ugly[1]$ 开始遍历数组，计算下一个丑数。计算方式为：$ugly[i] = \min(ugly[p_2] \times 2, ugly[p_3] \times 3, ugly[p_5] \times 5)$。

6. 如果 $ugly[i]$ 能够被 2、3、5 中的任意一个整除，则将对应指针 $p_2$、$p_3$ 或 $p_5$ 加 1。

7. 最后返回 $ugly[n-1]$ 即可。

下面是具体实现代码：

相关问题

用c语言实现判断一个整数是不是丑数

一个正整数如果只包含质因子2,3,5中的若干个数，则称其为丑数。例如，6、8都是丑数，但14不是，因为它包含了质因子7。现在让我们用C语言实现判断一个整数是否是丑数的代码。

#include <stdio.h>

int isUgly(int num) {
    if(num <= 0) return 0;
    while(num % 2 == 0) num /= 2;
    while(num % 3 == 0) num /= 3;
    while(num % 5 == 0) num /= 5;
    return num == 1;
}

int main() {
    int n;
    printf("请输入一个整数：");
    scanf("%d", &n);
    if(isUgly(n)) {
        printf("%d是丑数\n", n);
    } else {
        printf("%d不是丑数\n", n);
    }
    return 0;
}

以上代码中，我们定义了一个 `isUgly` 函数，该函数接受一个整数作为参数，如果该整数是丑数，则返回1，否则返回0。在函数中，我们使用了三个while循环来连续除以2、3、5，直到除不尽为止，如果最终结果是1，则说明原数只包含质因子2、3、5，即为丑数。在主函数中，我们可以读入一个整数，然后调用 `isUgly` 函数来判断该数是否为丑数并输出结果。

输入一个整数判断是否为丑数，python

def isUgly(num: int) -> bool:
if num <= 0:
return False
while num % 2 == 0:
num //= 2
while num % 3 == 0:
num //= 3
while num % 5 == 0:
num //= 5
return num == 1

# 测试
print(isUgly(6)) # True
print(isUgly(14)) # False