Class | Prime::EratosthenesSieve |
In: |
lib/backports/1.9.1/stdlib/prime.rb
|
Parent: | Object |
Internal use. An implementation of eratosthenes‘s sieve
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 |
returns the least odd prime number which is greater than n.
# 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