sieve-benchmark.rb

require 'benchmark'
 
class Integer
  def is_prime?
    return true if self == 2
    return false if self < 2 || self.even?
    
    i = 3
    while i**2 <= self 
      return false if self % i == 0
      i += 2
    end
    
    true
  end
end


def primes_sieve(max)
  nums = Array.new(max+1){true}
  nums[0] = nums[1] = false
  
  i = 2
  while i**2 <= max
    if nums[i]
      j = i**2
      
      while j <= max
        nums[j] = false
        j += i
      end
      
    end
    i += 1
  end
  
  nums.each_with_index.with_object([]) do |(prime, num), primes| 
    primes << num if prime
  end
end

def primes_upto_v1(n)
  (1..n).each_with_object([]) do |n, arr|
    arr << n if n.is_prime?
  end
end

def primes_upto_v2(n)
  primes, i = [], 2
  while i <= n
    primes << i if i.is_prime?
    i += 1
  end
  primes    
end

#n = 500
#p primes_sieve(n) 
#p primes_upto_v1(n)
#p primes_upto_v2(n)


trial_num = 1
[10, 25, 50, 75, 100, 500, 1000, 5000].each do |n|
  puts "\n\nTrial #{trial_num} (n = #{n}) :\n"
  Benchmark.bmbm do |x|
    x.report("primes_sieve:")   { for i in 1..n; primes_sieve(i); end }
    x.report("primes_upto_v1:") { for i in 1..n; primes_upto_v1(i); end }
    x.report("primes_upto_v2:") { for i in 1..n; primes_upto_v2(i); end }
  end
trial_num += 1
end

sieve.rb

def sieve(max)
  # create an array indexed by 0 to n = max
  nums = Array.new(max+1){true}
  nums[0] = nums[1] = false

  i = 2
  while i**2 <= max       # from 2 to sqrt(n)
    
    if nums[i]            # if current number is prime 
      j = i**2
      while j <= max
        nums[j] = false   # eliminate its square 
        j += i            # and all multiples thereafter
      end
    end

    i += 1
  end
  
  nums.each_with_index.with_object([]) do |(prime, num), primes| 
    primes << num if prime  # returns an array of primes
  end
end