class Prime::EratosthenesSieve
Internal use. An implementation of eratosthenes' sieve
Public Class Methods
new()
click to toggle source
# File lib/prime.rb, line 426 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)
click to toggle source
# File lib/prime.rb, line 432 def get_nth_prime(n) compute_primes while @primes.size <= n @primes[n] end
Private Instance Methods
compute_primes()
click to toggle source
# File lib/prime.rb, line 438 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) 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 segment.each do |prime| @primes.push prime unless prime.nil? end @max_checked = segment_max end