We need to determine whether a given integer is an "ugly number," a positive integer whose only prime factors are 2, 3, and 5. Numbers like 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 are all ugly, while 7, 11, 13, 14 are not.

Three details shape the solution. First, the number must be positive: zero and negative numbers are never ugly. Second, 1 is ugly because it has no prime factors at all, which satisfies the condition vacuously. Third, divisibility by 2, 3, or 5 is not enough. We need to verify that after removing every factor of 2, 3, and 5, nothing else remains, meaning the number reduces to 1.

That gives the core idea: divide n by 2, 3, and 5 repeatedly while it stays divisible. If n reaches 1, every prime factor was 2, 3, or 5. If it stops at any other value, that value is a prime factor outside the allowed set, so n is not ugly.

Key Constraints:

Intuition

Strip out the allowed prime factors one at a time and inspect the remainder. While n is divisible by 2, divide by 2 until it no longer is. Repeat for 3, then for 5. If n reduces to 1, every prime factor was 2, 3, or 5. If it stops at any larger value, that leftover value is a prime factor outside the allowed set, so n is not ugly.

The order of the three factors does not matter. Dividing out all 2s, then all 3s, then all 5s removes exactly the same set of factors as any other order, because removing one prime never creates or destroys a factor of another prime.

Handle the edge case first: if n is zero or negative, return false immediately, since neither can be ugly.

Algorithm

Example Walkthrough

Code

The iterative version removes factors with explicit loops. The same check has a recursive form that expresses the self-similar structure of the problem directly.

Intuition

An ugly number has a self-similar structure: if n is divisible by one of the allowed primes, then n is ugly exactly when n / prime is ugly. Dividing out a single factor leaves a smaller problem of the same kind, which makes recursion a clean fit.

The base cases anchor the recursion. A value of 1 is ugly, so return true. A value that is zero or negative is not ugly, so return false. For any other value, check the three allowed primes: if one divides n, recurse on n divided by that prime. If none divides n, then n is greater than 1 and has no allowed factor, so it is not ugly.

This does the same total work as the iterative version, since each recursive call removes one prime factor. The difference is that the loop's bounded iteration becomes a chain of calls on the stack.

Algorithm

Example Walkthrough

Code