Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

DZone's Guide to

# Sieve Of Eratosthenes In Ruby

· ·
Free Resource

Comment (0)

Save
{{ articles[0].views | formatCount}} 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
``````
Topics:

Comment (0)

Save
{{ articles[0].views | formatCount}} Views

Opinions expressed by DZone contributors are their own.

# {{ parent.title || parent.header.title}}

### {{ parent.tldr }}

{{ parent.urlSource.name }}