Internal use. An implementation of Eratosthenes' sieve
# File lib/prime.rb, line 532 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.sqrt(segment_max) 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–2020 Yukihiro Matsumoto
Licensed under the Ruby License.
Ruby Standard Library © contributors
Licensed under their own licenses.