#!/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

IyEvdXNyL2Jpbi9ydWJ5CgpkZWYgcHJpbWVzKHVwdG8sICZibG9jaykKICByZXR1cm4gbGFyZ2VfcHJpbWVzKHVwdG8sICZibG9jaykgaWYgdXB0byA+IDI1MDAwCiAgdXB0byAtPSAxCiAgZmxhZ3MgPSBBcnJheS5uZXcodXB0bywgdHJ1ZSkKICAoMC4uLnVwdG8tMSkuZWFjaCBkbyB8aXwKICAgIGlmIGZsYWdzW2ldIHRoZW4KICAgICAgcHJpbWUgPSBpICsgMgogICAgICBrID0gaSArIHByaW1lCiAgICAgIHdoaWxlIGsgPCB1cHRvIGRvCiAgICAgICAgZmxhZ3Nba10gPSBmYWxzZQogICAgICAgIGsgKz0gcHJpbWUKICAgICAgZW5kCiAgICAgIGJsb2NrLmNhbGwocHJpbWUpCiAgICBlbmQKICBlbmQKZW5kCgpkZWYgbGFyZ2VfcHJpbWVzKHVwdG8sICZibG9jaykKICAjIFRoZSBBbGdvcml0aG0gaXMgYWRhcHRlZCBmcm9tIGh0dHA6Ly93Li4uY29udGVudC1hdmFpbGFibGUtdG8tYXV0aG9yLW9ubHkuLi5rLmNvbS9+anJtL3ByaW50cHJpbWVzLmh0bWwKICAjIFRoaXMgY29kZSBpcyBhIHRyYW5zbGF0ZWQgdmVyc2lvbiBvZiBBbmRyZWFzIFJhYWIncyAjbGFyZ2VQcmltZXNVcFRvOmRvOiBtZXRob2QKICAjIHdoaWNoIHdhcyB3cml0dGVuIGZvciB0aGUgU3F1ZWFrIFNtYWxsdGFsayBlbnZpcm9ubWVudC4gCgogIGlkeF9saW1pdCA9IE1hdGguc3FydCh1cHRvKSArIDEKCiAgZmxhZ3MgPSBBcnJheS5uZXcoKHVwdG8gKyAyMzA5KSAvIDIzMTAgKiA2MCArIDYwLCAweEZGKQogICMgZmxhZ3MgPSAiXDM3NyIgKiAoKHVwdG8gKyAyMzA5KSAvIDIzMTAgKiA2MCArIDYwKQoKICBwcmltZXNfdXBfdG9fMjMxMCA9IFtdCiAgcHJpbWVzKDIzMTApIHt8cHJpbWV8IHByaW1lc191cF90b18yMzEwIDw8IHByaW1lfQoKICBtYXNrX2JpdF9pZHggPSBBcnJheS5uZXcoMjMxMCkKICBiaXRfaWR4ID0gLTEKICBtYXNrX2JpdF9pZHhbMF0gPSAoYml0X2lkeCArPSAxKQogIG1hc2tfYml0X2lkeFsxXSA9IChiaXRfaWR4ICs9IDEpCgogICgwLi40KS5lYWNoIHt8aXwgYmxvY2suY2FsbChwcmltZXNfdXBfdG9fMjMxMFtpXSl9CgogIGlkeCA9IDUKICAoMi4uMjMwOSkuZWFjaCBkbyB8bnwKICAgIHdoaWxlIHByaW1lc191cF90b18yMzEwW2lkeF0gPCBuIGRvIGlkeCArPSAxIGVuZAogICAgaWYgbiA9PSBwcmltZXNfdXBfdG9fMjMxMFtpZHhdIHRoZW4KICAgICAgbWFza19iaXRfaWR4W25dID0gKGJpdF9pZHggKz0gMSkKICAgIGVsc2lmIG4gJSAyID09IDAgfHwgbiAlIDMgPT0gMCB8fCBuICUgNSA9PSAwIHx8IG4gJSA3ID09IDAgfHwgbiAlIDExID09IDAgdGhlbgogICAgICBtYXNrX2JpdF9pZHhbbl0gPSAwCiAgICBlbHNlCiAgICAgIG1hc2tfYml0X2lkeFtuXSA9IChiaXRfaWR4ICs9IDEpCiAgICBlbmQKICBlbmQKCiAgKDEzLi51cHRvKS5zdGVwKDIpIGRvIHxufAogICAgaWYgKG1hc2tfYml0ID0gbWFza19iaXRfaWR4W24gJSAyMzEwXSkgIT0gMCB0aGVuCiAgICAgIGJ5dGVfaWR4ID0gbiAvIDIzMTAgKiA2MCArIChtYXNrX2JpdC0xIDw8IC0zKQogICAgICBiaXRfaWR4ID0gMSA8PCAobWFza19iaXQgJiA3KQogICAgICBpZiBmbGFnc1tieXRlX2lkeF0gJiBiaXRfaWR4ICE9IDAgdGhlbgogICAgICAgIGJsb2NrLmNhbGwobikKICAgICAgICBpZiBuIDwgaWR4X2xpbWl0IHRoZW4KICAgICAgICAgIGlkeCA9IG4gKiBuCiAgICAgICAgICBpZiAoaWR4ICYgMSkgPT0gMCB0aGVuIGlkeCArPSBuIGVuZAogICAgICAgICAgd2hpbGUgaWR4IDw9IHVwdG8gZG8KICAgICAgICAgICAgaWYgKG1hc2tfYml0ID0gbWFza19iaXRfaWR4W2lkeCAlIDIzMTBdKSAhPSAwIHRoZW4KICAgICAgICAgICAgICBieXRlX2lkeCA9IGlkeCAvIDIzMTAgKiA2MCArIChtYXNrX2JpdC0xIDw8IC0zKQogICAgICAgICAgICAgIG1hc2tfYml0ID0gMjU1IC0gKDEgPDwgKG1hc2tfYml0ICYgNykpCiAgICAgICAgICAgICAgZmxhZ3NbYnl0ZV9pZHhdID0gZmxhZ3NbYnl0ZV9pZHhdICYgbWFza19iaXQKICAgICAgICAgICAgZW5kCiAgICAgICAgICAgIGlkeCArPSAyICogbgogICAgICAgICAgZW5kCiAgICAgICAgZW5kCiAgICAgIGVuZAogICAgZW5kCiAgZW5kCmVuZAoKbWF4ID0gQVJHVi5zaXplID09IDEgPyBBUkdWWzBdLnRvX2kgOiAxMDAKYyA9IDAKcSA9IDAKcHJpbWVzKG1heCkge3xwcmltZXwgcSA9IHByaW1lOyBjICs9IDF9CnB1dHMgcSwgYw==