Sieve Of Eratosthenes In Ruby

• Tweet
• 

        From: http://bohnsack.com/2006/02/13/cs-442-project-1-sieve-of-eratosthenes/

Author: Matthew Bohnsack

max = Integer(ARGV.shift || 100)
	
sieve = [nil, nil] + (2 .. max).to_a
	
(2 .. Math.sqrt(max)).each do |i|
  next unless sieve[i]
  (i*i).step(max, i) do |j|
    sieve[j] = nil
  end
end
	
puts sieve.compact.join(", ")



#------------------------------------



#!/usr/local/bin/ruby -w

require 'benchmark' 

class Integer

   def primes1

      primes = [nil, nil].concat((2..self).to_a)

      (2 .. Math.sqrt(self).floor).each do |i|
         next unless primes[i]
            (i*i).step(self, i) do |j|
               primes[j] = nil
            end
      end
	
      primes.compact!

   end  


   def primes2

      sieve = []
      3.step(self, 2) { |i| sieve[i] = i }
      sieve[1] = nil
      sieve[2] = 2

      3.step(Math.sqrt(self).floor, 2) do |i| 
         next unless sieve[i]
         (i*i).step(self, i) do |j|
            sieve[j] = nil
         end
      end

      sieve.compact!

   end 


   def primes3

      n2 = 0
      i = 0
      sieve = []

      while n2 < self
         n1 = 6*i+1       # cf. http://betterexplained.com/articles/another-look-at-prime-numbers/ and
         n2 = n1+4        # http://everything2.com/index.pl?node_id=1176369
         i += 1

         sieve[n1] = n1
         sieve[n2] = n2

      end  

      sieve[1] = nil
      sieve[2] = 2
      sieve[3] = 3
      sieve[-1] = nil

      5.step(Math.sqrt(self).floor, 2) do |i| 
         next unless sieve[i]
         (i*i).step(self, i) do |j|     
            sieve[j] = nil
         end
      end   

      sieve.compact!

   end 

end



limit = 10_000_000
limit = 5_000_000
limit = 1_000_000
limit = 500_000
limit = 100_000
limit = 10_000
limit = 7_500
limit = 5_000
limit = 1_000
limit = 500_000

ret1 = nil
ret2 = nil
ret3 = nil

# cf. primegen.c, http://cr.yp.to/primegen.html and
# prime_sieve.c, http://wwwhomes.uni-bielefeld.de/achim/prime_sieve.html

Benchmark.bm(14) do |t|       

   t.report("primes up to #{limit}: ") do
      ret1 = limit.primes1
   end 

   t.report("primes up to #{limit}: ") do
      ret2 = limit.primes2
   end 

   t.report("primes up to #{limit}: ") do
      ret3 = limit.primes3
   end 


end 


puts

#p ret1.first(10)
p ret1.last(10)
p ret1.size

puts

#p ret2.first(10)
p ret2.last(10)
p ret2.size

puts 

#p ret3.first(10)
p ret3.last(10)
p ret3.size

Tags:
• math
• prime
• Primes
• Ruby
• sieve