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