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