Class: Prime::EratosthenesSieve

Inherits:
Object
  • Object
show all
Includes:
Singleton
Defined in:
lib/prime.rb

Overview

Internal use. An implementation of eratosthenes’s sieve

Constant Summary collapse

BITS_PER_ENTRY =

each entry is a set of 16-bits in a Fixnum

16
NUMS_PER_ENTRY =

twiced because even numbers are omitted

BITS_PER_ENTRY * 2
ENTRIES_PER_TABLE = 
8
NUMS_PER_TABLE = 
NUMS_PER_ENTRY * ENTRIES_PER_TABLE
FILLED_ENTRY = 
(1 << NUMS_PER_ENTRY) - 1

Instance Method Summary collapse

Constructor Details

#initialize ⇒ EratosthenesSieve

:nodoc:



431
432
433
434
435
436
437
438
 
# File 'lib/prime.rb', line 431

def initialize # :nodoc:
  # bitmap for odd prime numbers less than 256.
  # For an arbitrary odd number n, @tables[i][j][k] is
  # * 1 if n is prime,
  # * 0 if n is composite,
  # where i,j,k = indices(n)
  @tables = [[0xcb6e, 0x64b4, 0x129a, 0x816d, 0x4c32, 0x864a, 0x820d, 0x2196].freeze]
end

Instance Method Details

#next_to(n) ⇒ Object

returns the least odd prime number which is greater than n.



441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
 
# File 'lib/prime.rb', line 441

def next_to(n)
  n = (n-1).div(2)*2+3 # the next odd number to given n
  table_index, integer_index, bit_index = indices(n)
  loop do
    extend_table until @tables.length > table_index
    for j in integer_index...ENTRIES_PER_TABLE
      if !@tables[table_index][j].zero?
        for k in bit_index...BITS_PER_ENTRY
          return NUMS_PER_TABLE*table_index + NUMS_PER_ENTRY*j + 2*k+1 if !@tables[table_index][j][k].zero?
        end
      end
      bit_index = 0
    end
    table_index += 1; integer_index = 0
  end
end