Ugly Number
Problem
An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5. Given an integer n, return true if n is an ugly number.
n = 6truedef is_ugly(n):
if n <= 0: return False
for p in (2, 3, 5):
while n % p == 0:
n //= p
return n == 1function isUgly(n) {
if (n <= 0) return false;
for (const p of [2, 3, 5]) {
while (n % p === 0) n = n / p;
}
return n === 1;
}class Solution {
public boolean isUgly(int n) {
if (n <= 0) return false;
for (int p : new int[]{2, 3, 5})
while (n % p == 0) n /= p;
return n == 1;
}
}bool isUgly(int n) {
if (n <= 0) return false;
for (int p : {2, 3, 5})
while (n % p == 0) n /= p;
return n == 1;
}Explanation
An ugly number is allowed to have only 2, 3, and 5 as prime factors. The simplest way to test this is to strip away all of those factors and see if anything else is left.
We loop over the three allowed primes. For each prime p, while n divides evenly by p, we divide it out with n //= p. After this, none of 2, 3, 5 remain in n.
If n is now exactly 1, it was built purely from those primes, so it is ugly. If anything bigger than 1 survives, then n had some other prime factor and is not ugly. We also reject n <= 0 up front, since ugly numbers must be positive.
Example: n = 6. Dividing by 2 gives 3, then dividing by 3 gives 1. The remainder is 1, so 6 is ugly → true. By contrast 14 = 2 * 7 would leave 7 behind and return false.
It is fast because each division at least halves n, so the loop finishes in O(log n) steps.