丑数的判断

说法一：把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但7、14不是，因为它们包含质因子7。 习惯上我们把1当做是第一个丑数。

前20个丑数为：1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36。

说法二：对于一给定的素数集合 S = {p1, p2, ..., pK},考虑一个正整数集合，该集合中任一元素的质因数全部属于S。这个正整数集合包括，p1、p1*p2、p1*p1、p1*p2*p3...(还有其它)。该集合被称为S集合的“丑数集合”。注意：我们认为1不是一个丑数，丑数集合中每个数从小到大排列，每个丑数都是素数集合中的数的乘积。（如S={2，3，5}时，对应丑数集合为U={2，3，4，5，6，9，10，15，25，30}）

1.问题描述

把只包含质因子2，3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但7、14不是，因为它们包含质因子7。 习惯上我们把1当做是第一个丑数。要求：输入一个数，判断是否是丑数或者输出某一范围内的所有丑数。

2.解题思路

• 由于因子只能是2，3，5这三个特殊数字，所以可以把这三个数字做成列表进行判断
• 遍历小于该数的除了1以外的最小因子，判断其是否在2，3，5之间
• 若不在内部可以直接输出其不是丑数
• 若是2，3，5之一，则可以使用剩下的数，再次判断其最小因子，直至数变成2，3，5后，可确定其是丑数，循环

3.解题方法

a = [2, 3, 5]

def UglyNumber(m):
    n = m
    while True:
        if n == 1:
            return f'{m}是丑数'
            break
        elif n in a:
            return f'{m}是丑数'
            break
        else:
            b = 0
            for i in a:
                if n % i != 0:
                    b += 1
                else:
                    n /= i
                    continue
            if b == 3:
                return f'{m}不是丑数'
                break


m = int(input('请输入整数:'))
print(UglyNumber(m))

第1行： 将三个特殊数字2，3，5建立成一个列表

第3行： 创建丑数函数UglyNumber，并输入m作为它的变量

第4行： 使用n来替代m的值，n用于变化，m用于表示原数

第6-11行： 判断n是否为1，2，3，5之间的一个，若是，打印m是完数且结束循环

第12-13行： 若n不是1，2，3，5之间的一个，定义b=0，用处稍后介绍

第14-16行： 使用for循环遍历2，3，5这三个数，判断2，3，5是否是其因数，若不是，b的值加一

第17-19行： 只要2，3，5之间有一个数为n的因数，则替换n为n除以因数之后的值，并使用continue结束本次循环，进行下次循环判断n是否是丑数

第20-22行： 如果b=3，则表示2，3，5之间任何一个数都不是n的因子，则n不是丑数，那么m也不是丑数

第25-26行： 输入一个整数并将其值返回给m，打印其是否是丑数

代码运行结果为：

4.小思考

那么如果要求输出一万以内的所有丑数，应该如何修改呢？