Class: PrimeFinder

Inherits:
Object
  • Object
show all
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