Seive of Eratosthenes

seive_of_eratosthenes.rb

# Naive implementation of the Seive of Eratosthenes
#
#   # Usage
#   SeiveOfEratosthenes.find_primes(10_000)
#
class SeiveOfEratosthenes
  attr_reader :set_array
  # Return an array of all prime numbers below ceiling
  def self.find_primes(ceiling)
    new(ceiling).mark_table.filter_table.set_array
  end

  def initialize(ceiling)
    @ceiling = ceiling
    @set_table = initialize_set_table
    @set_array = []
  end

  def mark_table
    # For all numbers 'A' from 2 to sqrt(ceiling)
    (2..Math.sqrt(@ceiling)).to_a.each do |a|
      # Skip to next number if already marked
      next unless @set_table[a].nil?

      # Mark as prime
      @set_table[a] = :prime

      # For all multiples of A < ceiling
      multiple_of_a = a
      while multiple_of_a < @ceiling
        multiple_of_a += a

        # Mark multiples as composite
        @set_table[multiple_of_a] = :composite
      end
    end
    self
  end

  def filter_table
    # { 2 => :prime, 3 => :prime...} becomes [[2, :prime], [3, :prime]...]
    @set_array = @set_table.to_a

    # Mark unmarked numbers as prime
    @set_array.map! { |a| a[1].nil? ? [a[0], :prime] : a }

    # Filter out all composite numbers
    @set_array.reject! { |a| a[1] == :composite }

    # [[2, :prime], [3, :prime]...] becomes [2, 3...]
    @set_array.map! { |a| a[0] }
    self
  end

  private

  def initialize_set_table
    # [2...N] becomes {2 => nil, 3 => nil,.. N => nil}
    Hash[(2..@ceiling).to_a.map! { |a| [a, nil] }]
  end
end