{-# LANGUAGE PartialTypeSignatures #-}
{-# LANGUAGE BangPatterns #-}
-- {-# LANGUAGE Strict #-}
{-# 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 Data.Heap (Heap)
import qualified Data.Heap as Heap

main :: IO ()
main = do
  [n] <- readInts
  readInts >>= output . solve . Heap.fromList . Heap.sort

solve :: Heap Int -> Int
solve xs
  | Heap.null xs = 0
  | Heap.size xs == 1 = 1
  | otherwise =
      case Heap.uncons xs of
        Nothing -> 0
        Just (y,ys) ->
          let (c1,rest) = go False y ys in fromEnum c1 + solve rest
  where
    go isSeq a v
      | Heap.null v = if isSeq then (0,Heap.empty) else (1,Heap.empty)
      | otherwise =
          case Heap.uncons v of
            Nothing -> if isSeq then (0,Heap.empty) else (1,Heap.empty)
            Just (b,bs) -> 
              if | a==1 && b==1 -> (0,Heap.empty)
                 | a==1 -> (1,Heap.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, Heap.insert b l) -- ここが問題

-- solve _ [] = 0
-- solve _ [_] = 1
-- solve n (x:xs)
--   | otherwise = let (c1,l1) = go False x xs in fromEnum c1 + solve n 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
