丑数

题意

写一个程序来检测一个整数是不是丑数

丑数的定义是,只包含质因子 2, 3, 5 的正整数。比如 6, 8 就是丑数,但是 14 不是丑数以为他包含了质因子 7。

注意事项

可以认为 1 是一个特殊的丑数。

样例

给出 num = 8,返回 true
给出 num = 14,返回 false

思路

使 sum 依次对 2, 3, 5 相除,直到与 2, 3, 5 的余数不为 0,最终 sum 为 1,则代表该数只能被 2, 3, 5整除,返回 true,反之返回 false

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
/*
* @param num: An integer
* @return: true if num is an ugly number or false
*/
public boolean isUgly(int num) {
if (num == 1)
return true;

while (num >= 2 && num % 2 == 0) num /= 2;
while (num >= 3 && num % 3 == 0) num /= 3;
while (num >= 5 && num % 5 == 0) num /= 5;

return num == 1;
}
}

原题地址

LintCode:丑数

坚持原创技术分享,您的支持将鼓励我继续创作!