# The Sieve of Eratosthenes

Working through the exercism.io ruby algorithms, I came across a problem that really interested me. The problem is called the Sieve of Eratosthenes. The explanation is below.

Write a program that uses the Sieve of Eratosthenes to find all the primes from 2 up to a given number.
The Sieve of Eratosthenes is a simple, ancient algorithm for finding all prime numbers up to any given limit. It does so by iteratively marking as composite (i.e. not prime) the multiples of each prime, starting with the multiples of 2.
Create your range, starting at two and continuing up to and including the given limit. (i.e. [2, limit])
The algorithm consists of repeating the following over and over:
- take the next available unmarked number in your list (it is prime)
- mark all the multiples of that number (they are not prime)
- Repeat until you have processed each number in your range.
When the algorithm terminates, all the numbers in the list that have not been marked are prime.
The wikipedia article has a useful graphic that explains the algorithm: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

My first solution to the problem was the following

`class Sieve  def initialize(num)    @limit = num  end  def primes    enumer = (2..@limit).to_a    enumer.each do |x|      ((x*2)..@limit).step(x).each{ |y| enumer.include?(y) ? enumer.delete(y) : next }    end  endend`

However, this solution suffers from a few drawbacks. Namely, it for every iteration it checks if the array includes a number. This is a time intensive process, causing the array to iterate of itself. These leaves my solution with a time complexity of O(n2).

A more efficient solution is something along the lines of this.

`def sieve(top)  primes = (2..top).to_a`
`  primes.each do |num|    next unless num    break if num*num > top    (num*num).step(top,num) do |val|      primes[val - 2] = nil    end  end`
`  primes.compactend`

Instead of iterating through the primes array each time, looking if it contains a number, you a just setting the correct values to nil. This also preserves space complexity by not using the delete method which would cause a new array to be built every time.

This solution is much closer to O(n) which I believe would be a close to an ideal time complexity for this problem. Could you make it more efficient? If so, here are some test cases to look at.

`def test_find_first_prime    skip    expected = [2]    assert_equal expected, Sieve.new(2).primes  end  def test_find_primes_up_to_10    skip    expected = [2, 3, 5, 7]    assert_equal expected, Sieve.new(10).primes  end  def test_limit_is_prime    skip    expected = [2, 3, 5, 7, 11, 13]    assert_equal expected, Sieve.new(13).primes  end  def test_primes_up_to_1000 # rubocop:disable Metrics/MethodLength    skip    expected = [      2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,      61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127,      131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193,      197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269,      271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349,      353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431,      433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503,      509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599,      601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673,      677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761,      769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857,      859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947,      953, 967, 971, 977, 983, 991, 997    ]    assert_equal expected, Sieve.new(1000).primes  end`

Shout out to stackoverflow and exercism.io for the assistance.

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.