Class: Prime::EratosthenesSieve

Inherits:
Object
  • Object
show all
Includes:
Singleton
Defined in:
lib/vendor/backports-3.3.5/lib/backports/1.9.1/stdlib/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:



418
419
420
421
422
423
424
425
 
# File 'lib/vendor/backports-3.3.5/lib/backports/1.9.1/stdlib/prime.rb', line 418

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.



428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
 
# File 'lib/vendor/backports-3.3.5/lib/backports/1.9.1/stdlib/prime.rb', line 428

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