benchmark/bm_so_nsieve.rb

   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 = 9 # (ARGV[0] || 2).to_i
  27 Flags = ("\x1" * ( 2 ** n * 10_000)).unpack("c*")
  28
  29 n.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
  35 end