fork(1) download
copy 
  1. {-# OPTIONS_GHC -O2 #-}
  2.  
  3. module Main where
  4.  
  5. import Data.Array.Unboxed
  6.  
  7. main = do
  8.   m <- getLine
  9.   print {- $ fork(last,length) -} $ primesToAO (read m)
  10.  
  11. -- the simplest Sieve of Eratosthenes formulation, using
  12. -- an array that is passed as an accumulating argument
  13. -- between steps of iterative computation, and as such
  14. -- (could be, but ain't) liable to the destructive update (but is fast, still, 
  15. -- on unboxed arrays, with explicit type signature)
  16.  
  17. primesToA :: Int -> [Int]
  18. primesToA m | m > 2 = sieve 3 (array (3,m)  [(i,odd i) | i<-[3..m]]     -- 16M:2.03s
  19.                                  -- (zip [3..m] $ cycle [True,False])     -- 16M:2.90s
  20.                                  :: UArray Int Bool)
  21.   where
  22.     sieve p a 
  23.       | p*p > m   = 2 : [i | (i,True) <- assocs a]
  24.       | a!p       = sieve (p+2) $ a//[(i,False) | i <- [p*p, p*p+2*p..m]]
  25.       | otherwise = sieve (p+2) a
  26.  
  27.  
  28. fork (f,g) x = (f x,g x)  -- f &&& g
  29.  
  30.  
  31. -- apply the simple optimization of working with odds only: --------
  32.  
  33. primesToAO :: Int -> (Int,Int)
  34. primesToAO m | m > 2 = sieve 3 (-- array (1,m1)  [(i,True) | i<-[1..m1]]    -- 16M 0.73s-7.8MB
  35.                                 accumArray const True (1,m1) []             -- 16M 0.68s-7.8MB
  36.                                   :: UArray Int Bool)
  37.   where
  38.     m1 = (m-1) `div` 2
  39.     r  = floor . sqrt $ fromIntegral m + 1
  40.     sieve p a 
  41.       | p > r     = let
  42.                       last = head [i | i<-[u,u-1..l], a!i]               -- plug
  43.                       len  = length [() | (i,True) <- assocs a]           --  the leak
  44.                       (l,u) = bounds a
  45.                     in   (last*2+1, len+1)                                -- '2' is prime too
  46.       | a!p1      = sieve (p+2) $ a//[(i,False) | i <- [q1, q1+p..m1]]
  47.       | otherwise = sieve (p+2) a
  48.                        where p1 = (p-1) `div` 2
  49.                              q1 = (p*p-1) `div` 2
  50.  
  51. {-
  52.  en.wikipedia.org/wiki/Prime_number_theorem#Approximations_for_the_nth_prime_number
  53.  
  54.  n(log n + log(log n) - 1) < p_n <  n(log n + log(log n))  , for n >= 6
  55.  
  56. aaprimes n = 
  57.   let x=fromIntegral n
  58.       a=primesToA $ ceiling $ x*(log x + log(log x))   -- good for n >= 4  (p >= 7)
  59.       (l,u)=bounds a
  60.       p=head [i | i<-[u,u-1..l], a!i]
  61.       len=length [() | (i,True) <- assocs a]
  62.       ..........
  63.  
  64.  
  65.          m     n      Data.Array           Data.Array.Unboxed                             Odds_Only
  66.                                                                       Theoretical
  67. 100k  (99991,9592)    0.13s-6.8MB           0.02s-4.8MB                  cpxty
  68. 200k  (199999,17984)  0.39s-9.9MB   n^1.75  0.03s-4.8MB            n*log n*log(log n)
  69. 400k  (399989,33860)  1.06s-26.3MB  n^1.58  0.04s-4.8MB                              
  70. 1M    (999983,78498)  3.99s-45.7MB  n^1.58  0.09s-5.8MB                            0.04s-4.8MB
  71. 2M    (1999993,148933) 11.46s-84.6  n^1.65  0.16s-7.8MB    n^0.90-1.72   n^1.122   0.07s-4.8MB
  72. 4M    (3999971,283146)                      0.34s-9.9MB    n^1.17-0.83   n^1.114   0.14s-5.8MB   n^1.08
  73. 8M    (7999993,539777)                      0.73s-18.1MB   n^1.18-1.49   n^1.108   0.31s-5.8MB   n^1.23
  74. 16M  (15999989,1031130)                     2.03s-27.3MB   n^1.58-0.81             0.68s-7.8MB   n^1.21
  75. 32M  (31999939,1973815)                     4.89s-84.6MB   n^1.35-1.95             2.13s-11.9MB  n^1.76-1.33
  76. 50M  (49999991,3001134)                     8.45s-115.3MB  n^1.31-0.78             3.81s-16.0MB  n^1.39-1.09
  77. 64M  (63999979,3785086)                                                            5.24s-20.1MB  n^1.37-1.34
  78. 100M (99999989,5761455)                                                            9.27s-28.3MB  n^1.36-1.02
  79. 104M (104395301,6000000)                                                           9.80s-39.6MB -}
Success #stdin #stdout 0.04s 4760KB
comments (?)
stdin
copy 
1000000
stdout
copy 
(999983,78498)
https://ideone.com/dE0iU
contiguous accumulating array sieve of E. 2012-10-02
language:
Haskell (ghc 8.4.4)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!