Prime Factorization

Decompose any positive integer into its prime factors with multiplicity.

prime math loops number-theory

Write a function `prime_factors(n: int) -> list[int]` that takes a positive integer `n` and returns a list of its prime factors in non-decreasing order. Each prime factor should appear as many times as it divides `n`. For example, `prime_factors(12)` should return `[2, 2, 3]` because 12 = 2 × 2 × 3. The result must be a list of integers.

Details:
- Assume `n >= 2`.
- The list must be sorted in non-decreasing order.
- The product of the returned list must equal `n`.

Constraints

Input `n` is an integer such that `2 <= n <= 10^9`. The expected time complexity is O(sqrt(n)) in the worst case.

Example

>>> prime_factors(2)
[2]
>>> prime_factors(12)
[2, 2, 3]
>>> prime_factors(17)
[17]
>>> prime_factors(100)
[2, 2, 5, 5]

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

You only need to trial divide by 2, then odd numbers up to sqrt(n).

After dividing by all factors up to sqrt(n), if n > 1, it must be prime.

Use a while loop to collect all occurrences of each factor.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.