language: Haskell (ghc-7.4.1)
date: 91 days 15 hours ago
link:
visibility: private 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

{-# OPTIONS_GHC -O2 #-}
 
import Control.Monad
import Control.Monad.ST
import Data.Array.ST
import Data.Array.Unboxed
 
main = do
  s <- getContents
  forM_ (words s) $ \w-> do
    -- let ps = primesTo (read w)
    -- print (length ps, last ps)        -- leaks badly
    print (lastPrimes (read w))          -- no leak
 
sieveUA :: Int -> UArray Int Bool
sieveUA top = runSTUArray $ do
    let m = (top-1) `div` 2
        r = floor . sqrt . fromIntegral $ top + 1 
    sieve <- newArray (1,m) True                 -- :: ST s (STUArray s Int Bool)
    forM_ [1..r `div` 2] $ \i -> do
      isPrime <- readArray sieve i
      when isPrime $                             -- ((2*i+1)^2-1)`div`2 = 2*i*(i+1)
        forM_ [2*i*(i+1), 2*i*(i+2)+1..m] $ \j -> 
          writeArray sieve j False
    return sieve
 
primesTo :: Int -> [Int]
primesTo top = 2 : [i*2+1 | (i,True) <- assocs $ sieveUA top]
 
lastPrimes :: Int -> (Int,[Int])   -- (nth, vals)
lastPrimes top = 
  let arr   = sieveUA top
      (b,t) = bounds arr
  in 
     ( 1 + length [() | (i,True) <- assocs arr]
     , (if (top < 13) then (2:) else id) 
        $ reverse $ take 5 [ 2*i+1 | i <- [t,t-1..b], arr ! i ] )
 
{-
ST Array [Int] ON ODDS 
    -= n =-    -= top =- 
    30,000:     350,377:  0.01s  3.7MB
   100,000:   1,299,709:  0.03s  3.7MB
   300,000:   4,256,233:  0.10s  3.7MB
  1 mln -->  15,485,863:  0.43s  4.8MB        time   space (s_0=3.7)
  2 mln -->  32,452,843:  0.98s  5.8MB
  4 mln -->  67,867,967:  2.31s  8.9MB  1m-> n^1.21  n^1.12
  5 mln -->  86,028,121:  3.04s  9.9MB
  6 mln --> 104,395,301:  3.77s 10.9MB   (leak: was: ***6.7s-227MB***!!!)
6,500,000-> 113,648,393:  4.14s 10.9MB
  7 mln --> 122,949,823:  4.52s 11.9MB
7,538,613-> 133,000,999:  4.95s 11.9MB
  8 mln --> 141,650,939:  5.32s 13.0MB  4m-> n^1.20  n^0.84
  9 mln --> 160,481,183:  6.12s 14.0MB
 10 mln --> 179,424,673:  6.91s 15.0MB
 15 mln --> 275,604,541: 11.01s 21.1MB
 18 mln --> 334,214,459: 13.65s 24.2MB  8m-> n^1.16  n^0.97 (1m->n^1.01)
 20 mln --> 373,587,883:    TIMEOUT   
-}