首先,根据丑数的定义,n≤0n \le 0n≤0 时一定不是丑数,直接返回 false.
然后根据定义,当 n>0n>0n>0 时如果 nnn 是丑数,那么它一定可以写成 n=2a×3b×5c(a≥0b≥0c≥0)n = 2^a \times 3^b \times 5^c (a\ge0b\ge0c\ge0)n=2a×3b×5c(a≥0b≥0c≥0) 的形式,而当 a=b=c=0a=b=c=0a=b=c=0 时 n=1n = 1n=1,正是第一个丑数.
于是就可以递归求解:
当 n 不能被 222,333,555 整除时,若 n=1n=1n=1,则说明 nnn 不包含其他质因数,是丑数;否则,说明 nnn 包含其他质因数,不是丑数.