# 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 2) First number is prime, so keep it
3) Cross out multiples of 2 4) The first number left is 3, so it is the first odd prime, keep it.
5) Cross out all multiples of 3 6) Now the first number left is 5, the second odd prime, keep it.
7) Cross out all multiples of 5 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?

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