Ugly Number
Ugly Number: determine whether a positive integer's only prime factors are 2, 3, and 5.
- -2³¹ <= n <= 2³¹ - 1
Intuition
Ugly number tests whether a positive integer's only prime factors are 2, 3, and 5. Factorising fully is unnecessary — the question is narrower than it appears.
The direct method removes the permitted factors and inspects the remainder:
- Divide out every factor of 2, then 3, then 5; the number is ugly exactly when 1 remains.
If anything other than 1 is left, it must contain a prime factor outside the allowed set, which disqualifies it. No factorisation of that remainder is needed — its mere existence settles the answer.
Each division must run in a loop, not once. A number like 8 has three factors of 2, and dividing a single time leaves 4, which then fails the test wrongly.
The order of the three divisions does not matter, since removing one prime's factors never affects another's.
The cases that break implementations are at the boundary. Zero and negative numbers are not ugly, and zero in particular causes an infinite loop, since it divides evenly by 2 forever. Guarding n <= 0 before the loop is essential.
1 is ugly by convention — it has no prime factors at all, so vacuously none outside the set. The algorithm returns this correctly without a special case, since no divisions occur and 1 remains.
The number shrinks by a factor of at least 2 per division, so the loop runs O(log n) times.
Ugly Number II is a different problem entirely — generating the n-th ugly number, which needs a DP with three pointers rather than a divisibility test.
Divide out every factor of 2, 3, and 5; if 1 remains, those were the only prime factors. The loop over a tuple of divisors keeps the three cases from being written three times — and the positivity guard comes first, as with every divide-down test.
Approach
Before reading on: price up what the direct approach costs here, then ask what pattern in the numbers removes the loop entirely. Aim for O(log n) time and O(1) space.
Narrow the question
Full factorisation is unnecessary. Removing the permitted factors and checking the remainder settles it without identifying any other prime.
Guard the boundary first
Return false for n <= 0. Zero divides evenly by 2 forever and causes an infinite loop — the case that hangs naive implementations.
Divide out each factor in a loop
Repeatedly divide by 2, then 3, then 5. Dividing once leaves 4 from 8, which then fails the test wrongly.
Check for one
The number is ugly exactly when 1 remains. Anything else must contain a disallowed prime, and its identity does not matter.
Accept one as ugly
1 has no prime factors, so vacuously none outside the set. The algorithm returns this correctly with no special case.
Cost of the check
The number shrinks by a factor of at least 2 per division, giving O(log n) time and O(1) space.
Solution & live demo
Common pitfalls
Omitting the positivity guard
for factor in (2, 3, 5):
while n % factor == 0:
n //= factorif n <= 0:
return FalseZero divides by 2 forever without changing, so the loop never terminates. Negative values also can't be ugly by definition, and dividing them yields −1 rather than 1.
Using if instead of while
if n % factor == 0:
n //= factorwhile n % factor == 0:
Each prime may appear many times — 8 is 2³. Dividing once leaves a residue that isn't 1 and reports a genuinely ugly number as false.
Testing divisibility rather than dividing
return n % 2 == 0 or n % 3 == 0 or n % 5 == 0
while n % factor == 0: n //= factor return n == 1
That accepts 14, whose factors include 7. The requirement is that 2, 3, and 5 are the only prime factors, which is proved by nothing remaining after they're divided out.
Edge cases
no factors to divide out, remains 1, trivially ugly by definition
while loop divides by 2 three times, leaving 1 -> ugly
dividing by 2 once leaves 7, which 3 and 5 don't divide -> not ugly
guarded out before any division, returns False