bench/shootout/nsieve.ruby

   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
   7 def 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
  24 end
  25
  26 n = (ARGV[0] || 2).to_i
  27
  28 Flags = "\x1" * ( 2 ** n * 10_000)
  29
  30 n.downto(n-2) do |exponent|
  31   break if exponent < 0
  32   m = (1 << exponent) * 10_000
  33   # m = (2 ** exponent) * 10_000
  34   count = sieve(m)
  35   printf "Primes up to %8d %8d\n", m, count
  36 end