| 316 |
316 |
def rewind
|
| 317 |
317 |
initialize
|
| 318 |
318 |
end
|
|
319 |
|
|
320 |
def each(&block)
|
|
321 |
return self.dup unless block
|
|
322 |
if @ubound
|
|
323 |
EratosthenesSieve.instance.each(@ubound, &block)
|
|
324 |
else
|
|
325 |
loop do
|
|
326 |
block.call(succ)
|
|
327 |
end
|
|
328 |
end
|
|
329 |
end
|
| 319 |
330 |
alias next succ
|
| 320 |
331 |
end
|
| 321 |
332 |
|
| ... | ... | |
| 427 |
438 |
ENTRIES_PER_TABLE = 8
|
| 428 |
439 |
NUMS_PER_TABLE = NUMS_PER_ENTRY * ENTRIES_PER_TABLE
|
| 429 |
440 |
FILLED_ENTRY = (1 << NUMS_PER_ENTRY) - 1
|
|
441 |
BITS_MASK = 0b00011111
|
|
442 |
BITS_SHIFT = 1
|
|
443 |
ENTRY_MASK = 0b11100000
|
|
444 |
ENTRY_SHIFT = 5
|
|
445 |
TABLE_SHIFT = 8
|
| 430 |
446 |
|
| 431 |
447 |
def initialize # :nodoc:
|
| 432 |
448 |
# bitmap for odd prime numbers less than 256.
|
| ... | ... | |
| 437 |
453 |
@tables = [[0xcb6e, 0x64b4, 0x129a, 0x816d, 0x4c32, 0x864a, 0x820d, 0x2196].freeze]
|
| 438 |
454 |
end
|
| 439 |
455 |
|
|
456 |
def each(ubound, &block)
|
|
457 |
last_value = nil
|
|
458 |
last_value = block.call(2) if ubound > 1
|
|
459 |
ubound = (ubound-1).div(2)*2+1 # the biggist odd number less than or equal to ubound
|
|
460 |
to_table_index, to_integer_index, to_bit_index = indices(ubound)
|
|
461 |
extend_table until @tables.length > to_table_index
|
|
462 |
|
|
463 |
for i in 0..to_table_index
|
|
464 |
table_base = NUMS_PER_TABLE * i
|
|
465 |
tables_i = @tables[i]
|
|
466 |
end_integer_index = (i == to_table_index ? to_integer_index+1 : ENTRIES_PER_TABLE)
|
|
467 |
for j in 0...end_integer_index
|
|
468 |
tables_i_j = tables_i[j]
|
|
469 |
unless tables_i_j.zero?
|
|
470 |
integer_base = table_base + NUMS_PER_ENTRY * j
|
|
471 |
end_bit_index = (i == to_table_index && j == to_integer_index ?
|
|
472 |
to_bit_index+1 : BITS_PER_ENTRY)
|
|
473 |
for k in 0...end_bit_index
|
|
474 |
unless tables_i_j[k].zero?
|
|
475 |
last_value = block.call(integer_base + 2*k+1)
|
|
476 |
end
|
|
477 |
end
|
|
478 |
end
|
|
479 |
end
|
|
480 |
end
|
|
481 |
last_value
|
|
482 |
end
|
|
483 |
|
| 440 |
484 |
# returns the least odd prime number which is greater than +n+.
|
| 441 |
485 |
def next_to(n)
|
| 442 |
486 |
n = (n-1).div(2)*2+3 # the next odd number to given n
|
| ... | ... | |
| 462 |
506 |
# indices: |-| k | j | i
|
| 463 |
507 |
# because of NUMS_PER_ENTRY, NUMS_PER_TABLE
|
| 464 |
508 |
|
| 465 |
|
k = (n & 0b00011111) >> 1
|
| 466 |
|
j = (n & 0b11100000) >> 5
|
| 467 |
|
i = n >> 8
|
|
509 |
k = (n & BITS_MASK) >> BITS_SHIFT
|
|
510 |
j = (n & ENTRY_MASK) >> ENTRY_SHIFT
|
|
511 |
i = n >> TABLE_SHIFT
|
| 468 |
512 |
return i, j, k
|
| 469 |
513 |
end
|
| 470 |
514 |
|
| ... | ... | |
| 473 |
517 |
ubound = lbound + NUMS_PER_TABLE
|
| 474 |
518 |
new_table = [FILLED_ENTRY] * ENTRIES_PER_TABLE # which represents primarity in lbound...ubound
|
| 475 |
519 |
(3..Integer(Math.sqrt(ubound))).step(2) do |p|
|
| 476 |
|
i, j, k = indices(p)
|
|
520 |
k = (p & BITS_MASK) >> BITS_SHIFT
|
|
521 |
j = (p & ENTRY_MASK) >> ENTRY_SHIFT
|
|
522 |
i = p >> TABLE_SHIFT
|
| 477 |
523 |
next if @tables[i][j][k].zero?
|
| 478 |
524 |
|
| 479 |
525 |
start = (lbound.div(p)+1)*p # least multiple of p which is >= lbound
|
| 480 |
526 |
start += p if start.even?
|
| 481 |
527 |
(start...ubound).step(2*p) do |n|
|
| 482 |
|
_, j, k = indices(n)
|
|
528 |
k = (n & BITS_MASK) >> BITS_SHIFT
|
|
529 |
j = (n & ENTRY_MASK) >> ENTRY_SHIFT
|
| 483 |
530 |
new_table[j] &= FILLED_ENTRY^(1<<k)
|
| 484 |
531 |
end
|
| 485 |
532 |
end
|