249. Only 2, 3 and 5
A tile factory only produces boards whose side length factors completely into the primes 2, 3 and 5; any other prime factor makes the length unusable. Given the integer n, return true if every prime factor of n is one of 2, 3 or 5, and false otherwise.
By convention 1 is accepted because it has no prime factors, while zero and every negative number are rejected. For example, 180 = 2^2 * 3^2 * 5 is accepted, and 22 = 2 * 11 is rejected.
Do not test every number up to n for divisibility. Instead keep dividing n by 2, then 3, then 5 for as long as it divides evenly, and check whether you arrive at 1. The loop needs only O(log n) time and O(1) extra space.
Example 1
- Input:
- n = 450
- Output:
- true
- Explanation:
450 = 2 * 3^2 * 5^2 uses only the allowed primes, so the answer is true.
Example 2
- Input:
- n = 98
- Output:
- false
- Explanation:
98 = 2 * 7^2 contains the prime 7, so the answer is false.
Example 3
- Input:
- n = 1
- Output:
- true
- Explanation:
1 has no prime factors at all, so it counts as true.
Constraints
-231 ≤ n ≤ 231 - 1
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(log n)
- Space
- O(1)