1# The Computer Language Shootout
2# http://shootout.alioth.debian.org/
3#
4# contributed by Glenn Parker, March 2005
5# modified by Evan Phoenix, Sept 2006
6
7def sieve(m)
8  flags = Flags.dup[0,m]
9  count = 0
10  pmax = m - 1
11  p = 2
12  while p <= pmax
13    unless flags[p].zero?
14      count += 1
15      mult = p
16      while mult <= pmax
17        flags[mult] = 0
18        mult += p
19      end
20    end
21    p += 1
22  end
23  count
24end
25
26n = 9 # (ARGV[0] || 2).to_i
27Flags = ("\x1" * ( 2 ** n * 10_000)).unpack("c*")
28
29n.downto(n-2) do |exponent|
30  break if exponent < 0
31  m = (1 << exponent) * 10_000
32  # m = (2 ** exponent) * 10_000
33  count = sieve(m)
34  printf "Primes up to %8d %8d\n", m, count
35end
36