import Control.Monad
import Control.Monad.ST
import Data.List
import qualified Data.Vector.Unboxed as V
import qualified Data.Vector.Unboxed.Mutable as MV

main = do
  getLine
  ns <- sort . map read . words <$> getLine
  print $ solve ns

solve ns = length $ filter (cs V.!) ns'
  where
    ns' = map head . filter (null . tail) $ group ns
    cs = runST $ do
      v <- MV.replicate (10^6 + 1) True
      forM_ ns' $ \i ->
        forM_ (takeWhile (<=10^6) (iterate (+i) (i*2))) $ \j -> MV.write v j False
      V.freeze v