summaryrefslogtreecommitdiff
path: root/benchmark/bm_so_nsieve.rb
blob: a65cc7823316767daa02a02ee50d3dd02a9eecad (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# The Computer Language Shootout
# http://shootout.alioth.debian.org/
#
# contributed by Glenn Parker, March 2005
# modified by Evan Phoenix, Sept 2006

def sieve(m)
  flags = Flags.dup[0,m]
  count = 0
  pmax = m - 1
  p = 2
  while p <= pmax
    unless flags[p].zero?
      count += 1
      mult = p
      while mult <= pmax
        flags[mult] = 0
        mult += p
      end
    end
    p += 1
  end
  count
end

n = 9 # (ARGV[0] || 2).to_i
Flags = ("\x1" * ( 2 ** n * 10_000)).unpack("c*")

n.downto(n-2) do |exponent|
  break if exponent < 0
  m = (1 << exponent) * 10_000
  # m = (2 ** exponent) * 10_000
  count = sieve(m)
  printf "Primes up to %8d %8d\n", m, count
end