diff options
author | marcandre <marcandre@b2dd03c8-39d4-4d8f-98ff-823fe69b080e> | 2015-06-09 03:32:11 +0000 |
---|---|---|
committer | marcandre <marcandre@b2dd03c8-39d4-4d8f-98ff-823fe69b080e> | 2015-06-09 03:32:11 +0000 |
commit | 9d3c64a40a8190684155f3ee085a12a8f3dd2c72 (patch) | |
tree | 3be3c83ad982659d3c6c7c997bfbc86c52546579 /lib | |
parent | d46336e71731aa64d71d4573b2741b7de43ec340 (diff) | |
download | ruby-9d3c64a40a8190684155f3ee085a12a8f3dd2c72.tar.gz |
* lib/prime.rb: Simplify and optimize EratosthenesSieve
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@50802 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
Diffstat (limited to 'lib')
-rw-r--r-- | lib/prime.rb | 7 |
1 files changed, 4 insertions, 3 deletions
diff --git a/lib/prime.rb b/lib/prime.rb index 822f0f3ac0..ef0784a385 100644 --- a/lib/prime.rb +++ b/lib/prime.rb @@ -424,10 +424,11 @@ class Prime 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 } - segment = ((segment_min + 1) .. segment_max).step(2).to_a - sieving_primes.each do |prime| + + (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 |