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

Version Path
rubylabs-0.7.5 lib/sievelab.rb
rubylabs-0.7.4 lib/sievelab.rb
rubylabs-0.7.3 lib/sievelab.rb
rubylabs-0.7.2 lib/sievelab.rb
rubylabs-0.7.1 lib/sievelab.rb
rubylabs-0.7.0 lib/sievelab.rb
rubylabs-0.6.4 lib/sievelab.rb
rubylabs-0.6.2 lib/sievelab.rb
rubylabs-0.5.5 lib/sievelab.rb
rubylabs-0.5.4 lib/sievelab.rb