{-# 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

ey0jIE9QVElPTlNfR0hDIC1PMiAjLX0KCm1vZHVsZSBNYWluIHdoZXJlCgppbXBvcnQgRGF0YS5BcnJheS5VbmJveGVkCgptYWluICA9IGRvIHNwZWMgPC0gbWFwIHJlYWQgLiB0YWtlIDIgLiB3b3JkcyA8JD4gZ2V0TGluZSAgCiAgICAgICAgICAgY2FzZSBzcGVjIG9mICAKICAgICAgICAgICAgIC0tIFtuXSAgICAgLT4gcHJpbnQgLiB0YWtlIDEwIC4gZHJvcCAobi0xMCkgJCBwcmltZXNUTVdFIAogICAgICAgICAgICAgW24sbGltXSAtPiBwcmludCAkIHByaW1lc0xpbUFPRSBsaW0gbgoKLS0gYXJyYXktYmFzZWQgU2lldmUgb2YgRXJhdG9zdGhlbmVzLCB1c2luZyBhbiBhcnJheSB0aGF0IGlzIHBhc3NlZCBhcyAKLS0gYW4gYWNjdW11bGF0aW5nIGFyZ3VtZW50IGJldHdlZW4gc3RlcHMgb2YgaXRlcmF0aXZlIGNvbXB1dGF0aW9uLCBhbmQgCi0tIGFzIHN1Y2ggaXMgbGlhYmxlIHRvIHRoZSBkZXN0cnVjdGl2ZSB1cGRhdGUgKGRvZXNuJ3QgaGFwcGVuLCBidXQgc3RpbGwgaXMgZmFzdCwgIAotLSBvbiB1bmJveGVkIGFycmF5cywgd2l0aCBleHBsaWNpdCB0eXBlIHNpZ25hdHVyZSwgR0hDLWNvbXBpbGVkIHdpdGggLU8yKSwgIAotLSB3b3JraW5nIHdpdGggb2RkcyBvbmx5ICAgICAgICAgKG9yaWdpbmFsOiBpZGVvbmUuY29tL2RFMGlVKQoKcHJpbWVzTGltQU9FIDo6IEludCAtPiBJbnQgLT4gKEludCxbSW50XSkKcHJpbWVzTGltQU9FIG0gbiB8IG0gPiAyID0gc2lldmUgMyAoIGFjY3VtQXJyYXkgY29uc3QgVHJ1ZSAoMSxtMikgW10gKQogIHdoZXJlCiAgICBtMiA9IChtLTEpIGBkaXZgIDIKICAgIHIgID0gZmxvb3IgLiBzcXJ0ICQgZnJvbUludGVncmFsIG0gKyAxCiAgICBzaWV2ZSA6OiBJbnQgLT4gVUFycmF5IEludCBCb29sIC0+IChJbnQsIFtJbnRdKSAgLS0gMjAxNzogbW92ZWQgdHlwZSBkZWNsIGhlcmUKICAgIHNpZXZlIHAgYSAKICAgICAgfCBwID4gciAgPSBsZXQgIGsgPSAxMAogICAgICAgICAgICAgICAgICAgICAgKGwsdSkgPSBib3VuZHMgYQogICAgICAgICAgICAgICAgICAgICAgbGVuICAgPSAxICsgbGVuZ3RoIFsoKSB8IChpLFRydWUpIDwtIGFzc29jcyBhXSAgCiAgICAgICAgICAgICAgICAgICAgICBpeHMgICA9IHJldmVyc2UgJCB0YWtlIChsZW4tbitrKSBbaSB8IGk8LVt1LHUtMS4ubF0sIGEhaV0KICAgICAgICAgICAgICAgICAgICAgIGxhc3QgID0gKGlmIGxlbiA8IG4gdGhlbiBbMl0gZWxzZSBbXSkgKysKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgWzIqaSsxIHwgaSA8LSB0YWtlIGsgaXhzXQogICAgICAgICAgICAgICAgICAgIGluICAgKCBsZW4sIGxhc3QgKQogICAgICB8IGEhcDIgICAgICA9IHNpZXZlIChwKzIpICQgYS8vWyhpLEZhbHNlKSB8IGkgPC0gW3EyLCBxMitwLi5tMl1dCiAgICAgIHwgb3RoZXJ3aXNlID0gc2lldmUgKHArMikgYQogICAgICAgICAgICAgICAgICAgICAgIHdoZXJlIHAyID0gKHAtMSkgYGRpdmAgMgogICAgICAgICAgICAgICAgICAgICAgICAgICAgIHEyID0gKHAqcC0xKSBgZGl2YCAyCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgCi0tIDIwMTc6IE5COiBuZXdlciBjb21waWxlciBjdXJyZW50bHkgaW4gdXNlIHJ1bnMgdGhpcyBjb2RlIGFsbW9zdCAzeCBmYXN0ZXIuCi0tICAgICAgIGFiUFNPeC1kZXJpdmVkIGNvZGUgKGZvciBvZGRzLCB0aGF0IGlzKSBtaWdodCBiZSBmYXN0ZXIuCgotLSAxbTo3ODQ5ODowLjA0LTQuOCAyNzUwMTU5OjIwMGs6MC4wOS00LjggNTgwMDA3OTo0MDBrOjAuMjEtNS44IDE1NDg1ODYzOjFtOjAuNjctNy44IDMyNDUyODQzOjJtOjIuMTYtMTEuOQoKLS0gNjc4Njc5Njc6NG06NS42My0yNC4yIDEwNDM5NTMwMTo2bTo5Ljg0LTM5LjYgMTIyOTQ5ODIzOjdtOjEyLjIwLTM2LjUgMTQxNjUwOTM5OjhtOjE0LjYxLTQwLjY=

MTAwMDAwMCAxNTQ4NTg2MyAgICAob2xkZXIgSWRlb25lIHVzZWQgR0hDICg2LjguLi4uKSkKNDAwMDAwIDU4MDAwNzkgICAgIChub3cgaXQncyB0d2ljZSBzbG93ZXIsIHdpdGggR0hDICg3LjYuMykgLi4uPyk=

1000000 15485863    (older Ideone used GHC (6.8....))
400000 5800079     (now it's twice slower, with GHC (7.6.3) ...?)