{-# OPTIONS_GHC -O2 #-}

-- http://stackoverflow.com/questions/26075806/haskell-garbage-collector/

import Data.List (foldl')  -- '

erat_ :: (Integer, Bool) -> [(Integer,Integer)] -> [(Integer,Integer)]
erat_ (c,b) ((x,y):xs)
    | c < x = (x,y) : erat_ (c,b) xs
    | c == x = (x+y,y) : erat_ (c,True) xs
    | c > x = (x+y,y) : erat_ (c,b) xs
erat_ (c,b) []
    | b = []
    | otherwise = [(c,c)]
{-
erat :: [Integer] -> [(Integer,Integer)]
erat = foldl_ (\a c -> erat' (c,False) a) []

primes :: Integer -> [Integer]
primes n = map snd $ erat [2..n]
-}
-- main = print . last . primes . read =<< getLine

--   NO  FORCING
main = print . length . (\n->  
                   foldl_ (\a c -> erat_ (c,False) a) 
                     [] [2..n])
             . read =<< getLine

-- 10k: 0.46s-8.4MB   20k: 2.34s-8.4MB   30k: 7.13s-9.4MB
--               N^2.35             N^2.75

{-   WITH  FORCING
main = print . length . (\n->  
                   foldl_ (\a c -> (if null a then 0 else 
        case last a of (x,y) -> y) `seq` erat_ (c,False) a) 
                     [] [2..n])
             . read =<< getLine
-}
-- 10k: 0.27s-6.3MB  20k: 1.07s-7.4MB  40k: 3.99s-7.4MB  70k: 13.63-7.3MB
--               N^1.99            N^1.90            N^2.20

----- STOPPING EARLY -----

g :: (Integer, Bool) -> [(Integer,Integer)] -> [(Integer,Integer)]
g (c,b) ((x,y):xs)
    | c < x  = (x,  y) : if x==y*y then (if b then xs 
                                              else xs++[(c*c,c)])
                                   else g (c,b)    xs 
    | c == x = (x+y,y) : if x==y*y then            xs 
                                   else g (c,True) xs 
    | c > x  = (x+y,y) :                g (c,b)    xs 
g (c,True)  [] = []
g (c,False) [] = [(c*c,c)]

{-     WITH FORCING

main = print . length . (\n->  
                   foldl_ (\a c -> (if null a then 0 else 
        case last a of (x,y) -> y) `seq` g (c,False) a) 
                     [] [2..n])
             . read =<< getLine
-}
-- 20k: 0.30s-6.3MB  40k: 1.05s-6.3MB  80k: 3.99s-7.4MB  100k: 5.70s-7.4MB
--               N^1.80            N^1.93            N^1.60(1.85)

{-    NO FORCING

main = print . length . (\n->  
                   foldl_ (\a c -> g (c,False) a) 
                     [] [2..n])
             . read =<< getLine
-}
-- 20k: 0.20s-8.4MB  40k: 0.75s-9.4MB  80k: 2.55s-9.4MB  100k: 3.87s-9.4MB 
--               N^1.90            N^1.77            N^1.87(1.79)

foldl_ f z xs = foldl' f z xs  -- '