Feature #5378 ยป prime.patch
| lib/prime.rb | ||
|---|---|---|
|
def rewind
|
||
|
initialize
|
||
|
end
|
||
|
def each(&block)
|
||
|
return self.dup unless block
|
||
|
if @ubound
|
||
|
EratosthenesSieve.instance.each(@ubound, &block)
|
||
|
else
|
||
|
loop do
|
||
|
block.call(succ)
|
||
|
end
|
||
|
end
|
||
|
end
|
||
|
alias next succ
|
||
|
end
|
||
| ... | ... | |
|
ENTRIES_PER_TABLE = 8
|
||
|
NUMS_PER_TABLE = NUMS_PER_ENTRY * ENTRIES_PER_TABLE
|
||
|
FILLED_ENTRY = (1 << NUMS_PER_ENTRY) - 1
|
||
|
BITS_MASK = 0b00011111
|
||
|
BITS_SHIFT = 1
|
||
|
ENTRY_MASK = 0b11100000
|
||
|
ENTRY_SHIFT = 5
|
||
|
TABLE_SHIFT = 8
|
||
|
def initialize # :nodoc:
|
||
|
# bitmap for odd prime numbers less than 256.
|
||
| ... | ... | |
|
@tables = [[0xcb6e, 0x64b4, 0x129a, 0x816d, 0x4c32, 0x864a, 0x820d, 0x2196].freeze]
|
||
|
end
|
||
|
def each(ubound, &block)
|
||
|
last_value = nil
|
||
|
last_value = block.call(2) if ubound > 1
|
||
|
ubound = (ubound-1).div(2)*2+1 # the biggist odd number less than or equal to ubound
|
||
|
to_table_index, to_integer_index, to_bit_index = indices(ubound)
|
||
|
extend_table until @tables.length > to_table_index
|
||
|
for i in 0..to_table_index
|
||
|
table_base = NUMS_PER_TABLE * i
|
||
|
tables_i = @tables[i]
|
||
|
end_integer_index = (i == to_table_index ? to_integer_index+1 : ENTRIES_PER_TABLE)
|
||
|
for j in 0...end_integer_index
|
||
|
tables_i_j = tables_i[j]
|
||
|
unless tables_i_j.zero?
|
||
|
integer_base = table_base + NUMS_PER_ENTRY * j
|
||
|
end_bit_index = (i == to_table_index && j == to_integer_index ?
|
||
|
to_bit_index+1 : BITS_PER_ENTRY)
|
||
|
for k in 0...end_bit_index
|
||
|
unless tables_i_j[k].zero?
|
||
|
last_value = block.call(integer_base + 2*k+1)
|
||
|
end
|
||
|
end
|
||
|
end
|
||
|
end
|
||
|
end
|
||
|
last_value
|
||
|
end
|
||
|
# returns the least odd prime number which is greater than +n+.
|
||
|
def next_to(n)
|
||
|
n = (n-1).div(2)*2+3 # the next odd number to given n
|
||
| ... | ... | |
|
# indices: |-| k | j | i
|
||
|
# because of NUMS_PER_ENTRY, NUMS_PER_TABLE
|
||
|
k = (n & 0b00011111) >> 1
|
||
|
j = (n & 0b11100000) >> 5
|
||
|
i = n >> 8
|
||
|
k = (n & BITS_MASK) >> BITS_SHIFT
|
||
|
j = (n & ENTRY_MASK) >> ENTRY_SHIFT
|
||
|
i = n >> TABLE_SHIFT
|
||
|
return i, j, k
|
||
|
end
|
||
| ... | ... | |
|
ubound = lbound + NUMS_PER_TABLE
|
||
|
new_table = [FILLED_ENTRY] * ENTRIES_PER_TABLE # which represents primarity in lbound...ubound
|
||
|
(3..Integer(Math.sqrt(ubound))).step(2) do |p|
|
||
|
i, j, k = indices(p)
|
||
|
k = (p & BITS_MASK) >> BITS_SHIFT
|
||
|
j = (p & ENTRY_MASK) >> ENTRY_SHIFT
|
||
|
i = p >> TABLE_SHIFT
|
||
|
next if @tables[i][j][k].zero?
|
||
|
start = (lbound.div(p)+1)*p # least multiple of p which is >= lbound
|
||
|
start += p if start.even?
|
||
|
(start...ubound).step(2*p) do |n|
|
||
|
_, j, k = indices(n)
|
||
|
k = (n & BITS_MASK) >> BITS_SHIFT
|
||
|
j = (n & ENTRY_MASK) >> ENTRY_SHIFT
|
||
|
new_table[j] &= FILLED_ENTRY^(1<<k)
|
||
|
end
|
||
|
end
|
||
| test/test_prime.rb | ||
|---|---|---|
|
assert_not_include Prime.each(7*37).to_a, 7*37, "[ruby-dev:39465]"
|
||
|
end
|
||
|
def test_each_with_ubound
|
||
|
primes = []
|
||
|
value = Prime.each(541) do |p|
|
||
|
primes << p
|
||
|
end
|
||
|
assert_equal PRIMES, primes
|
||
|
assert_equal PRIMES, value
|
||
|
end
|
||
|
def test_each_inject_with_ubound
|
||
|
assert_equal PRIMES, Prime.each(541).inject([]) {|a, p| a << p}
|
||
|
assert_equal PRIMES[0, PRIMES.size-1], Prime.each(540).inject([]) {|a, p| a << p}
|
||
|
assert_equal [], Prime.each(1).inject([]) {|a, p| a << p}
|
||
|
assert_equal [2], Prime.each(2).inject([]) {|a, p| a << p}
|
||
|
assert_equal [2, 3], Prime.each(3).inject([]) {|a, p| a << p}
|
||
|
end
|
||
|
end
|
||