#!/usr/bin/ruby

def primes(upto, &block)
  return large_primes(upto, &block) if upto > 25000
  upto -= 1
  flags = Array.new(upto, true)
  (0...upto-1).each do |i|
    if flags[i] then
      prime = i + 2
      k = i + prime
      while k < upto do
        flags[k] = false
        k += prime
      end
      block.call(prime)
    end
  end
end

def large_primes(upto, &block)
  # The Algorithm is adapted from http://w...content-available-to-author-only...k.com/~jrm/printprimes.html
  # This code is a translated version of Andreas Raab's #largePrimesUpTo:do: method
  # which was written for the Squeak Smalltalk environment. 

  idx_limit = Math.sqrt(upto) + 1

  flags = Array.new((upto + 2309) / 2310 * 60 + 60, 0xFF)
  # flags = "\377" * ((upto + 2309) / 2310 * 60 + 60)

  primes_up_to_2310 = []
  primes(2310) {|prime| primes_up_to_2310 << prime}

  mask_bit_idx = Array.new(2310)
  bit_idx = -1
  mask_bit_idx[0] = (bit_idx += 1)
  mask_bit_idx[1] = (bit_idx += 1)

  (0..4).each {|i| block.call(primes_up_to_2310[i])}

  idx = 5
  (2..2309).each do |n|
    while primes_up_to_2310[idx] < n do idx += 1 end
    if n == primes_up_to_2310[idx] then
      mask_bit_idx[n] = (bit_idx += 1)
    elsif n % 2 == 0 || n % 3 == 0 || n % 5 == 0 || n % 7 == 0 || n % 11 == 0 then
      mask_bit_idx[n] = 0
    else
      mask_bit_idx[n] = (bit_idx += 1)
    end
  end

  (13..upto).step(2) do |n|
    if (mask_bit = mask_bit_idx[n % 2310]) != 0 then
      byte_idx = n / 2310 * 60 + (mask_bit-1 << -3)
      bit_idx = 1 << (mask_bit & 7)
      if flags[byte_idx] & bit_idx != 0 then
        block.call(n)
        if n < idx_limit then
          idx = n * n
          if (idx & 1) == 0 then idx += n end
          while idx <= upto do
            if (mask_bit = mask_bit_idx[idx % 2310]) != 0 then
              byte_idx = idx / 2310 * 60 + (mask_bit-1 << -3)
              mask_bit = 255 - (1 << (mask_bit & 7))
              flags[byte_idx] = flags[byte_idx] & mask_bit
            end
            idx += 2 * n
          end
        end
      end
    end
  end
end

max = ARGV.size == 1 ? ARGV[0].to_i : 100
c = 0
q = 0
primes(max) {|prime| q = prime; c += 1}
puts q, c