Sha256: 82688eb2e33f9c8b885ea04c0007c8405e592c0cdaf1f8ef0abb95f438753374
Contents?: true
Size: 1.11 KB
Versions: 10
Compression:
Stored size: 1.11 KB
Contents
=begin rdoc
== Sieve of Eratosthenes
Use the Sieve of Eratosthenes algorithm to generate a list of prime
numbers. The method is an introduction to iteration, using iterators
to make and filter lists of numbers, and a while loop to repeat the
filtering step until no more composite numbers are left in the worklist.
=end
include Math
module RubyLabs
module SieveLab
# Call sieve(n) to create an array of prime numbers between 2 and n
# :begin :sieve
def sieve(n)
return [] if n < 2
worklist = []
(n-1).times { |i| worklist << i+2 }
primes = []
while worklist.first < sqrt(n)
primes << worklist.first
worklist.delete_if { |x| x % primes.last == 0 }
end
return primes + worklist
end
# :end :sieve
# A first version of the sieve, iterates until the worklist is empty
# :begin :proto_sieve
def proto_sieve(n)
return [] if n < 2
worklist = []
(n-1).times { |i| worklist << i+2 }
primes = []
while worklist.length > 0
primes << worklist.first
worklist.delete_if { |x| x % primes.last == 0 }
end
return primes
end
# :end :proto_sieve
end # SieveLab
end # RubyLabs
Version data entries
10 entries across 10 versions & 1 rubygems