Prime Factors

Level: Beginner 15–30 min

Concepts: AlgorithmsIncremental Design

Solutions: C# | TypeScript | Python

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

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

Reference Walkthrough

Full C#, TypeScript, and Python implementations live at tddbuddy-reference-katas/prime-factors — the same eleven scenarios across all three languages, walked commit-by-commit through the TDD cycle.

This is a Pedagogy mode kata — the walkthroughs step through the TDD cycle commit-by-commit. Watch the gear shift from low (fake-it, triangulate) to middle (obvious implementation) once the outer divisor loop lands, then notice the chain of spec — commits that prove the algorithm generalized. See the repo’s Gears section for why labelling “passes on arrival” honestly is the point.

Related reading

  • Katas Are Rehearsal, Not Performance
    You don't practice TDD on production code. You practice on katas and bring the muscle memory to production. The gap between knowing TDD and doing TDD is reps.
  • The Contract Test Is the Only Witness the Agent Cannot Author
    A test the agent wrote against code the same agent wrote shares the agent's blind spot: a misunderstanding in the implementation becomes a matching misunderstanding in the test, the bar goes green, and the bug ships certified. Consumer-driven contract tests are the only category where a second team publishes the assertion the first team has to satisfy. That separation of authorship is exactly what tamper-resistant test design demanded, applied at the integration seam.
  • Test Deletion Is a Privileged Operation
    The cheapest way for an agent to make a failing test pass is to delete it. That is logical for the agent and catastrophic for the codebase. Tests are append-only by default. Deletion needs a human author, a separate commit, and a separate review.