fork(3) download
  1. {-# OPTIONS_GHC -O2 #-}
  2.  
  3. import Control.Monad
  4. import Control.Monad.ST
  5. import Data.Array.ST
  6. import Data.Array.Unboxed
  7.  
  8. main = do
  9. forM_ (words s) $ \w-> do
  10. -- let ps = primesTo (read w)
  11. -- print (length ps, last ps) -- leaks badly
  12. print (lastPrimes (read w)) -- no leak
  13.  
  14. sieveUA :: Int -> UArray Int Bool
  15. sieveUA top = runSTUArray $ do
  16. let m = (top-1) `div` 2
  17. r = floor . sqrt . fromIntegral $ top + 1
  18. sieve <- newArray (1,m) True -- :: ST s (STUArray s Int Bool)
  19. forM_ [1..r `div` 2] $ \i -> do
  20. isPrime <- readArray sieve i
  21. when isPrime $ -- ((2*i+1)^2-1)`div`2 = 2*i*(i+1)
  22. forM_ [2*i*(i+1), 2*i*(i+2)+1..m] $ \j ->
  23. writeArray sieve j False
  24. return sieve
  25.  
  26. primesTo :: Int -> [Int]
  27. primesTo top = 2 : [i*2+1 | (i,True) <- assocs $ sieveUA top]
  28.  
  29. lastPrimes :: Int -> (Int,[Int]) -- (nth, vals)
  30. lastPrimes top =
  31. let arr = sieveUA top
  32. (b,t) = bounds arr
  33. in
  34. ( 1 + length [() | (i,True) <- assocs arr]
  35. , (if (top < 13) then (2:) else id)
  36. $ reverse $ take 5 [ 2*i+1 | i <- [t,t-1..b], arr ! i ] )
  37.  
  38. {-
  39. ST Array [Int] ON ODDS
  40.   -= n =- -= top =-
  41.   30,000: 350,377: 0.01s 3.7MB
  42.   100,000: 1,299,709: 0.03s 3.7MB
  43.   300,000: 4,256,233: 0.10s 3.7MB
  44.   1 mln --> 15,485,863: 0.43s 4.8MB time space (s_0=3.7)
  45.   2 mln --> 32,452,843: 0.98s 5.8MB
  46.   4 mln --> 67,867,967: 2.31s 8.9MB 1m-> n^1.21 n^1.12
  47.   5 mln --> 86,028,121: 3.04s 9.9MB
  48.   6 mln --> 104,395,301: 3.77s 10.9MB (leak: was: ***6.7s-227MB***!!!)
  49. 6,500,000-> 113,648,393: 4.14s 10.9MB
  50.   7 mln --> 122,949,823: 4.52s 11.9MB
  51. 7,538,613-> 133,000,999: 4.95s 11.9MB
  52.   8 mln --> 141,650,939: 5.32s 13.0MB 4m-> n^1.20 n^0.84
  53.   9 mln --> 160,481,183: 6.12s 14.0MB
  54.  10 mln --> 179,424,673: 6.91s 15.0MB
  55.  15 mln --> 275,604,541: 11.01s 21.1MB
  56.  18 mln --> 334,214,459: 13.65s 24.2MB 8m-> n^1.16 n^0.97 (1m->n^1.01)
  57.  20 mln --> 373,587,883: TIMEOUT
  58. -}
Success #stdin #stdout 2.78s 12976KB
stdin
10
104395305
stdout
(4,[2,3,5,7])
(6000001,[104395237,104395267,104395289,104395301,104395303])