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