module Main where

main = do
  putStrLn "primes above 13,000,000,000:"
  let m = 13000000000
  print $ take 8 $ primesFrom m
  let r = (floor.sqrt.fromIntegral) m
      k = length $ fst $ span (<= r) primes'
      (p:q:_) = drop (k-1) primes'
  print (r,k,[p,p*p,q,q*q])

primesFrom m = sieve (length h) ps $ m`div`2*2+1
  where 
    (h,(_:ps)) = span (<= (floor.sqrt.fromIntegral) m) primes
        
primes   = 2: 3: sieve 0 primes' 5 
primes'  = tail primes
{-
sieve k (p:ps) x   -- only 5 billion (?)
         = [x | x<-[x,x+2..p*p-2], and [(x`rem`p)/=0 | p<-take k primes']]
           ++ sieve (k+1) ps (p*p+2)  
-}
sieve k (p:ps) x   -- only 14 billion (?)
         = let (h,t) = ([x,x+2..t-2],p*p)
               qs = take k primes'
               h' = filter (\x-> all ((/=0).(x`rem`)) qs) h
            in h' ++ sieve (k+1) ps (t+2)

primes above 13,000,000,000:
[13000000073,13000000087,13000000141,13000000157,13000000163,13000000217,13000000229,13000000261]
(114017,10790,[114013,12998964169,114031,13003068961])