Prime::EratosthenesSieve

Parent:ObjectIncluded modules:Singleton

Internal use. An implementation of eratosthenes' sieve

Public Class Methods

new() Show source

# File lib/prime.rb, line 425
def initialize
  @primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101]
  # @max_checked must be an even number
  @max_checked = @primes.last + 1
end

Public Instance Methods

get_nth_prime(n) Show source

# File lib/prime.rb, line 431
def get_nth_prime(n)
  compute_primes while @primes.size <= n
  @primes[n]
end

Private Instance Methods

compute_primes() Show source

# File lib/prime.rb, line 437
def compute_primes
  # max_segment_size must be an even number
  max_segment_size = 1e6.to_i
  max_cached_prime = @primes.last
  # do not double count primes if #compute_primes is interrupted
  # by Timeout.timeout
  @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)

  segment = ((segment_min + 1) .. segment_max).step(2).to_a

  (1..Float::INFINITY).each do |sieving|
    prime = @primes[sieving]
    break if prime > root
    composite_index = (-(segment_min + 1 + prime) / 2) % prime
    while composite_index < segment.size do
      segment[composite_index] = nil
      composite_index += prime
    end
  end

  @primes.concat(segment.compact!)

  @max_checked = segment_max
end

 Ruby Core © 1993–2017 Yukihiro Matsumoto

Licensed under the Ruby License.

Ruby Standard Library © contributors

Licensed under their own licenses.