The Decomposer

An easy Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
easy
Seniority
L3
Asked in
Citadel

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]).

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

Example 1

Input:

n = 12

Output:

[2,2,3]

Example 2

Input:

n = 28

Output:

[2,2,7]

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
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

Common follow-up questions