fork download
copy 
  1. {-# OPTIONS_GHC -O2 #-}
  2. module Main where
  3.  
  4. main = interact (\s-> show (primes() !! (read s - 1)))
  5.  
  6. primes :: () -> [Int]
  7. primes () = 2: primes'   -- Segmented Generation w/ rem filtering
  8.  where
  9.    primes' = 3: sieve primes' 3 0
  10.    sieve (p:ps) x k =
  11.      let
  12.          q  = p*p
  13.          fs = take k primes'
  14.      in
  15.         [n | n<-[x+2,x+4..q-2], and [rem n f/=0 | f<-fs]]
  16.         ++ sieve ps q (k+1)
  17.  
  18. {-
  19. postponed filters:                O(n^)          delta  O(n^)
  20.      1,000:       7,919    0.00s          3.7MB   0.0
  21.     30,000:     350,377    0.16s          5.8MB   2.1
  22.    100,000:   1,299,709    0.92s  1.45    9.9MB   6.2   0.90
  23.    300,000:   4,256,233    4.60s  1.46   21.1MB  17.4   0.94
  24.    600,000:   8,960,453   13.27s  1.50   38.5MB  34.8   1.00
  25.  
  26. segmented generation/filtering:   O(n^)          delta  O(n^)
  27.      1,000:       7,919    0.00s          3.7MB   0.0   
  28.     30,000:     350,377    0.09s          4.7MB   1.0   
  29.    100,000:   1,299,709    0.51s  1.44    5.8MB   2.1   0.62
  30.    300,000:   4,256,233    2.49s  1.44   12.9MB   9.2   1.34  0.92
  31.    600,000:   8,960,453    6.77s  1.44   21.1MB  17.4   0.92  1.20  0.95
  32.  1,000,000:  15,485,863   14.09s  1.43   38.5MB  34.8   1.36  0.91  1.20  1.0
  33. -}
stdin
copy 
1000000
compilation info 
[1 of 1] Compiling Main             ( prog.hs, prog.o )
Linking prog ...
stdout
copy 
15485863
https://ideone.com/xsocD
language:
Haskell (ghc 8.4.4)
created:
13 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!