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
end

end

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

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.