Class: Primes

Inherits:
Object
  • Object
show all
Defined in:
lib/primes.rb

Class Method Summary collapse

Class Method Details

.first(n) ⇒ Object

based on incremental sieve of eratosthenes algorithm described by: www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf



7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
# File 'lib/primes.rb', line 7

def self.first(n)
  composites = OrderedCompositeSequences.new
  primes = []
  current = 2

  while primes.size < n
    if composites.empty? || composites.next_composite > current
      primes << current
      composites.add_sequence_for current
      current += 1
    elsif composites.next_composite == current
      composites.take_next_composite!
      current += 1
    end

  end

  primes
end