Class: PrimeFinder
- Inherits:
-
Object
- Object
- PrimeFinder
- Defined in:
- lib/prime_finder.rb
Overview
Uses the Sieve of Eratosthenes algorithm to find the prime_finder numbers given an upper bound
Instance Method Summary collapse
Instance Method Details
#find_primes(*bounds) ⇒ Object
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
# File 'lib/prime_finder.rb', line 6 def find_primes *bounds if bounds.size==0 || bounds.size > 2 raise "Either specify a lower bound and upper bound OR just the upper bound." end if bounds.size == 1 lower_bound = 2 upper_bound = bounds[0] else lower_bound = bounds[0] upper_bound = bounds[1] end sqrt_upper = (Math.sqrt upper_bound).round working_arr = Array.new(upper_bound) {|e| e = false} return_arr = [] (2 .. sqrt_upper).each { |m| if !working_arr[m] if m >= lower_bound return_arr << m end k = m * m while k <= upper_bound working_arr[k] = true k += m end end } (sqrt_upper+1 .. upper_bound).each { |n| if !working_arr[n] && n >= lower_bound return_arr << n end } return_arr end |