Prime Factors
Introduction
This kata demonstrates that, as the tests get more specific, the algorithm becomes more general. But, besides that, it’s a wonderful kata to reflect on example selection, and why the tests that pass as soon as we write them aren’t really useful.
On the other hand, the kata reveals a much more intriguing concept: the premise of the priority of the transformations, according to which, in the same way that there are refactorings (which are changes in the structure of a code that don’t alter its behavior), there would also be transformations (that are changes in the code that do produce changes in its behavior).
These transformations would have an order, from simplest to the most complex, and a priority in their application that dictates that we should apply the simpler ones first.
History
The kata was created by Robert C. Martin1 when he was writing a program for his son to calculate the prime factors of a number. Thinking about its development, his attention was caught by the way in which the algorithm evolved and became simpler as it became more general.
Problem statement
Write a class with a generate method that returns a list of the prime factors of an integer. If yo uprefer a more procedural -or even functional- approach, try to write a primefactors function.
To not overcomplicate the exercise, the result may be expressed as an array, list or collection, without having to group the factors as powers. For example:
1 primefactors(2) = [2]
2 primefactors(3) = [3]
3 primefactors(6) = [2, 3]
4 primefactors(8) = [2, 2, 2]
5 primefactors(12) = [2, 2, 3]
Hints to solve it
This is a very simple kata, as well as a very potent one: you don’t need many cycles to carry it out, but nevertheless, highlights some specially important features of TDD.
To begin, we can analyze the examples that we could try. In principle, the arguments will be natural numbers. We have three main categories:
- Numbers that don’t have any prime factors, the only case is 1.
- Numbers that are prime, such as 2, 3, or 5.
- Numbers that are product of several prime numbers, such as 4, 6, 8, or 9.
Beside, among non-prime numbers, we find those that are the product of 2, 3, or n factors, repeated or not.
Applying the laws of TDD that we’ve already seen, we’ll start with the smallest possible failing test. Then, we’ll write the necessary production code to make the test pass.
We’ll go through the different cases by writing the test first, and then, the production code that makes it pass without breaking any of the previous tests.
One of the curiosities of this kata is that we can just go through the list of natural numbers in order, taking examples as we go until we consider that we can stop. However, is this the best strategy? Can it lead us to selecting unhelpful examples?