Ugly Number
Determine whether a positive integer's only prime factors are 2, 3, and 5.
Open on LeetCode ↗Intuition
The trap is checking divisibility by each factor only once instead of dividing it out completely. Take 8 = 222: a single division by 2 leaves 4, and if your check stops there and looks at 4 % 2 != 0 as if that settles it, or moves on to test 3 and 5 against 4 without finishing the job on 2, you wrongly reject a genuinely ugly number. The fix is a while loop per factor, not an if: divide by 2 repeatedly while it still divides, then move to 3, then 5, each with its own while loop. The invariant is that after fully draining all three factors, whatever integer remains has no more 2s, 3s, or 5s in it -- the number is ugly exactly when that remainder is 1.
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
Reject non-positive values immediately
Zero and negative numbers are never considered ugly by definition, so return False for n <= 0 before doing any factor work.
Fully divide out each factor with a while loop
For each factor in [2, 3, 5], use a while loop (not a single if) to keep dividing the current value by that factor as long as it divides evenly. This is the step that matters: a number like 8 needs three divisions by 2, not one, before moving on.
Check what remains
After all three factors have been fully drained, the number is ugly if and only if what's left equals 1. Any leftover value greater than 1 means some other prime factor was present.
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