Class: PrimeNumbers::AlgorithmSieveOfEratosthenes

Inherits:
Object
  • Object
show all
Defined in:
lib/prime-numbers/algorithms/sieve_of_eratosthenes.rb

Instance Method Summary collapse

Instance Method Details

#generate(lower_bound, upper_bound) ⇒ Object 



3
4
5
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
 
# File 'lib/prime-numbers/algorithms/sieve_of_eratosthenes.rb', line 3

def generate lower_bound, upper_bound
    sqrt_upper = (Math.sqrt upper_bound).round
    numbers = Array.new(upper_bound) {|e| e =  false}
    primes = []

    (2 .. sqrt_upper).each do |m|
      if !numbers[m]

        if m >= lower_bound
          primes << m
        end

        k = m * m
        while k <= upper_bound
          numbers[k] = true
          k += m
        end

      end
    end

    (sqrt_upper+1 .. upper_bound).each do |n|
      if !numbers[n] && n >= lower_bound
        primes << n
      end
    end
    primes
end

#is_prime?(number) ⇒ Boolean 



32
33
34
 
# File 'lib/prime-numbers/algorithms/sieve_of_eratosthenes.rb', line 32

def is_prime? number
  number < 2 ? false : !generate(number,number).empty?
end