Class: Prime8::Strategies::EratosthenesSieveStrategy

Inherits:
Strategy
  • Object
show all
Defined in:
lib/prime_8/strategies/eratosthenes_sieve_strategy.rb

Instance Method Summary collapse

Methods inherited from Strategy

#get_nth_prime, #get_through_nth_prime

Constructor Details

#initialize ⇒ EratosthenesSieveStrategy

Returns a new instance of EratosthenesSieveStrategy.



4
5
6
 
# File 'lib/prime_8/strategies/eratosthenes_sieve_strategy.rb', line 4

def initialize
  super
end

Instance Method Details

#compute_primes ⇒ Object 



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
 
# File 'lib/prime_8/strategies/eratosthenes_sieve_strategy.rb', line 8

def compute_primes
  max_segment_size = 1e6.to_i
  max_cached_prime = @primes.last
  @max_checked = max_cached_prime + 1 if max_cached_prime > @max_checked

  segment_min = @max_checked
  segment_max = [segment_min + max_segment_size, max_cached_prime * 2].min
  root = Integer(Math.sqrt(segment_max).floor)

  sieving_primes = @primes[1 .. -1].take_while { |prime| prime <= root }
  offsets = Array.new(sieving_primes.size) do |i|
    (-(segment_min + 1 + sieving_primes[i]) / 2) % sieving_primes[i]
  end

  segment = ((segment_min + 1) .. segment_max).step(2).to_a
  sieving_primes.each_with_index do |prime, index|
    composite_index = offsets[index]
    while composite_index < segment.size do
      segment[composite_index] = nil
      composite_index += prime
    end
  end
  @primes = @primes | segment.compact
  @max_checked = segment_max
end