{-# OPTIONS_GHC -O2 #-}  -- unbounded merging idea due to Richard Bird
module Main where    -- double staged production idea due to Melissa O'Neill
                       -- tree folding idea Dave Bayer / Heinrich Apfelmus
main =                   -- simplified formulation by Will Ness
  do s <- getLine                       -- logBase (n2/n1) (t2/t1): ~ n^1.20
     print $ take 5 $ drop (read s-5) primes 
 
primes :: [Int]          
primes = 2 : _Y ((3:) . gaps 5 . _U . map (\x-> [x*x, x*x+2*x..]))
 
_Y g = g (_Y g)                   -- telescoping feed (recursive)
  -- = g xs where xs = g xs       -- double feed (corecursive, sharing) 
 
gaps k s@(x:xs) | k < x     = k : gaps (k+2) s      -- ~= [k,k+2..]\\s , 
                | otherwise =     gaps (k+2) xs     --    when s⊂[k,k+2..]
 
_U ((x:xs):t) = x : (union xs . _U  . pairs) t      -- ~= nub.sort.concat
  where 
    pairs (xs:ys:t) = union xs ys : pairs t
    union a@(x:xs) b@(y:ys) = case compare x y of
         LT -> x : union  xs b
         EQ -> x : union  xs ys
         GT -> y : union  a  ys

ey0jIE9QVElPTlNfR0hDIC1PMiAjLX0gIC0tIHVuYm91bmRlZCBtZXJnaW5nIGlkZWEgZHVlIHRvIFJpY2hhcmQgQmlyZAptb2R1bGUgTWFpbiB3aGVyZSAgICAtLSBkb3VibGUgc3RhZ2VkIHByb2R1Y3Rpb24gaWRlYSBkdWUgdG8gTWVsaXNzYSBPJ05laWxsCiAgICAgICAgICAgICAgICAgICAgICAgLS0gdHJlZSBmb2xkaW5nIGlkZWEgRGF2ZSBCYXllciAvIEhlaW5yaWNoIEFwZmVsbXVzCm1haW4gPSAgICAgICAgICAgICAgICAgICAtLSBzaW1wbGlmaWVkIGZvcm11bGF0aW9uIGJ5IFdpbGwgTmVzcwogIGRvIHMgPC0gZ2V0TGluZSAgICAgICAgICAgICAgICAgICAgICAgLS0gbG9nQmFzZSAobjIvbjEpICh0Mi90MSk6IH4gbl4xLjIwCiAgICAgcHJpbnQgJCB0YWtlIDUgJCBkcm9wIChyZWFkIHMtNSkgcHJpbWVzIAoKcHJpbWVzIDo6IFtJbnRdICAgICAgICAgIApwcmltZXMgPSAyIDogX1kgKCgzOikgLiBnYXBzIDUgLiBfVSAuIG1hcCAoXHgtPiBbeCp4LCB4KngrMip4Li5dKSkKICAKX1kgZyA9IGcgKF9ZIGcpICAgICAgICAgICAgICAgICAgIC0tIHRlbGVzY29waW5nIGZlZWQgKHJlY3Vyc2l2ZSkKICAtLSA9IGcgeHMgd2hlcmUgeHMgPSBnIHhzICAgICAgIC0tIGRvdWJsZSBmZWVkIChjb3JlY3Vyc2l2ZSwgc2hhcmluZykgCiAgICAKZ2FwcyBrIHNAKHg6eHMpIHwgayA8IHggICAgID0gayA6IGdhcHMgKGsrMikgcyAgICAgIC0tIH49IFtrLGsrMi4uXVxccyAsIAogICAgICAgICAgICAgICAgfCBvdGhlcndpc2UgPSAgICAgZ2FwcyAoaysyKSB4cyAgICAgLS0gICAgd2hlbiBz4oqCW2ssaysyLi5dCgpfVSAoKHg6eHMpOnQpID0geCA6ICh1bmlvbiB4cyAuIF9VICAuIHBhaXJzKSB0ICAgICAgLS0gfj0gbnViLnNvcnQuY29uY2F0CiAgd2hlcmUgCiAgICBwYWlycyAoeHM6eXM6dCkgPSB1bmlvbiB4cyB5cyA6IHBhaXJzIHQKICAgIHVuaW9uIGFAKHg6eHMpIGJAKHk6eXMpID0gY2FzZSBjb21wYXJlIHggeSBvZgogICAgICAgICBMVCAtPiB4IDogdW5pb24gIHhzIGIKICAgICAgICAgRVEgLT4geCA6IHVuaW9uICB4cyB5cwogICAgICAgICBHVCAtPiB5IDogdW5pb24gIGEgIHlz

MjAwMDAwMAo=

2000000