{-# 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
-}

ey0jIE9QVElPTlNfR0hDIC1PMiAjLX0KbW9kdWxlIE1haW4gd2hlcmUKaW1wb3J0IHF1YWxpZmllZCBEYXRhLkludFNldCBhcyBJCiAKLS0gc2lldmUgb2YgRXJhdG9zdGhlbmVzIC0gYWxsIHByaW1lcyB1cCB0byBuIApwcmltZXMgbiA9IGdvIDMgKEkuZnJvbURpc3RpbmN0QXNjTGlzdCAoMjpbMyw1Li5uXSkpCiAgd2hlcmUKICAgIGdvIHggaXMgCiAgICAgIHwgKHgqeCkgPiBuICAgICAgICA9IGlzCiAgICAgIHwgSS5ub3RNZW1iZXIgeCBpcyA9IGdvICh4KzIpIGlzCiAgICAgIHwgb3RoZXJ3aXNlICAgICAgICA9IGdvICh4KzIpIChpcyBJLlxcCiAgICAgICAgICAgICAgICAgIChJLmZyb21EaXN0aW5jdEFzY0xpc3QgW3gqeCx4KngreCt4Li5uXSkpCgptYWluID0gZG8KICBsZXQgdG9wdmFsID0gNDI1NjIzMwogIGxldCBwcyA9IHByaW1lcyB0b3B2YWwKICAtLSBwcmludCBwcwogIHB1dFN0ckxuICQgIlRoZXJlIGFyZSAiICsrIHNob3coSS5zaXplIHBzKQogICAgICAgICAgICAgICsrICIgcHJpbWVzIHVwdG8gIiArKyBzaG93IHRvcHZhbAogICAgICAgICAgICAgICsrICIsIGFuZCB0aGUgdG9wbW9zdCBwcmltZSBpcyAiCiAgICAgICAgICAgICAgKysgc2hvdyAoSS5maW5kTWF4IHBzKSArKyAiLiIKCnstICAgICAgICAgICAgICAgICAgICAgIElOVFNFVC9hbGwgICBJTlRTRVQvT2RkcyAgICBTRUdmaWx0ICAgU0VHVFJFRSAgICBBUlIvT2RkcwogICAgMSwwMDA6ICAgICA3OTE5ICAgMC4wMXMgICA0LjZNQiAgIDAuMDAgICAzLjYgICAwLjAwICAzLjcgICAgICAgICAgICAgMC4wMCAgMy43CiAgIDMwLDAwMDogICAzNTAzNzcgICAwLjY1cyAgMjkuMk1CICAgMC4yOSAgMTUuOSAgIDAuMDkgIDQuNyAgICAgICAgICAgICAwLjAyICA0LjgKICAxMDAsMDAwOiAgMTI5OTcwOSAgIDIuOTBzIDExMC4xTUIgICAxLjM4ICA1Mi43ICAgMC41MSAgNS44ICAwLjIzICA2LjggIDAuMDYgIDcuOAogIDMwMCwwMDA6ICA0MjU2MjMzICAgIE9VVF9PRl9NRU0gICAgIDUuMzIgMTkwLjAgICAyLjQ5IDEyLjkgIDAuODMgMTIuOSAgMC4yNyAxNy4xCjEsMDAwLDAwMDogMTU0ODU4NjMgICAgICAgICAgICAgICAgICAgT1VUX09GX01FTSAgMTQuMDkgMzguNSAgMy43MyA1Ny4wICAxLjE4IDUyLjkKLX0=