Class Prime::EratosthenesSieve
In: lib/backports/1.9.1/stdlib/prime.rb
Parent: Object

Internal use. An implementation of eratosthenes‘s sieve

Methods

next_to  

Included Modules

Singleton

Constants

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

Public Instance methods

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

[Source]

     # File lib/backports/1.9.1/stdlib/prime.rb, line 427
427:     def next_to(n)
428:       n = (n-1).div(2)*2+3 # the next odd number to given n
429:       table_index, integer_index, bit_index = indices(n)
430:       loop do
431:         extend_table until @tables.length > table_index
432:         for j in integer_index...ENTRIES_PER_TABLE
433:           if !@tables[table_index][j].zero?
434:             for k in bit_index...BITS_PER_ENTRY
435:               return NUMS_PER_TABLE*table_index + NUMS_PER_ENTRY*j + 2*k+1 if !@tables[table_index][j][k].zero?
436:             end
437:           end
438:           bit_index = 0
439:         end
440:         table_index += 1; integer_index = 0
441:       end
442:     end

[Validate]