primes_bench.rb

module Kernel
  SKIP_2357 = [2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4,
               2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4,
               2, 4, 2, 10, 2, 10]

  def iterate(start, &f)
    Enumerator.new do |y|
      loop do
        y << start
        start = f.call start
      end
    end
  end

  def concat(*xss)
    Enumerator.new do |y|
      xss.each do |xs|
        xs.each { |x| y << x }
      end
    end
  end

  def prime?(primes, n)
    primes.none? do |p|
      return true if p*p > n
      n % p == 0
    end
  end
end


class HashmapSieve
  def initialize(n)
    @n = n
    @primes = Enumerator.new do |y|
      sieve = {}
      iterate(2) { |i| i + 1 }.each do |current|
        if sieve.has_key? current
          sieve.delete(current).each do |p|
            sieve.update(current + p => [p]) do |_, prime_factors|
              prime_factors << p
            end
          end
        else
          y << current
          sieve.update(current ** 2 => [current])
        end
      end
    end
  end

  def last
    @primes.lazy.drop(@n - 1).peek
  end
end

require 'priority_queue/CPriorityQueue'
# i'm pretty sure this still doesn't use the native extension
class PqSieve
  def initialize(n)
    @n = n
    wheel = SKIP_2357.cycle
    candidates = concat([2,3,5,7], iterate(11) { |i| i + wheel.next })

    @primes = Enumerator.new do |y|
      sieve = CPriorityQueue.new
      candidates.each do |candidate|
        if sieve.empty? || candidate < sieve.min_priority
          y << candidate
          sieve[candidate] = candidate ** 2
        else
          found = false
          while sieve.min_priority <= candidate
            prime, p = sieve.delete_min
            sieve[prime] = p + prime
            found = candidate == p
          end
          if !found
            y << candidate
            sieve[candidate] = candidate ** 2
          end
        end
      end
    end
  end

  def last
    @primes.lazy.drop(@n - 1).peek
  end
end

class TrialDivision
  def initialize(n)
    @n = n
    wheel = SKIP_2357.cycle
    candidates = concat([2,3,5,7], iterate(11) { |i| i + wheel.next })
    @primes = Enumerator.new do |y|
      primes = []
      candidates.each do |current|
        if prime? primes, current
          y << current
          primes << current
        end
      end
    end
  end

  def last
    @primes.lazy.drop(@n - 1).peek
  end
end

class TrialDivPreComp
  attr_reader :last

  def initialize(n)
    primes = []
    wheel = SKIP_2357.cycle
    candidates = concat([2,3,5,7], iterate(11) { |i| i + wheel.next })
    while primes.count < n
      current = candidates.next
      if prime? primes, current
        primes << current
      end
    end
    @last = primes.last
  end
end

class Sieve
  attr_reader :check

  def initialize(n)
    sieve = (2..n).to_a
    candidate = 2
    limit = candidate ** 2
    while limit <= n
      if sieve[candidate - 2]
        (limit..n).step(candidate).each do |i|
          sieve[i - 2] = nil
        end
      end
      candidate += 1
      limit = candidate ** 2
    end
    sieve.compact!
    @check = [sieve.last, sieve.count]
  end
end

N = 600_000
puts "Verify: #{N}th prime"
STDOUT << 'Hashmap sieve lazy    = ' << (answer = HashmapSieve.new(N).last) << $/
#STDOUT << 'Priority queue sieve  = ' << PqSieve.new(N).last << $/
#STDOUT << 'Trial division lazy   = ' << TrialDivision.new(N).last << $/
#STDOUT << 'Trial division strict = ' << TrialDivPreComp.new(N).last << $/
STDOUT << 'Sieve check           = ' << Sieve.new(answer).check << $/

require 'benchmark'
Benchmark.bm(25) do |bench|
#  3.times { TrialDivPreComp.new(N).last } # warmup
  bench.report('Trial division strict') { 1.times { TrialDivPreComp.new(N).last } }

#  3.times { TrialDivision.new(N).last }
  bench.report('Trial division lazy') { 1.times { TrialDivision.new(N).last } }

#  3.times { HashmapSieve.new(N).last }
  bench.report('Hashmap sieve lazy') { 1.times { HashmapSieve.new(N).last } }

#  3.times { PqSieve.new(N).last }
  bench.report('Priority queue sieve lazy') { 1.times { PqSieve.new(N).last } }

#  3.times { Sieve.new(answer).check }
  bench.report('Sieve classical') { 1.times { Sieve.new(answer).check } }
end

__END__
Verify: 600000th prime
Hashmap sieve lazy    = 8960453
Sieve check           = [8960453, 600000]
                                user     system      total        real
Trial division strict      45.760000   0.690000  46.450000 ( 46.481180)
Trial division lazy        45.260000   0.430000  45.690000 ( 45.713766)
Hashmap sieve lazy         44.380000   0.080000  44.460000 ( 44.514218)
Priority queue sieve lazy  81.960000   2.150000  84.110000 ( 89.971031)
Sieve classical             2.980000   0.130000   3.110000 (  3.805723)