# TDD Beyond Basics : Prime Factors Kata

# Objective

Learn to evaluate whether the amount of test code to production code is reasonable or not.

# Discussion

The principle of Ensure Commensurate Effort and Responsibility states that the amount of effort it takes to to write or modify tests should not exceed the effort it takes to implement the corresponding functionality. This principle is discussed in depth in xUnit Test Patterns by Gerard Meszaros.

# Problem Statement

Factorize a positive integer number into its prime factors.

# Problem Domain Analysis

Here is some sample input and output.

# Solution Domain Analysis

Start with the divisor 2 and repeatedly reduce n by a factor of 2 until 2 is no longer an exact divisor. We then try 3 as a divisor and again repeat the reduction process and so son until n has been reduced to 1.

Consider n = 60. Marking with an * the unsuccessful attempts to divide, we have:

That is, 60 = 2 x 2 x 3 x 5, and those numbers are primes.

# Steps

## Step 1

Create `prime_factor_spec.rb`

:

```
describe PrimeFactor do
it 'should return 2 for input of 2' do
prime_factorial = PrimeFactor.new(2)
prime = prime_factorial.calculate
expect(prime).to eq([2])
end
end
```

Create `prime_factor.rb`

:

```
class PrimeFactor
def initialize(n)
@n = n
end
def calculate
end
end
```

The test fails for the right reason.

## Step 2

Change `prime_factor.rb`

:

```
class PrimeFactor
def initialize(n)
@n = n
end
def calculate
[2]
end
end
```

The test passes.

## Step 3

Add the next test:

```
it 'should return 3 for input of 3' do
prime_factorial = PrimeFactor.new(3)
prime = prime_factorial.calculate
expect(prime).to eq([3])
end
```

The test fails.

## Step 4

Change the calculate method as follows:

```
def calculate
[@n]
end
```

Both tests pass.

## Step 5

Add the next test:

```
it 'should return [2,2] for input of 4' do
prime_factorial = PrimeFactor.new(4)
prime = prime_factorial.calculate
expect(prime).to eq([2,2])
end
```

This test fails.

## Step 6

Add the following quick and dirty implementation.

```
def calculate
result = []
remainder = @n / 2
result << 2
result << remainder if Prime.prime?(remainder)
result
end
```

This test now passes. But it breaks the second spec. We will make it pending for now.

## Step 7

Here is some notes from Prime Factor discussion:

```
n = 12
12 / 2 = 6
```

Is 12 evenly divisible by 2? Yes. Add 2 to the result list.

The remainder 6 is not a prime number, so we need to continue processing. Try 2 again:

```
6 / 2 = 3
```

6 is evenly divisible by 2, so add 2 to the result list. Is the remainder 3 a prime? Yes. Add it to the result list and STOP. Using this as the reference, here is the implementation that passes the test:

```
def calculate
result = []
until Prime.prime?(@n)
if (@n % 2) == 0
result << 2
@n = @n / 2
elsif (@n % 3) == 0
result << 3
@n = @n / 3
elsif
end
end
result << @n
result
end
```

From the notes, we have found the terminating condition for our algorithm. We are also using the concept of reduction we learned in an earlier article.

## Step 8

Uncomment the second test. This test passes without making any changes because our code is generic enough to handle the edge case of one element.

## Step 9

```
it 'should return [3,7,7] for input of 147' do
prime_factorial = PrimeFactor.new(147)
prime = prime_factorial.calculate
expect(prime).to eq([3,7,7])
end
```

## Step 10

Here is the quick and dirty implementation that makes all the tests pass.

```
def calculate
result = []
until Prime.prime?(@n)
if (@n % 2) == 0
result << 2
@n = @n / 2
elsif (@n % 3) == 0
result << 3
@n = @n / 3
elsif (@n % 7) == 0
result << 7
@n = @n / 7
end
end
result << @n
result
end
```

## Step 11

Reading the mathisfun.com worked out examples and converting them into tests has given us more insight into the problem. We see that we need to continuously look for the given number is evenly divisible by a series of prime numbers.

We have already discussed how to generate primes using The Sieve of Erastosthenes in a previous article. Let's adapt that function so that given a number, erastosthenes function will give us the next prime for us to use in the divisible by prime check condition. For an in-depth discussion on how the Sieve of Erastosthenes can be used to solve prime factor problem read the book How to Solve It by Computer (Prentice-Hall International Series in Computer Science) by R. G. Dromey.

After experimenting in the irb, here is a function that assumes we only need a list of primes upto 100, it takes a number and gives the next prime in the list. This function is added to our existing Erastostenes class.

```
def self.next(n)
e = Erastostenes.new(100)
primes = e.calculate
primes.detect{|x| x > n}
end
```

## Step 12

Let's refactor our code so that it uses our Sieve of Erastostenes for the evenly divisible check. Here is a partial refactoring:

```
def calculate
result = []
current_prime = 2
until Prime.prime?(@n)
if (@n % current_prime) == 0
result << current_prime
@n = @n / current_prime
elsif (@n % 3) == 0
result << 3
@n = @n / 3
elsif (@n % 7) == 0
result << 7
@n = @n / 7
end
end
result << @n
result
end
```

All tests passes. Let's continue the refactoring.

## Step 13

Here is the cleaned up version of the calculate method:

```
def calculate
result = []
current_prime = 2
until Prime.prime?(@n)
if (@n % current_prime) == 0
result << current_prime
@n = @n / current_prime
else
current_prime = Erastostenes.next(current_prime)
end
end
result << @n
result
end
```

All tests pass.

## Step 14

I added more specs one by one to check the answer for different numbers, here is the new specs:

```
it 'should return [2,3] for input of 6' do
prime_factorial = PrimeFactor.new(6)
prime = prime_factorial.calculate
expect(prime).to eq([2, 3])
end
it 'should return [2,2, 2] for input of 8' do
prime_factorial = PrimeFactor.new(8)
prime = prime_factorial.calculate
expect(prime).to eq([2, 2, 2])
end
it 'should return [2,7] for input of 14' do
prime_factorial = PrimeFactor.new(14)
prime = prime_factorial.calculate
expect(prime).to eq([2, 7])
end
it 'should handle any number' do
prime_factorial = PrimeFactor.new(168)
prime = prime_factorial.calculate
expect(prime).to eq([2, 2, 2, 3, 7])
end
```

All the tests pass without making any modification to our solution.

# Complete Code Listing

```
require_relative 'erastosthenes.rb'
require 'prime'
class PrimeFactor
def initialize(n)
@n = n
end
def calculate
result = []
current_prime = 2
until Prime.prime?(@n)
if (@n % current_prime) == 0
result << current_prime
@n = @n / current_prime
else
current_prime = Erastostenes.next(current_prime)
end
end
result << @n
result
end
end
describe PrimeFactor do
it 'should return 2 for input of 2' do
prime_factorial = PrimeFactor.new(2)
prime = prime_factorial.calculate
expect(prime).to eq([2])
end
it 'should return 3 for input of 3' do
prime_factorial = PrimeFactor.new(3)
prime = prime_factorial.calculate
expect(prime).to eq([3])
end
it 'should return [2,2] for input of 4' do
prime_factorial = PrimeFactor.new(4)
prime = prime_factorial.calculate
expect(prime).to eq([2,2])
end
it 'should return [2, 2, 3] for input of 12' do
prime_factorial = PrimeFactor.new(12)
prime = prime_factorial.calculate
expect(prime).to eq([2,2,3])
end
it 'should return [3,7,7] for input of 147' do
prime_factorial = PrimeFactor.new(147)
prime = prime_factorial.calculate
expect(prime).to eq([3,7,7])
end
it 'should return [2,3] for input of 6' do
prime_factorial = PrimeFactor.new(6)
prime = prime_factorial.calculate
expect(prime).to eq([2, 3])
end
it 'should return [2,2, 2] for input of 8' do
prime_factorial = PrimeFactor.new(8)
prime = prime_factorial.calculate
expect(prime).to eq([2, 2, 2])
end
it 'should return [2,7] for input of 14' do
prime_factorial = PrimeFactor.new(14)
prime = prime_factorial.calculate
expect(prime).to eq([2, 7])
end
it 'should handle any number' do
prime_factorial = PrimeFactor.new(168)
prime = prime_factorial.calculate
expect(prime).to eq([2, 2, 2, 3, 7])
end
it 'should handle any number' do
prime_factorial = PrimeFactor.new(330)
prime = prime_factorial.calculate
expect(prime).to eq([2, 3, 5, 11])
end
end
```

# Discussion

We have 20 lines of production code and almost 70 lines of test code. Ideally we want the minimal number of tests that gives us enough confidence in our code. After you write the story test, do some exploratory testing and write some tests based on exploratory tests, evaluate whether the test to code ratio is reasonable.

We made a simplifying assumption in generating a prime factors list by limiting it to 100. You can improve this implementation by reading the Prime Factors Analysis article.

# Exercises

- Can you delete some of the tests? What is the minimum number of tests for this problem?
- Study the Prime Factors Analysis. Compute the prime number required only up to a certain number discussed in that article.
- To find prime factors of a given number, you can use this online tool Find the Prime Factors of a Number

# Related Articles