{-# OPTIONS_GHC -O2 #-}
module Main where
import qualified Data.IntSet as I
 
-- sieve of Eratosthenes - all primes up to n 
primes n = go 3 (I.fromDistinctAscList (2:[3,5..n]))
  where
    go x is 
      | (x*x) > n        = is
      | I.notMember x is = go (x+2) is
      | otherwise        = go (x+2) (is I.\\
                  (I.fromDistinctAscList [x*x,x*x+x+x..n]))

main = do
  let topval = 4256233
  let ps = primes topval
  -- print ps
  putStrLn $ "There are " ++ show(I.size ps)
              ++ " primes upto " ++ show topval
              ++ ", and the topmost prime is "
              ++ show (I.findMax ps) ++ "."

{-                      INTSET/all   INTSET/Odds    SEGfilt   SEGTREE    ARR/Odds
    1,000:     7919   0.01s   4.6MB   0.00   3.6   0.00  3.7             0.00  3.7
   30,000:   350377   0.65s  29.2MB   0.29  15.9   0.09  4.7             0.02  4.8
  100,000:  1299709   2.90s 110.1MB   1.38  52.7   0.51  5.8  0.23  6.8  0.06  7.8
  300,000:  4256233    OUT_OF_MEM     5.32 190.0   2.49 12.9  0.83 12.9  0.27 17.1
1,000,000: 15485863                   OUT_OF_MEM  14.09 38.5  3.73 57.0  1.18 52.9
-}