diff options
| author | yugui <yugui@b2dd03c8-39d4-4d8f-98ff-823fe69b080e> | 2009-10-18 00:55:34 +0000 |
|---|---|---|
| committer | yugui <yugui@b2dd03c8-39d4-4d8f-98ff-823fe69b080e> | 2009-10-18 00:55:34 +0000 |
| commit | c0b42eedeafd49c867ffd776d95a6aeb1d7b732a () | |
| tree | 16d7024103a08c2c3322eb1dd66dfb36a8740a98 /lib/prime.rb | |
| parent | 79a8955f8d99d6e603a90a8038da461687d275ec (diff) | |
* test/test_prime.rb
(TestPrime#test_eratosthenes_works_fine_after_timeout): test for [ruby-dev:39465]. * lib/prime.rb (Prime::EratosthenesSieve): fixed [ruby-dev:39465]. suppressed memory reallocation. constantified some magic numbers. git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@25388 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
| -rw-r--r-- | lib/prime.rb | 62 |
1 files changed, 43 insertions, 19 deletions
@@ -408,44 +408,68 @@ class Prime class EratosthenesSieve include Singleton def initialize # :nodoc: # bitmap for odd prime numbers less than 256. - # For an arbitrary odd number n, @table[i][j] is 1 when n is prime where i,j = n.divmod(32) . - @table = [0xcb6e, 0x64b4, 0x129a, 0x816d, 0x4c32, 0x864a, 0x820d, 0x2196] end # returns the least odd prime number which is greater than +n+. def next_to(n) - n = (n-1).div(2)*2+3 # the next odd number of given n - i,j = n.divmod(32) loop do - extend_table until @table.length > i - if !@table[i].zero? - (j...32).step(2) do |k| - return 32*i+k if !@table[i][k.div(2)].zero? end end - i += 1; j = 1 end end private def extend_table - orig_len = @table.length - new_len = [orig_len**2, orig_len+256].min - lbound = orig_len*32 - ubound = new_len*32 - @table.fill(0xFFFF, orig_len...new_len) (3..Integer(Math.sqrt(ubound))).step(2) do |p| - i, j = p.divmod(32) - next if @table[i][j.div(2)].zero? - start = (lbound.div(2*p)*2+1)*p # odd multiple of p which is greater than or equal to lbound (start...ubound).step(2*p) do |n| - i, j = n.divmod(32) - @table[i] &= 0xFFFF ^ (1<<(j.div(2))) end end end end |