Prime Factors

Level: Beginner 15–30 min

Concepts: AlgorithmsIncremental Design

---

Write a function that takes a positive integer and returns its prime factorization as a list of prime numbers.

Requirements

• Given a positive integer, return its prime factors in ascending order
• If a prime factor appears multiple times, include it that many times
• 1 has no prime factors (return an empty list)

Examples

Input	Output
1	[]
2	[2]
3	[3]
4	[2, 2]
6	[2, 3]
8	[2, 2, 2]
9	[3, 3]
12	[2, 2, 3]
15	[3, 5]
100	[2, 2, 5, 5]
235711*13 = 30030	[2, 3, 5, 7, 11, 13]

Test Cases

Work through these in order — each one drives a small transformation in the algorithm:

1. generate(1) → []
2. generate(2) → [2]
3. generate(3) → [3]
4. generate(4) → [2, 2]
5. generate(6) → [2, 3]
6. generate(8) → [2, 2, 2]
7. generate(9) → [3, 3]

By test 7, the algorithm should be complete. Every subsequent input should pass without changing the code.

Bonus

• Handle edge cases: what happens with 0? Negative numbers?
• Return the factorization as a map of prime → exponent (e.g. 12 → {2: 2, 3: 1})
• Calculate the greatest common divisor (GCD) of two numbers using their prime factorizations

Hint

Follow the tests in order. The beauty of this kata is how the algorithm emerges from the simplest possible transformations. Don’t think ahead — let each failing test drive the next change.