1423. Prime Power Breakdown
A workshop stamps a serial number n on every batch of tiles, and the quality team wants to know which prime building blocks the number is made of. Given the integer n, write it as a product of prime powers and return one pair [prime, exponent] for every distinct prime that divides n. The pairs must be sorted by prime in ascending order, and every exponent is at least 1. For example, 360 = 23 x 32 x 5 gives [[2,3],[3,2],[5,1]]. A prime number is returned as a single pair with exponent 1. Trial division up to the square root of n is expected, so the running time is O(sqrt(n)) with O(1) extra space apart from the output.
Example 1
- Input:
- n = 360
- Output:
- [[2,3],[3,2],[5,1]]
- Explanation:
360 = 2^3 * 3^2 * 5, so the pairs are [2,3], [3,2] and [5,1].
Example 2
- Input:
- n = 97
- Output:
- [[97,1]]
- Explanation:
97 is prime, so the only pair is [97,1].
Constraints
2 ≤ n ≤ 1012
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(sqrt(n))
- Space
- O(1)