# The Decomposer

> Every composite thing can be broken down to its simplest parts.

Canonical URL: <https://datadriven.io/problems/the_decomposer>

Domain: Python · Difficulty: easy · Seniority: L3

## Problem

Given an integer n > 1, return its prime factorization as a list of primes in ascending order. Repeated factors are included (for example, 12 -> [2, 2, 3]).

## Worked solution and explanation

### Why this problem exists in real interviews

This tests **prime factorization via trial division**, a fundamental number theory algorithm. It probes loop construction, modular arithmetic, and understanding of the optimization to only check up to the square root.

---

### Break down the requirements

#### Step 1: Start dividing by 2

Extract all factors of 2 first, since it is the only even prime.

#### Step 2: Try odd divisors from 3 up to the square root

After removing all 2s, only odd factors remain. Check each odd number and extract all instances.

#### Step 3: Handle the remaining factor

If the number is still greater than 1 after the loop, it is itself a prime factor.

---

### The solution

**Trial division with square root cutoff**

```python
def prime_factors(n: int) -> list:
    factors = []
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors.append(d)
            n = n // d
        d += 1
    if n > 1:
        factors.append(n)
    return factors
```

> **Time and Space Complexity**
>
> **Time:** O(sqrt(n)) in the worst case. Each division reduces n, so the total work is bounded by the square root of the original input.
> 
> **Space:** O(log n) for the factors list, since the number of prime factors is at most log2(n).

> **Interviewers Watch For**
>
> Whether you optimize by stopping at sqrt(n) instead of checking all divisors up to n. The sqrt cutoff is the key efficiency gain.

> **Common Pitfall**
>
> Forgetting the final `if n > 1` check. Without it, large prime factors that remain after the loop are lost.

---

## Common follow-up questions

- How would you check if a number is prime? _(Tests reusing the trial division pattern but returning a boolean.)_
- What is the time complexity for very large numbers? _(Tests awareness that trial division is not practical for cryptographic-size primes.)_
- How would you find the prime factorization of many numbers efficiently? _(Tests the Sieve of Eratosthenes for precomputing smallest prime factors.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_decomposer)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.