Math Number tricks
95. Ugly Number
The prime factors of a number are the primes that multiply together to make it. For example, the prime factors of 60 = 2 × 2 × 3 × 5 are 2, 3 and 5, and the prime factors of 42 = 2 × 3 × 7 are 2, 3 and 7.
An ugly number is a positive integer whose prime factors are all 2, 3 or 5. So 60 is ugly, and 42 is
not, because 7 is one of its prime factors. Given an integer n, return true if n is an ugly number,
and false otherwise.
1 is ugly: it has no prime factors at all, so none of them is anything other than 2, 3 or 5. Zero and the
negative numbers are not positive, so they are never ugly. In C++, Java, Go, Rust and C#, n is a 64-bit
integer.
Example 1
Input: n = 1350
trueExplanation: 1350 = 2 × 3 × 3 × 3 × 5 × 5. Every prime factor is 2, 3 or 5.
Example 2
Input: n = 154
falseExplanation: 154 = 2 × 7 × 11. It is even, but 7 and 11 are prime factors too.
Example 3
Input: n = -30
falseExplanation: 30 = 2 × 3 × 5 is ugly, but −30 is negative, and an ugly number must be positive.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
-9 × 1015 ≤ n ≤ 9 × 1015
Clarifying questions
What you would ask an interviewer before writing any code.