Class: Prime8::Strategies::AtkinSieveStrategy

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

Instance Method Summary collapse

Methods inherited from Strategy

#get_nth_prime, #get_through_nth_prime

Constructor Details

#initialize ⇒ AtkinSieveStrategy

Returns a new instance of AtkinSieveStrategy.



6
7
8
9
10
11
 
# File 'lib/prime_8/strategies/atkin_sieve_strategy.rb', line 6

def initialize
  @first_set = %w(1 13 17 29 37 41 49 53).map(&:to_i)
  @second_set = %w(7 19 31 43).map(&:to_i)
  @third_set = %w(11 23 47 59).map(&:to_i)
  super
end

Instance Method Details

#compute_primes ⇒ Object 



14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
# File 'lib/prime_8/strategies/atkin_sieve_strategy.rb', line 14

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

  ((segment_min + 1) .. segment_max).step(2).each do |candidate|
    remainder = candidate % 60
    if @first_set.include?(remainder)
      candidate_is_prime = first_quadratic_form(candidate)
    elsif @second_set.include?(remainder)
      candidate_is_prime = second_quadradic_form(candidate)
    elsif @third_set.include?(remainder)
      candidate_is_prime = third_quadradic_form(candidate)
    end

    if candidate_is_prime && !has_prime_divisor?(candidate)
      @primes << candidate
    end
  end
  @max_checked = segment_max
end