{-# OPTIONS_GHC -O2 #-}

module Main where

import Data.Array.Unboxed

main  = do spec <- map read . take 2 . words <$> getLine  
           case spec of  
             -- [n]     -> print . take 10 . drop (n-10) $ primesTMWE 
             [n,lim] -> print $ primesLimAOE lim n

-- array-based Sieve of Eratosthenes, using an array that is passed as 
-- an accumulating argument between steps of iterative computation, and 
-- as such is liable to the destructive update (doesn't happen, but still is fast,  
-- on unboxed arrays, with explicit type signature, GHC-compiled with -O2),  
-- working with odds only         (original: ideone.com/dE0iU)

primesLimAOE :: Int -> Int -> (Int,[Int])
primesLimAOE m n | m > 2 = sieve 3 ( accumArray const True (1,m2) [] )
  where
    m2 = (m-1) `div` 2
    r  = floor . sqrt $ fromIntegral m + 1
    sieve :: Int -> UArray Int Bool -> (Int, [Int])  -- 2017: moved type decl here
    sieve p a 
      | p > r  = let  k = 10
                      (l,u) = bounds a
                      len   = 1 + length [() | (i,True) <- assocs a]  
                      ixs   = reverse $ take (len-n+k) [i | i<-[u,u-1..l], a!i]
                      last  = (if len < n then [2] else []) ++
                              [2*i+1 | i <- take k ixs]
                    in   ( len, last )
      | a!p2      = sieve (p+2) $ a//[(i,False) | i <- [q2, q2+p..m2]]
      | otherwise = sieve (p+2) a
                       where p2 = (p-1) `div` 2
                             q2 = (p*p-1) `div` 2
                             
-- 2017: NB: newer compiler currently in use runs this code almost 3x faster.
--       abPSOx-derived code (for odds, that is) might be faster.

-- 1m:78498:0.04-4.8 2750159:200k:0.09-4.8 5800079:400k:0.21-5.8 15485863:1m:0.67-7.8 32452843:2m:2.16-11.9

-- 67867967:4m:5.63-24.2 104395301:6m:9.84-39.6 122949823:7m:12.20-36.5 141650939:8m:14.61-40.6