Class: Prime::EratosthenesSieve
Relationships & Source Files | |
Super Chains via Extension / Inclusion / Inheritance | |
Instance Chain:
self,
Singleton
|
|
Inherits: | Object |
Defined in: | lib/prime.rb |
Overview
Internal use. An implementation of eratosthenes' sieve
Class Method Summary
- .new ⇒ EratosthenesSieve constructor
Instance Method Summary
- #get_nth_prime(n)
- #compute_primes private
Constructor Details
.new ⇒ EratosthenesSieve
# 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
Instance Method Details
#compute_primes (private)
[ GitHub ]# 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
#get_nth_prime(n)
[ GitHub ]# File 'lib/prime.rb', line 431
def get_nth_prime(n) compute_primes while @primes.size <= n @primes[n] end