DZone Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

Snippets has posted 5883 posts at DZone. View Full User Profile

# Sieve Of Eratosthenes In Ruby

03.26.2007
| 6729 views |
```        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
```
`    `
"Starting from scratch" is seductive but disease ridden
-Pithy Advice for Programmers