CharExponent = 3
BitsPerChar = 1 << CharExponent
LowMask = BitsPerChar - 1

def sieve(m)
  ret = []
  items = "\xFF" * ((m / BitsPerChar) + 1)
  masks = ""
  BitsPerChar.times do |b|
    masks << (1 << b).chr
  end

  count = 0
  pmax = m - 1
  2.step(pmax, 1) do |p|
    if items[p >> CharExponent][p & LowMask] == 1
      ret << p
      count += 1
      p.step(pmax, p) do |mult|
	a = mult >> CharExponent
	b = mult & LowMask
	items[a] -= masks[b] if items[a][b] != 0
        #p items
      end
    end
  end
  #count
  ret
end

n = (ARGV[0] || 2).to_i
n.step(n - 2, -1) do |exponent|
  break if exponent < 0
  m = 2 ** exponent * 10_000
  primes = sieve(m)
  count = primes.size
  puts
  printf "Primes up to %8d %8d\n", m, count
  puts "last ten primes: #{primes[-10..-1].join(' ')}"
  puts
end

max = Integer(ARGV.shift || 100)
	
sieve = [nil, nil] + (2 .. max).to_a
	
(2 .. Math.sqrt(max)).each do |i|
  next unless sieve[i]
  (i*i).step(max, i) do |j|
    sieve[j] = nil
  end
end
	
puts sieve.compact.join(", ")



#------------------------------------



#!/usr/local/bin/ruby -w

require 'benchmark' 

class Integer

   def primes1

      primes = [nil, nil].concat((2..self).to_a)

      (2 .. Math.sqrt(self).floor).each do |i|
         next unless primes[i]
            (i*i).step(self, i) do |j|
               primes[j] = nil
            end
      end
	
      primes.compact!

   end  


   def primes2

      sieve = []
      3.step(self, 2) { |i| sieve[i] = i }
      sieve[1] = nil
      sieve[2] = 2

      3.step(Math.sqrt(self).floor, 2) do |i| 
         next unless sieve[i]
         (i*i).step(self, i) do |j|
            sieve[j] = nil
         end
      end

      sieve.compact!

   end 


   def primes3

      n2 = 0
      i = 0
      sieve = []

      while n2 < self
         n1 = 6*i+1       # cf. http://betterexplained.com/articles/another-look-at-prime-numbers/ and
         n2 = n1+4        # http://everything2.com/index.pl?node_id=1176369
         i += 1

         sieve[n1] = n1
         sieve[n2] = n2

      end  

      sieve[1] = nil
      sieve[2] = 2
      sieve[3] = 3
      sieve[-1] = nil

      5.step(Math.sqrt(self).floor, 2) do |i| 
         next unless sieve[i]
         (i*i).step(self, i) do |j|     
            sieve[j] = nil
         end
      end   

      sieve.compact!

   end 

end



limit = 10_000_000
limit = 5_000_000
limit = 1_000_000
limit = 500_000
limit = 100_000
limit = 10_000
limit = 7_500
limit = 5_000
limit = 1_000
limit = 500_000

ret1 = nil
ret2 = nil
ret3 = nil

# cf. primegen.c, http://cr.yp.to/primegen.html and
# prime_sieve.c, http://wwwhomes.uni-bielefeld.de/achim/prime_sieve.html

Benchmark.bm(14) do |t|       

   t.report("primes up to #{limit}: ") do
      ret1 = limit.primes1
   end 

   t.report("primes up to #{limit}: ") do
      ret2 = limit.primes2
   end 

   t.report("primes up to #{limit}: ") do
      ret3 = limit.primes3
   end 


end 


puts

#p ret1.first(10)
p ret1.last(10)
p ret1.size

puts

#p ret2.first(10)
p ret2.last(10)
p ret2.size

puts 

#p ret3.first(10)
p ret3.last(10)
p ret3.size