{-# LANGUAGE PartialTypeSignatures #-}
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE MultiWayIf #-}
module Main (main) where

import qualified Data.ByteString.Char8 as C8
import qualified Data.Char as C
import qualified Data.List as L
import qualified Data.Vector as V
import qualified Data.Vector.Generic.Mutable as MV
import qualified Data.Vector.Algorithms.Merge as V

main :: IO ()
main = do
  [n] <- readInts
  vec <- readIntsVec
  mvec <- V.thaw vec
  V.sort mvec
  V.unsafeFreeze mvec >>= output . solve

solve :: V.Vector Int -> Int
solve vec
  | V.null vec = 0
  | V.length vec == 1 = 1
  | otherwise = let (c1,vec1) = go False (V.head vec) (V.tail vec) in fromEnum c1 + solve vec1
  where
    go isSeq a v
      | V.null v = if isSeq then (0,V.empty) else (1,V.empty)
      | otherwise =
          let b = V.head v
              bs = V.tail v
          in if | a==1 && b==1 -> (0,V.empty)
                | a==1 -> (1,V.empty)
                | a == b -> (0,V.empty)
                | (b `mod` a) == 0 -> let (c,l) = go (a==b) a bs in (c,l)
                | otherwise -> let (c,l) = go isSeq a bs in (c,b `V.cons` l) -- ここが問題

-- solve :: [Int] -> Int
-- solve [] = 0
-- solve [_] = 1
-- solve (x:xs) = let (c1,l1) = go False x xs in fromEnum c1 + solve l1
--   where
--     go isSeq _ [] = if isSeq then (0,[]) else (1,[])
--     go isSeq a (b:bs)
--       | a==1 && b==1 = (0,[])
--       | a==1 = (1,[])
--       | (b `mod` a) == 0 = let (c,l) = go (a==b) a bs in (c,l)
--       | otherwise = let (c,l) = go isSeq a bs in (c,b:l)

output :: Int -> IO ()
output = print

-- utils
readInts :: IO [Int]
readInts = L.unfoldr (C8.readInt . C8.dropWhile C.isSpace) <$> C8.getLine

readIntsVec :: IO (V.Vector Int)
readIntsVec = V.unfoldr (C8.readInt . C8.dropWhile C.isSpace) <$> C8.getLine