# 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

classSieve

definitialize(num)

@limit=num

end

defprimes

enumer=(2..@limit).to_a

enumer.eachdo|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 unlessnum

break ifnum*num > top

(num*num).step(top,num)do|val|

primes[val - 2] = nil

end

end

primes.compact

end

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.

deftest_find_first_prime

skip

expected=[2]

assert_equal expected, Sieve.new(2).primes

end

deftest_find_primes_up_to_10

skip

expected=[2, 3, 5, 7]

assert_equal expected, Sieve.new(10).primes

end

deftest_limit_is_prime

skip

expected=[2, 3, 5, 7, 11, 13]

assert_equal expected, Sieve.new(13).primes

end

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