blob: 6f958ee44e75891f641561f2e69ef4fec14f66b9 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
#!/usr/bin/ruby
#coding: us-ascii
#
# The Great Computer Language Shootout
# http://shootout.alioth.debian.org/
#
# nsieve-bits in Ruby
# Contributed by Glenn Parker, March 2005
CharExponent = 3
BitsPerChar = 1 << CharExponent
LowMask = BitsPerChar - 1
def sieve(m)
items = "\xFF" * ((m / BitsPerChar) + 1)
masks = ""
BitsPerChar.times do |b|
masks << (1 << b).chr
end
count = 0
pmax = m - 1
2.step(pmax, 1) do |p|
if items[p >> CharExponent][p & LowMask] == 1
count += 1
p.step(pmax, p) do |mult|
a = mult >> CharExponent
b = mult & LowMask
items[a] -= masks[b] if items[a][b] != 0
end
end
end
count
end
n = 9 # (ARGV[0] || 2).to_i
n.step(n - 2, -1) do |exponent|
break if exponent < 0
m = 2 ** exponent * 10_000
count = sieve(m)
printf "Primes up to %8d %8d\n", m, count
end
|
