TDD Basics : The Sieve of Erastosthenes

The Sieve of Erastosthenes


The most efficient way to find all of the small primes is by using a sieve such as Sieve of Eratosthenes.

  1. Make a list of all the integers <= n and > 1
  2. Strike out the multiples of all primes <= sqrt(n), then the numbers that are left are the primes.

Example


Find all the primes upto a given number n. For 30 the result is 2,3,5,7,11,13,17,19,23,29. Let's find all the primes <= 30

1) First list the numbers from 2 to 30

alt text

2) First number is prime, so keep it
3) Cross out multiples of 2

alt text

4) The first number left is 3, so it is the first odd prime, keep it.
5) Cross out all multiples of 3

alt text

6) Now the first number left is 5, the second odd prime, keep it.
7) Cross out all multiples of 5

alt text

8) The next number 7 is larger than the square root of 30, so there are no multiples of 7 to eliminate. Therefore the sieve is complete.

Erastostenes Javascript Demo


Erastostenes Javascript Demo

Algorithm


while square of(current_prime) <= n
  apply the sieve
end

Terminating Condition is square of(current_prime) > or = n

Steps


Step 1

Let's write the test for step 1 of the example. Create erastosthenes_spec.rb file with the following content:

describe Erastostenes do
  it 'makes a list of all integers <= 30 and greater than 1' do
    e = Erastostenes.new(30)
    number_list = e.number_list
    expect(number_list).to eq([2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30])
  end
end

Step 2

Here is the empty implementation that fails for the right reason:

class Erastostenes
  def initialize(n)
    @n = n
  end

  def number_list

  end
end

Step 3

Implement the number_list as follows:

def number_list
  (2..@n).to_a
end

The test passes.

Step 4

Let's add the test for the second step in the example as follows:

it 'should cross out multiples of 2' do
  e = Erastostenes.new(30)
  cross_out_multiples_of_two = e.cross_out_multiples_of_two

  expect(cross_out_multiples_of_two).to eq([2,3,5,7,9,11,13,15,17,19,21,23,25,27,29])
end

This test fails.

Step 5

Here is the implementation that passes the test.

def cross_out_multiples_of_two
  number_list.reject do |x|
    unless x == 2
     x % 2 == 0 
    end
  end    
end

Step 6

Let's write the test for the next step as follows:

it 'should cross out multiples of 2 and 3' do
  e = Erastostenes.new(30)
  cross_out_multiples_of_three = e.cross_out_multiples_of_three

  expect(cross_out_multiples_of_three).to eq([2,3,5,7,11,13,17,19,23,25,29])    
end

Step 7

We are not just testing step 2 by itself. We are developing the algorithm incrementally so it needs to build on top of the previous step. The following implementation passes the test.

def cross_out_multiples_of_three
  list = cross_out_multiples_of_two
  list.reject do |x|
    unless x == 3
     x % 3 == 0 
    end
  end        
end

Step 8

The following implementation passes the test.

def cross_out_multiples_of_five
  list = cross_out_multiples_of_three
  list.reject do |x|
    unless x == 5
     x % 5 == 0 
    end
  end
end

Step 9

Let's refactor by eliminating the duplication in Erastostenes class.

class Erastostenes 
  def initialize(n)
    @n = n
    @list = (2..@n).to_a  
  end

  def number_list
      (2..@n).to_a  
  end

  def cross_out_multiples_of_two
    cross_out_multiples_of(2)
  end

  def cross_out_multiples_of_three
    @list = cross_out_multiples_of(2)
    cross_out_multiples_of(3)
  end

  def cross_out_multiples_of_five
    list = cross_out_multiples_of_three
    list.reject! do |x|
      unless x == 5
       x % 5 == 0 
      end
    end
  end

  private

  def cross_out_multiples_of(number)
    @list.reject! do |x|
      unless x == number
       x % number == 0 
      end
    end    
  end

end

We are still green.

Step 10

Here is the complete listing as of now, erastosthenes_spec.rb:

describe Erastostenes do
  it 'makes a list of all integers <= 30 and greater than 1' do
    e = Erastostenes.new(30)
    number_list = e.number_list
    expect(number_list).to eq([2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30])
  end

  it 'should cross out multiples of 2' do
    e = Erastostenes.new(30)
    cross_out_multiples_of_two = e.cross_out_multiples_of_two

    expect(cross_out_multiples_of_two).to eq([2,3,5,7,9,11,13,15,17,19,21,23,25,27,29])
  end

  it 'should cross out multiples of 2 and 3' do
    e = Erastostenes.new(30)
    cross_out_multiples_of_three = e.cross_out_multiples_of_three

    expect(cross_out_multiples_of_three).to eq([2,3,5,7,11,13,17,19,23,25,29])    
  end

  it 'should cross out multiples of 2, 3 and 5' do
    e = Erastostenes.new(30)
    cross_out_multiples_of_five = e.cross_out_multiples_of_five

    expect(cross_out_multiples_of_five).to eq([2,3,5,7,11,13,17,19,23,29])
  end

end

erastosthenes.rb:

class Erastostenes 
  def initialize(n)
    @n = n
    @list = (2..@n).to_a  
  end

  def number_list
    (2..@n).to_a  
  end

  def cross_out_multiples_of_two
    cross_out_multiples_of(2)
  end

  def cross_out_multiples_of_three
    @list = cross_out_multiples_of(2)
    cross_out_multiples_of(3)
  end

  def cross_out_multiples_of_five
    list = cross_out_multiples_of_three
    list.reject! do |x|
      unless x == 5
       x % 5 == 0 
      end
    end
  end

  private

  def cross_out_multiples_of(number)
    @list.reject! do |x|
      unless x == number
       x % number == 0 
      end
    end    
  end

end

Step 11

Let's add the story test as follows:

it 'should calculate the prime numbers for 30' do
  e = Erastostenes.new(30)
  result = e.calculate

  expect(result).to eq([2,3,5,7,11,13,17,19,23,29])
end

Step 12

By looking at our discussion in the algorithm section and the terminating condition we came up with, we know what the real implementation will be like.

def calculate
  list = number_list
  list.each do |x|
    unless x >= Math.sqrt(@n)
      cross_out_multiples_of(x)
    end
  end
  @list
end

This passes all our tests.

Step 13

Let's cleanup. Here is the listing after deleting unnecessary code and tests.

class Erastostenes 
  def initialize(n)
    @n = n
    @list = (2..@n).to_a  
  end

  def number_list
      (2..@n).to_a  
  end

  def calculate
    list = number_list
    list.each do |x|
      unless x >= Math.sqrt(@n)
        cross_out_multiples_of(x)
      end
    end
    @list
  end

  private

  def cross_out_multiples_of(number)
    @list.reject! do |x|
      unless x == number
       x % number == 0 
      end
    end    
  end

end

describe Erastostenes do
  it 'makes a list of all integers <= 30 and greater than 1' do
    e = Erastostenes.new(30)
    number_list = e.number_list
    expect(number_list).to eq([2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30])
  end

  it 'should calculate the prime numbers for 30' do
    e = Erastostenes.new(30)
    result = e.calculate

    expect(result).to eq([2,3,5,7,11,13,17,19,23,29])
  end

end

The deleted tests were necessary in the beginning to get us moving in the right direction to solving the problem. Now they are no longer required.

Step 14

Final cleanup.

class Erastostenes 
  def initialize(n)
    @n = n
    @list = number_list
  end

  def calculate
    list = number_list
    list.each do |x|
      unless x >= Math.sqrt(@n)
        cross_out_multiples_of(x)
      end
    end
    @list
  end

  private

  def cross_out_multiples_of(number)
    @list.reject! do |x|
      unless x == number
       x % number == 0 
      end
    end    
  end

  def number_list
    (2..@n).to_a  
  end

end


describe Erastostenes do

  it 'should calculate the prime numbers for 30' do
    e = Erastostenes.new(30)
    result = e.calculate

    expect(result).to eq([2,3,5,7,11,13,17,19,23,29])
  end

end

We are green after refactoring. Remember to modify either the test code or the production code and run the tests. Do not modify both at the same time without running the tests.

Discussion


If you see the specs there are lot of arrays. I always think twice before coupling the specs to the data structure choice in the production code. Do not write tests that are dependent on data structures. Because, the data structures are implementation details and can change to optimize performance without changing the behavior. If we couple our tests to the implementation details, our tests will be brittle and break even when the behavior remains the same but when the implementation changes.

Exercise


The spec used 30 as the example. What is the minimum number that we can use and still have high confidence that our code works?


Related Articles


Ace the Technical Interview

  • Easily find the gaps in your knowledge
  • Get customized lessons based on where you are
  • Take consistent action everyday
  • Builtin accountability to keep you on track
  • You will solve bigger problems over time
  • Get the job of your dreams

Take the 30 Day Coding Skills Challenge

Gain confidence to attend the interview

No spam ever. Unsubscribe anytime.