Solving the Prime Factors kaka
Statement of the kata
Our objective will be to write a program that decomposes a natural number into its prime factors. For the sake of simplicity, we won’t group the factors as powers. We’ll leave that as a posterior exercise, if you wish to advance a bit further.
Language and approach
We’re going to solve this kata in Javascript, using the Jest testing framework. We’ll create a primefactors function to which we’ll pass the number that we wish to decompose, obtaining as a response an array of its prime factors sorted from lowest to highest.
1 var primesOf18 = primefactors(18);
2 // -> [2, 3, 3]
Define the function
Our first test expects the primefactors function to exist:
1 describe('Calculate prime factors', function () {
2 it ('should exist', () => {
3 expect(primefactors())
4 });
5 });
Which, as we already know, hasn’t been defined yet:
1 ReferenceError: primefactors is not defined
We introduce it without further ado. For now, in the test file itself:
1 function primefactors() {
2
3 }
We haven’t yet communicated with the function in the test, so we’re going to introduce that idea, passing it a first example of a number to decompose, along the result that we expect. The first thing that should draw our attention is, that due to the peculiarities of the definition and distribution of primes among natural numbers, we have a very intuitive way of organizing the examples and writing the test. It’s almost enough to start with number one and advance incrementally.
Number one, moreover, is a particular case (it doesn’t have any prime factor), so it suits us especially well as a first test.
1 import primefactors from "../src/primefactors";
2
3 describe('Calculate prime factors', function () {
4 it ('should exist', () => {
5 expect(primefactors())
6 });
7
8 it('1 should not have factors', () => {
9 expect(primefactors(1)).toEqual([]);
10 });
11 });
To pass the test we need a minimal implementation of the function:
1 function primefactors() {
2 return [];
3 }
4
5 export default primefactors;
Note that we don’t even implement the function’s necessity for a parameter. We’re gonna make the test be the one that asks for it first. Meanwhile, we delete the first test, given that it has become redundant.
1 import primefactors from "../src/primefactors";
2
3 describe('Calculate prime factors', function () {
4 it('1 should not have factors', () => {
5 expect(primefactors(1)).toEqual([]);
6 });
7 });
Define the function’s signature
The second test should help us define the function’s signature. To do so, we need a case in which we expect a response different than [], something we’ll be able to do if we receive a parameter that introduces the necessary variation. Number 2 is a good example with which to achieve this:
1 import primefactors from "../src/primefactors";
2
3 describe('Calculate prime factors', function () {
4 it('1 should not have factors', () => {
5 expect(primefactors(1)).toEqual([]);
6 });
7
8 it ('2 is a prime number', () => {
9 expect(primefactors(2)).toEqual([2])
10 })
11 });
To solve this case we need to take into account the parameter defined by the function, which forces us to introduce and use it. In our solution, we handle the case that the previous test states, and we make an obvious implementation to pass the test that we’ve just introduced. We’re postponing the implementation of the algorithm until we have more information:
1 function primefactors(numberToDecompose) {
2 if (numberToDecompose === 1) {
3 return [];
4 }
5
6 return [2];
7 }
8
9 export default primefactors;
Obtaining more imformation about the problem
The next case that we’re going to try is decomposing number 3, which is prime like number 2. This test will help us to better understand how to handle these cases:
1 import primefactors from "../src/primefactors";
2
3 describe('Calculate prime factors', function () {
4 it('1 should not have factors', () => {
5 expect(primefactors(1)).toEqual([]);
6 });
7
8 it ('2 is a prime number', () => {
9 expect(primefactors(2)).toEqual([2])
10 })
11
12 it ('3 is also a prime number', () => {
13 expect(primefactors(3)).toEqual([3])
14 })
15 });
Now that we have this failing test we’ll make an obvious implementation, such as returning the passed number itself. Since it’s a prime number, this is perfectly correct. There’s not much else to do here.
1 function primefactors(numberToDecompose) {
2 if (numberToDecompose === 1) {
3 return [];
4 }
5
6 return [numberToDecompose];
7
8 }
9
10 export default primefactors;
Introducing a test that doesn’t fail
In the presentation of the kata we’ve divided the cases into categories. Let’s review:
- Edge or special cases, such as 1
- Prime numbers, like 2, 3, or 5
- Non-prime numbers, like 4, 6, or 8
We’ve already covered the first category, since there are no more edge cases to consider.
We haven’t begun to treat the third category yet, and we haven’t done any test with any of its examples.
The second category is the one that we’ve been testing until now. At this point, we could keep selecting examples from this category and trying new cases. But, what would happen? Let’s see it.
1 import primefactors from "../src/primefactors";
2
3 describe('Calculate prime factors', function () {
4 it('1 should not have factors', () => {
5 expect(primefactors(1)).toEqual([]);
6 });
7
8 it ('2 is a prime number', () => {
9 expect(primefactors(2)).toEqual([2])
10 })
11
12 it ('3 is also a prime number', () => {
13 expect(primefactors(3)).toEqual([3])
14 })
15
16 it ('5 is also a prime number', () => {
17 expect(primefactors(5)).toEqual([5])
18 })
19
20 });
The test passes without implementing anything!
It was pretty obvious, wasn’t it? At this moment, the so-called algorithm, doesn’t do anything else than consider all numbers as primes. For this reason, if we keep using prime numbers as examples, nothing will force us to make changes to the implementation.
When we add a test that doesn’t fail, it means that the algorithm that we’re developing is already general enough to solve every case from that category, and therefore, it’s time to move on to a different category that we cannot yet successfully handle. Or, if we’ve already discovered all of the possible categories, it means that we’ve already finished!
We’re going to start using example from the non-prime category. But, we’re also going to refactor the solution to be able to see these categories in a more explicit manner:
1 import primefactors from "../src/primefactors";
2
3 describe('Calculate prime factors', function () {
4 it('1 should not have factors', () => {
5 expect(primefactors(1)).toEqual([]);
6 });
7
8 it ('prime numbers cannot be decomposed', () => {
9 expect(primefactors(2)).toEqual([2])
10 expect(primefactors(3)).toEqual([3])
11 expect(primefactors(5)).toEqual([5])
12 })
13 });
Questioning our algorithm
The first non-prime that we have is number 4, and it’s the simplest of them all for many reasons. So, this time we write a test that will fail:
1 import primefactors from "../src/primefactors";
2
3 describe('Calculate prime factors', function () {
4 it('1 should not have factors', () => {
5 expect(primefactors(1)).toEqual([]);
6 });
7
8 it ('prime numbers cannot be decomposed', () => {
9 expect(primefactors(2)).toEqual([2])
10 expect(primefactors(3)).toEqual([3])
11 expect(primefactors(5)).toEqual([5])
12 })
13
14 it ('4 is 2 * 2', () => {
15 expect(primefactors(4)).toEqual([2, 2])
16 })
17 });
There are many ways of approaching this implementation. For example, we have this one that, while especially naive, is effective:
1 function primefactors(numberToDecompose) {
2 if (numberToDecompose === 1) {
3 return [];
4 }
5
6 if (numberToDecompose === 4) {
7 return [2, 2];
8 }
9
10 return [numberToDecompose];
11 }
12
13 export default primefactors;
In spite of its simpleness, it’s interesting. It help us understand that we have to distinguish between primes and non-primes in order to develop the algorithm.
Nevertheless, it has a very unkept look. Let’s try to organize it a bit more neatly:
1 function primefactors(numberToDecompose) {
2 if (numberToDecompose > 1) {
3 if (numberToDecompose === 4) {
4 return [2, 2];
5 }
6
7 return [numberToDecompose];
8 }
9
10 return [];
11 }
12
13 export default primefactors;
It basically says: if a number is higher than 1 we try to decompose it. If it’s 4, we return its factorization. And if it’s not, we return the same number, for it will be prime. Which is true for all of our current examples.
Discovering the multiples of 2
The next number that we can decompose is 6. A nice thing about this kata is that every non-prime number gives us a different response, and that means that every test is going to provide us with some information. Here it is:
1 import primefactors from "../src/primefactors";
2
3 describe('Calculate prime factors', function () {
4 it('1 should not have factors', () => {
5 expect(primefactors(1)).toEqual([]);
6 });
7
8 it ('prime numbers cannot be decomposed', () => {
9 expect(primefactors(2)).toEqual([2])
10 expect(primefactors(3)).toEqual([3])
11 expect(primefactors(5)).toEqual([5])
12 })
13
14 it ('4 is 2 * 2', () => {
15 expect(primefactors(4)).toEqual([2, 2])
16 })
17
18 it ('6 is 2 * 3', () => {
19 expect(primefactors(6)).toEqual([2, 3])
20 })
21 });
Let’s begin with the naive implementation:
1 function primefactors(numberToDecompose) {
2 if (numberToDecompose > 1) {
3 if (numberToDecompose === 4) {
4 return [2, 2];
5 }
6
7 if (numberToDecompose === 6) {
8 return [2, 3];
9 }
10
11 return [numberToDecompose];
12 }
13
14 return [];
15 }
16
17 export default primefactors;
There’s nothing wrong with doing it this way. On the contrary, this way of solving the problem starts highlighting regularities. 4 and 6 are multiples of 2, so we want to introduce this knowledge in the shape of a refactoring. And we could do this thanks to our tests, that demonstrate that the function already decomposes them correctly. So, we’re going to modify the code without changing the behavior that we’ve already defined through tests.
Our first try relies on the fact that the first factor is 2 and is common between them. That is, we can design an algorithm that processes multiples of 2 and, for now, we assume that the remainder of that first division by 2 is the second of its factors, whichever it is.
To do so we have to introduce an array-type variable with which to deliver the response, to which we’ll be adding the factors as we discover them.
1 function primefactors(numberToDecompose) {
2
3 let factors = [];
4
5 if (numberToDecompose > 1) {
6 if (numberToDecompose === 4) {
7 factors.push(2);
8 factors.push(2);
9
10 return factors;
11 }
12
13 if (numberToDecompose === 6) {
14 factors.push(2);
15 factors.push(3);
16
17 return factors;
18 }
19
20 factors.push(numberToDecompose);
21 }
22
23 return factors;
24 }
25
26 export default primefactors;
This has been a first step, now it’s clearer how it would work, and we can generalize it by expressing it like this:
1 function primefactors(numberToDecompose) {
2
3 let factors = [];
4
5 if (numberToDecompose > 1) {
6 if (numberToDecompose % 2 === 0) {
7 factors.push(2);
8 factors.push(Math.floor(numberToDecompose/2));
9
10 return factors;
11 }
12
13 factors.push(numberToDecompose);
14 }
15
16 return factors;
17 }
18
19 export default primefactors;
This refactoring almost works, but the test for number 2 has stopped passing. We fix it, and we advance a step further.
1 function primefactors(numberToDecompose) {
2
3 let factors = [];
4
5 if (numberToDecompose > 1) {
6 if (numberToDecompose % 2 === 0 && numberToDecompose > 2) {
7 factors.push(2);
8 numberToDecompose = Math.floor(numberToDecompose/2);
9 }
10
11 factors.push(numberToDecompose);
12 }
13
14 return factors;
15 }
16
17 export default primefactors;
This new implementation passes all the tests, and we’re ready to force a new change.
Introducing more factors
Among the non-prime numbers we could consider several groupings to the effect of selecting examples. There are some cases in which the numbers are decomposed as the product of two prime factors, and others in which they’re decomposed as the product of three or more. This is relevant because our next examples are 8 and 9. 8 is 2 * 2 * 2, while 9 is 3 * 3. The 8 forces us to consider the cases in which we can decompose a number in more than two factors, while the 9, those in which new divisors are introduced.
In principle, we don’t care much about which case to start with. Maybe the key is to pick the case that seems the easiest to manage. Here we’ll start by decomposing the number 8. This way we keep working with the 2 as the only divisor, which at the moment looks a little easier to approach.
Let’s write a test:
1 import primefactors from "../src/primefactors";
2
3 describe('Calculate prime factors', function () {
4 it('1 should not have factors', () => {
5 expect(primefactors(1)).toEqual([]);
6 });
7
8 it ('prime numbers cannot be decomposed', () => {
9 expect(primefactors(2)).toEqual([2])
10 expect(primefactors(3)).toEqual([3])
11 expect(primefactors(5)).toEqual([5])
12 })
13
14 it ('4 is 2 * 2', () => {
15 expect(primefactors(4)).toEqual([2, 2])
16 })
17
18 it ('6 is 2 * 3', () => {
19 expect(primefactors(6)).toEqual([2, 3])
20 })
21
22 it ('8 is 2 * 2 * 2', () => {
23 expect(primefactors(8)).toEqual([2, 2, 2])
24 })
25 });
To implement, we have the change an if for a while. That is, we have to keep dividing the number by 2 until we can’t do it anymore.
1 function primefactors(numberToDecompose) {
2
3 let factors = [];
4
5 if (numberToDecompose > 1) {
6 while (numberToDecompose % 2 === 0 && numberToDecompose > 2) {
7 factors.push(2);
8 numberToDecompose = Math.floor(numberToDecompose/2);
9 }
10
11 factors.push(numberToDecompose);
12 }
13
14 return factors;
15 }
16
17 export default primefactors;
This change is quite spectacular because, while being very small, is also very powerful. By applying this, we can decompose any number that is a power of 2, nothing more and nothing less. But this is not the final goal, we want to be able to decompose any number, and to do so we must introduce new divisors.
New divisors
At this point, we need an example to force us introduce new divisors. Earlier we had left number 9 for later, and now the time has come to resume it. 9 is a good example because it’s a multiple of 3 without being a multiple of 2. Let’s write a test that we’re sure will fall.
1 import primefactors from "../src/primefactors";
2
3 describe('Calculate prime factors', function () {
4 it('1 should not have factors', () => {
5 expect(primefactors(1)).toEqual([]);
6 });
7
8 it ('prime numbers cannot be decomposed', () => {
9 expect(primefactors(2)).toEqual([2])
10 expect(primefactors(3)).toEqual([3])
11 expect(primefactors(5)).toEqual([5])
12 })
13
14 it ('4 is 2 * 2', () => {
15 expect(primefactors(4)).toEqual([2, 2])
16 })
17
18 it ('6 is 2 * 3', () => {
19 expect(primefactors(6)).toEqual([2, 3])
20 })
21
22 it ('8 is 2 * 2 * 2', () => {
23 expect(primefactors(8)).toEqual([2, 2, 2])
24 })
25
26 it ('9 is 3 * 3', () => {
27 expect(primefactors(9)).toEqual([3, 3])
28 })
29 });
Again, let’s start with an implementation that’s very naive but works. The important thing is to pass the test, proof that we’ve implemented the specified behavior.
1 function primefactors(numberToDecompose) {
2
3 let factors = [];
4
5 if (numberToDecompose > 1) {
6 while (numberToDecompose % 2 === 0 && numberToDecompose > 2) {
7 factors.push(2);
8 numberToDecompose = Math.floor(numberToDecompose/2);
9 }
10
11 while (numberToDecompose % 3 === 0 && numberToDecompose > 3) {
12 factors.push(3);
13 numberToDecompose = Math.floor(numberToDecompose / 3);
14 }
15
16 factors.push(numberToDecompose);
17 }
18
19 return factors;
20 }
21
22 export default primefactors;
With the previous code, all tests are green. At this point it’s made obvious that each new divisor that we wish to introduce, such as 5, will need a repetition of the block, so let’s refactor it into a general solution.
1 function primefactors(numberToDecompose) {
2
3 let factors = [];
4
5 let divisor = 2;
6
7 while (numberToDecompose > 1) {
8 while (numberToDecompose % divisor === 0) {
9 factors.push(divisor);
10 numberToDecompose = Math.floor(numberToDecompose / divisor);
11 }
12 divisor++;
13 }
14
15 return factors;
16 }
17
18 export default primefactors;
This algorithm looks pretty general. Let’s test a couple of cases:
1 import primefactors from "../src/primefactors";
2
3 describe('Calculate prime factors', function () {
4 it('1 should not have factors', () => {
5 expect(primefactors(1)).toEqual([]);
6 });
7
8 it ('2 is a prime number', () => {
9 expect(primefactors(2)).toEqual([2])
10 })
11
12 it ('3 is also a prime number', () => {
13 expect(primefactors(3)).toEqual([3])
14 })
15
16 it ('4 is 2 * 2', () => {
17 expect(primefactors(4)).toEqual([2, 2])
18 })
19
20 it ('6 is 2 * 3', () => {
21 expect(primefactors(6)).toEqual([2, 3])
22 })
23
24 it ('8 is 2 * 2 * 2', () => {
25 expect(primefactors(8)).toEqual([2, 2, 2])
26 })
27
28 it ('9 is 3 * 3', () => {
29 expect(primefactors(9)).toEqual([3, 3])
30 })
31
32 it ('10 is 2 * 5', () => {
33 expect(primefactors(10)).toEqual([2, 5])
34 })
35
36 it ('12 is 2 * 2 * 3', () => {
37 expect(primefactors(12)).toEqual([2, 2, 3])
38 })
39 });
We’ve added two tests that pass. It seems that we’ve solve the problem, but… don’t you have the sensation of having leaped too far with this last step?
The shortest path isn’t always the fastest
The development road in TDD isn’t always easy. The next test is sometimes very obvious, but other time we are faced with several alternatives. Choosing the wrong path can lead us to a dead end or, like it has happened here, to a point where we have to implement too much in one go. And as we’ve already discussed, the changes that we add to the production code should always be as small as possible.
In the sixth test, we decided to explore the path of “repetitions of the same factor” instead of forcing other prime factors to appear. Would it have been better to follow that ramification of the problem? Let’s try it, let’s rewind and go back to the situation as it was before that sixth test.
Introducing new factors, second try
This is the version of the production code that we had when we arrived at the sixth test:
1 function primefactors(numberToDecompose) {
2
3 let factors = [];
4
5 if (numberToDecompose % 2 === 0) {
6 factors.push(2);
7 numberToDecompose = Math.floor(numberToDecompose / 2);
8 }
9
10 if (numberToDecompose > 1) {
11 factors.push(numberToDecompose);
12 }
13
14 return factors;
15 }
16
17 export default primefactors;
Now, let’s go down the other route:
1 import primefactors from "../src/primefactors";
2
3 describe('Calculate prime factors', function () {
4 it('1 should not have factors', () => {
5 expect(primefactors(1)).toEqual([]);
6 });
7
8 it ('prime numbers cannot be decomposed', () => {
9 expect(primefactors(2)).toEqual([2])
10 expect(primefactors(3)).toEqual([3])
11 expect(primefactors(5)).toEqual([5])
12 })
13
14 it ('4 is 2 * 2', () => {
15 expect(primefactors(4)).toEqual([2, 2])
16 })
17
18 it ('6 is 2 * 3', () => {
19 expect(primefactors(6)).toEqual([2, 3])
20 })
21
22 it ('9 is 3 * 3', () => {
23 expect(primefactors(9)).toEqual([3, 3])
24 })
25 });
The following production code let’s us pass the new test, and all the previous ones:
1 function primefactors(numberToDecompose) {
2
3 let factors = [];
4
5 if (numberToDecompose % 2 === 0) {
6 factors.push(2);
7 numberToDecompose = Math.floor(numberToDecompose / 2);
8 }
9
10 if (numberToDecompose % 3 === 0) {
11 factors.push(3);
12 numberToDecompose = Math.floor(numberToDecompose / 3);
13 }
14
15 if (numberToDecompose > 1) {
16 factors.push(numberToDecompose);
17 }
18
19 return factors;
20 }
21
22 export default primefactors;
Now we could refactor:
1 function primefactors(numberToDecompose) {
2
3 let factors = [];
4
5 let divisor = 2;
6
7 while (divisor < numberToDecompose) {
8 if (numberToDecompose % divisor === 0) {
9 factors.push(divisor);
10 numberToDecompose = Math.floor(numberToDecompose / divisor);
11 }
12 divisor++;
13 }
14
15 if (numberToDecompose > 1) {
16 factors.push(numberToDecompose);
17 }
18
19 return factors;
20 }
21
22 export default primefactors;
More than two factors
To introduce more than two factors we need a test:
1 import primefactors from "../src/primefactors";
2
3 describe('Calculate prime factors', function () {
4 it('1 should not have factors', () => {
5 expect(primefactors(1)).toEqual([]);
6 });
7
8 it ('prime numbers cannot be decomposed', () => {
9 expect(primefactors(2)).toEqual([2])
10 expect(primefactors(3)).toEqual([3])
11 expect(primefactors(5)).toEqual([5])
12 })
13
14 it ('4 is 2 * 2', () => {
15 expect(primefactors(4)).toEqual([2, 2])
16 })
17
18 it ('6 is 2 * 3', () => {
19 expect(primefactors(6)).toEqual([2, 3])
20 })
21
22 it ('9 is 3 * 3', () => {
23 expect(primefactors(9)).toEqual([3, 3])
24 })
25
26 it ('8 is 2 * 2 * 2', () => {
27 expect(primefactors(8)).toEqual([2, 2, 2])
28 })
29 });
The necessary change is a simple one:
1 function primefactors(numberToDecompose) {
2
3 let factors = [];
4
5 let divisor = 2;
6
7 while (divisor < numberToDecompose) {
8 while (numberToDecompose % divisor === 0) {
9 factors.push(divisor);
10 numberToDecompose = Math.floor(numberToDecompose / divisor);
11 }
12 divisor++;
13 }
14
15 if (numberToDecompose > 1) {
16 factors.push(numberToDecompose);
17 }
18
19 return factors;
20 }
21
22 export default primefactors;
And we can rid ourselves of that last if, as it’s covered by the while that we’ve just introduced:
1 function primefactors(numberToDecompose) {
2
3 let factors = [];
4
5 let divisor = 2;
6
7 while (divisor <= numberToDecompose) {
8 while (numberToDecompose % divisor === 0) {
9 factors.push(divisor);
10 numberToDecompose = Math.floor(numberToDecompose / divisor);
11 }
12 divisor++;
13 }
14
15 return factors;
16 }
17
18 export default primefactors;
If we add new tests we’ll see that we can refactor any number without problems. That is to say, after this last change and its refactoring, we’ve finished the development of the class. Has this path been any better? Partly yes. We’ve come up with an almost identical algorithm, but I’d say that the journey has been smoother, the jumps in production code have been less steep, and everything has gone better.
Do we have any criteria to select new examples?
From the traditional QA point of view, there is a series of methods to choose the test cases. However, these methods are not necessarily applicable in TDD. Remember how we started this book: QA and TDD are not the same despite using the same tools and overlapping a lot. TDD is a methodology to drive software development, and the most adequate tests to do it can be slightly different to those that we would use to verify the behavior of the finished software.
For example, our categorization of the numbers into primes and non-primes may be more than enough in QA, but in TDD, the case of non-prime numbers could be further subdivided:
- Powers of a prime factor, such as 4, 8 or 9, which involve just one prime number multiplied several times by itself.
- Products of different primes, such as 6 or 10, which involve more than one prime number.
- Products of n prime factors, with n larger than two.
Each of these categories forces us to implement different parts of the algorithm, which can set up problems that are more or less difficult to solve. Even, a bad choice could lead us to a dead end.
Nevertheless, nothing prevents us from rewinding and going back if we get stuck. When we are faced with reasonable doubt about going one way or another in TDD, it’s best to take note about the state of the development, and mark that point as a point of return in case we get ourselves into some code swamp. Just go back and think again. Making mistakes is also information.
What have we learned in this kata
- With this kata we’ve learned how, as we add tests and they become more specific, the algorithm becomes more general
- We’ve also seen that we get better results when we prioritize the simplest transformations (changes in the production code)