Given is a number sequence A of length N.
Find the number of integers i \left(1 \leq i \leq N\right) with the following property:
 - For every integer j \left(1 \leq j \leq N\right) such that i \neq j , A_j does not divide A_i.

-----Constraints-----
 - All values in input are integers.
 - 1 \leq N \leq 2 \times 10^5
 - 1 \leq A_i \leq 10^6

-----Input-----
Input is given from Standard Input in the following format:
N
A_1 A_2 \cdots A_N

-----Output-----
Print the answer.

-----Sample Input-----
5
24 11 8 3 16

-----Sample Output-----
3

The integers with the property are 2, 3, and 4.

Difficulty: interview

Starter code:

Solutions:
n = int(input())
a = list(map(int, input().split()))
MAX = 10 ** 6 + 5
cnt = [0] * MAX
ok = [True] * MAX
for x in a:
    cnt[x] += 1
ans = 0
for i in range(1, MAX):
    if cnt[i] > 0:
        for j in range(i * 2, MAX, i):
            ok[j] = False       
        if ok[i] and cnt[i] == 1:
            ans += 1
print(ans)

N = int(input())
*A,=map(int,input().split())
A = sorted(A)

if N == 1:
  print(1)
  return

flag = [0]*(10**6+5)
for i in range(N):
  flag[A[i]] = 1

for i in range(N):
  if flag[A[i]] == 0:
    continue
  if i>0 and A[i]==A[i-1]:
    flag[A[i]] = 0
    continue
  for num in range(A[i]*2,A[-1]+1,A[i]):
    flag[num] = 0
  
print(sum(flag))

#https://at274.hatenablog.com/entry/2020/06/29/181102
import collections
N=int(input())
A=list(map(int,input().split()))
c=collections.Counter(A)
A=set(A)
MAX_A=10**6
X=[0]*(MAX_A + 1)#0-MAX_Aまでの整数がAの倍数で何回割られるか
for i in A:
  for j in range(i,MAX_A + 1,i):
    X[j]+=1

#割られた回数が1つしかないものはその数自身で割ったのでカウント
#ただし複数ある場合は除外
ans = len([a for a in A if (X[a] == 1) and (c[a] == 1)])
print(ans)

import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
import numpy as np
def main():
    a = np.array(read().split(), np.int32)[1:]
    count = np.zeros(10**6+1, np.int32)
    for ae in a:
        if count[ae] <= 1:
            count[::ae] += 1
    r = 0
    for ae in a:
        r += count[ae] == 1
    print(r)

def __starting_point():
    main()
__starting_point()

N=int(input())
A=sorted(list(map(int,input().split())))
B=[0]*(A[-1]+1)

for i in A:
  j=i
  while j<=A[-1]:
    B[j]+=1
    j+=i
s=0
for i in A:
  if B[i]==1:
    s+=1
print(s)

N = int(input())
A = list(map(int, input().split()))
 
M = 10**6 + 1
 
cnt = [0] * M
 
for a in A:
    if cnt[a] != 0:
        cnt[a] += 1
        continue
    for b in range(a, M, a):
        cnt[b] += 1
 
ans = 0
for a in A:
    if cnt[a] == 1:ans += 1
 
print(ans)


import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
import numpy as np
from collections import Counter
def main():
    n, *a = list(map(int, read().split()))

    if 1 in a:
        count1 = a.count(1)
        if count1 == 1:
            print((1))
            return
        else:
            print((0))
            return
    a = np.array(a)
    maxa = a.max()
    seq = np.zeros(maxa + 1, np.int32)
    u, cnt = np.unique(a, return_counts=True)
    for ue, cnte in zip(u, cnt):
        if cnte == 1:
            seq[ue] = 1
    for ae in a:
        t = ae * 2
        while t <= maxa:
            seq[t] = 0
            t += ae
    r = seq.sum()
    print(r)

def __starting_point():
    main()

__starting_point()

n = int(input())
A = list(map(int,input().split()))
A.sort()
# print(A)
multiple = [0]*(A[-1]+1)
for i in range(n):
    now = A[i]
    while(now <= A[-1]):
        multiple[now] += 1
        now += A[i]
ans = 0
for i in range(n):
    if(multiple[A[i]] == 1):
        ans += 1
# print(multiple)
print(ans)

import collections
# Your code her
a = int(input())
b = [int(s) for s in input().split()]
b = sorted(b)
mod = int(1000000)
d = {}
e = collections.Counter(b)
X = int(0)
ans = int(0)

for i in range(a):
    if d.get(b[i]) == None:
        if e.get(b[i]) != 1:
            d[b[i]] = 1
        X = b[i]
        while X <= (mod-b[i]):
            X += b[i]
            d[X] = 1
        X = 0
    else:
        pass

for i in range(a):
    if d.get(b[i]) == None:
        ans += 1

print(ans)

import math
ini = lambda : int(input())
inm = lambda : map(int,input().split())
inl = lambda : list(map(int,input().split()))
gcd = lambda x,y : gcd(y,x%y) if x%y else y
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
mod = 10**9 + 7

#maincode-------------------------------------------------

n = ini()
a = inl()
A = 10**6 + 5
b = [0] * A
ans = 0

for i in a:
    if b[i] != 0:
        b[i] = 2
        continue
    for i in range(i,A,i):
        b[i] += 1

for i in a:
    if b[i] == 1:
        ans += 1

print(ans)

N = int(input())
A = [int(x) for x in input().split()]
M = max(A)

count = [0] * (M + 1)
for i in range(N):
    count[A[i]] += 1

check = [True] * (M + 1)
for a in range(1, M + 1):
    if count[a] > 0 and check[a] == True:
        for k in range(2, M // a + 1):
            check[a * k] = False      

ans = 0
for i in range(N):
    if count[A[i]] == 1 and check[A[i]] == True:
        ans += 1

print(ans)

#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N=I()
    A=sorted(LI())

    MAX=10**6
    divible=[False]*(MAX+1)

    ans = 0
    for i,a in enumerate(A):
        if(i+1<N and A[i+1]==a or divible[a]):
            pass
        else:
            ans += 1
            
        b = a
        if(not divible[a]):#エラトステネスの篩と同じ計算量解析.
            while(b<=MAX): 
                divible[b] = True
                b += a
    print(ans)
        
def __starting_point():
    main()
__starting_point()

N = int(input())
A = sorted(list(map(int,input().split())))
B = (10**6+1)*[0]

for a in A:
  B[a]+=1
  if B[a]==1:
    for n in range(2*a,10**6+1,a):
      B[n]+=2

print(B.count(1))

n = int(input())
a = list(map(int, input().split()))
MAX = 10 ** 6 + 5
cnt = [0] * MAX
ok = [True] * MAX
for x in a:
    cnt[x] += 1
ans = 0
for i in range(1, MAX):
    if cnt[i] > 0:
        for j in range(i * 2, MAX, i):
            if cnt[j] > 0:
                ok[j] = False       
        if ok[i] and cnt[i] == 1:
            ans += 1
print(ans)

N = int(input())
A = list(map(int, input().split()))
A.sort()
MAX = 10**6+1
cnt = [0]*MAX

for x in A:
  if cnt[x] != 0:
  	cnt[x] = 2
  else:
    for i in range(x, MAX, x):
      cnt[i] += 1
  
ans = 0
for x in A:
  # 2回以上通った数字 (cnt[x]>1) は，その数字より小さい約数が存在する (割り切れる他の数が存在する)。
  if cnt[x] == 1:  
    ans += 1
    
print(ans)

n=int(input())
a=sorted(map(int,input().split()))
s=[0]*(m:=a[-1]+1)
for x in a:s[x]+=1
for x in a:
  for j in range(x*2,m,x):s[j]=0
print(s.count(1))

#!/usr/bin/env python3
import sys
def input(): return sys.stdin.readline().rstrip()


def main():
    n=int(input())
    A=list(map(int, input().split()))
    counts=[0]*(10**6+5)
    for AA in A:
        counts[AA]+=1
    ans=0
    for i in range(1,10**6+5):
        if counts[i]>0:
            for j in range(i+i,10**6+5,i):
                counts[j]=-1
        if counts[i]==1:
            ans+=1
    print(ans)
        

        
    


def __starting_point():
    main()


__starting_point()

from collections import Counter 
n = int(input())
a = list(map(int, input().split()))
s = set(a)
c = Counter(a)
t = [0] * (10**6 + 1)
for i in s:
    for j in range(i, 10**6+1, i):
        t[j] += 1

ans = len([1 for i in s if t[i] == 1 and c[i] == 1])
print(ans)



import numpy as np
n = int(input())
li_a = list(map(int, input().split()))
m = max(li_a)
e = np.zeros(m)
dup = []
for a in li_a:
    if(e[a-1]==1):
        dup.append(a-1)
        continue
    e[a-1] = 1

for i in dup:
    e[i] = 0

for a in set(li_a):
    origin = a
    while a <= m:
        if a==origin:
            a += origin
            continue
        e[a-1]=0
        a += origin
print(int(sum(e)))

#D - Not Divisible
import collections
N = int(input())
a = list(map(int,input().split()))
a = sorted(a,reverse = False)

#collections.Counterは存在しない値を指定すると0を返す
cnt = collections.Counter(a)
m = max(a)+1
for i in a:
    if cnt[i] >= 2:
        del cnt[i]
    for j in range(i*2,m,i):
        del cnt[j]
print(len(cnt.keys()))

N = int(input())
A = [int(_) for _ in input().split()]

A.sort()
M = max(A)
X = [True for _ in range(M + 1)]

for a in set(A):
    if not X[a]:
        continue
    for v in range(2 * a, M + 1, a):
        X[v] = False

for i in range(N-1):
    if A[i] == A[i+1]:
        X[A[i]] = False

ans = 0
for a in A:
    if X[a]:
        ans += 1
print(ans)


# import itertools
import math
from functools import reduce
# import sys
# sys.setrecursionlimit(500*500)
# import numpy as np
# import heapq
# from collections import deque

N = int(input())
# S = input()
# n, *a = map(int, open(0))
# N, M = map(int, input().split())
A = list(map(int, input().split()))
# B = list(map(int, input().split()))
# tree = [[] for _ in range(N + 1)]
# B_C = [list(map(int,input().split())) for _ in range(M)]
# S = input()

# B_C = sorted(B_C, reverse=True, key=lambda x:x[1])
# all_cases = list(itertools.permutations(P))
# a = list(itertools.combinations_with_replacement(range(1, M + 1), N))
# itertools.product((0,1), repeat=n)

# A = np.array(A)
# cum_A = np.cumsum(A)
# cum_A = np.insert(cum_A, 0, 0)

# def dfs(tree, s):
#     for l in tree[s]:
#         if depth[l[0]] == -1:
#             depth[l[0]] = depth[s] + l[1]
#             dfs(tree, l[0])
# dfs(tree, 1)

# def factorization(n):
#     arr = []
#     temp = n
#     for i in range(2, int(-(-n**0.5//1))+1):
#         if temp%i==0:
#             cnt=0
#             while temp%i==0:
#                 cnt+=1
#                 temp //= i
#             arr.append([i, cnt])
#     if temp!=1:
#         arr.append([temp, 1])
#     if arr==[]:
#         arr.append([n, 1])
#     return arr

# def gcd_list(numbers):
#     return reduce(math.gcd, numbers)

# if gcd_list(A) > 1:
#     print("not coprime")
#     return

# 高速素因数分解準備
#MAXN = 10**6+10
#sieve = [i for i in range(MAXN+1)]
#p = 2
#while p*p <= MAXN:
#    if sieve[p] == p:
#        for q in range(2*p, MAXN+1, p):
#            if sieve[q] == q:
#                sieve[q] = p
#    p += 1

A.sort()
MAXN = A[-1]
sieve = [1] * (MAXN + 1)
st = set()
for a in A:
    if a in st:
        sieve[a] = 0
    if sieve[a] == 1:
        for q in range(2*a, MAXN+1, a):
            if sieve[q] == 1:
                sieve[q] = 0
    st.add(a)

ans = 0
for a in A:
    ans += sieve[a]
print(ans)

import collections

n=int(input())
arr=list(map(int,input().split()))
arr=sorted(arr) #小さい順にソートしておく
s=set()
cnt=collections.Counter(arr) #各要素の個数を事前に数えておく
for i in range(n):
 if arr[i] in s: #Aiがすでに列挙した数に含まれていれば処理を行わない
   continue
 if cnt[arr[i]]>=2: #Aiが2個以上含まれているとき、Ai自身を列挙した数に加える
   s.add(arr[i])
 for j in range(2,10**6//arr[i]+1): #Ai自身を除くAiの倍数を列挙する
   s.add(arr[i]*j)
ans=0
for i in range(n): #列挙した数に含まれないAiの個数を数える
 if arr[i] in s:
   continue
 ans+=1
print(ans)

n = int(input())
a = list(map(int,input().split()))
a.sort()

dp = [0]*a[-1]
for x in a:
	if dp[x-1] == 0:
		y = 2*x
		while y <= a[-1]:
			dp[y-1] = 1
			y += x

sum = 0
d = [0]*a[-1]
for i in a:
	if dp[i-1] == 0:
		d[i-1] += 1
for i in a:
	if d[i-1] == 1:
		sum += 1
print(sum)

# coding: utf-8
n = int(input())
A = list(map(int,input().split()))
a_ = max(A)
A_ = list(set(A))
dp = [True] * (a_+1)
C = [0] * (a_+1)
for a in A:
    C[a]+=1
A_.sort()
ans = 0

for a in A_:
    tmp = a
    if dp[tmp]:
        tmp += a
        while tmp <= a_:
            dp[tmp] = False
            tmp += a
#print(dp)
for a in A_:
    if dp[a]:
        if C[a]==1:
            ans += 1
print(ans)

n = int(input())
a = sorted(list(map(int, input().split())))
ans = 0
dp = [0]*(a[-1]+1)
 
for i in a:
    for j in range(i, a[-1]+1, i):
        dp[j] += 1
 
for i in a:
    if dp[i]==1:
        ans += 1
print(ans)

N = int(input())
a = list(map(int, input().split()))

cnt = {}

for item in a:
    if item not in cnt:
        cnt[item] = 0
    cnt[item] += 1

A = list(set(a))

candidate = []

for item in A:
    if cnt[item] == 1:
        candidate.append(item)

judge = [True] *(10**6 + 1)

for item in A:
    for i in range(2, ((10**6)//item) + 1):
        judge[item*i] = False

ans = 0

for item in candidate:
    if judge[item]:
        ans += 1

print(ans)

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy,bisect
#from operator import itemgetter
#from heapq import heappush, heappop
#import numpy as np
#import sympy
#from scipy.sparse.csgraph import breadth_first_order, depth_first_order, shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
#from scipy.sparse import csr_matrix
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
import sys

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
nf = lambda: float(ns())
na = lambda: list(map(int, stdin.readline().split()))
nb = lambda: list(map(float, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces


def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

N = ni()
A = na()
d = collections.Counter(A)
dp = [0] * (10 ** 6 + 10)
A.sort()
pre = -1
ans = 0
for ai in A:
    if pre == ai:
        continue
    pre = ai
    if dp[ai] == 0 and d[ai] == 1:
        ans += 1
    for j in range(ai, 10 ** 6 + 1, ai):
        dp[j] = 1
print(ans)


#!/usr/bin/env python3
import sys
import collections

input = sys.stdin.readline


def ST():
    return input().rstrip()


def I():
    return int(input())


def MI():
    return list(map(int, input().split()))


def LI():
    return list(MI())


N = I()
A = LI()
A.sort()
cnt = collections.Counter(A)
MAX = A[-1] + 1
# end = A[-1] ** 0.5

for a in A:
    if cnt[a] >= 2:
        del cnt[a]
    for i in range(a * 2, MAX, a):
        del cnt[i]

print((sum(cnt.values())))


N = int(input())
A = list(map(int, input().split()))
A.sort()
minNum = A[0]
maxNum = A[N - 1]
countList = [0]*(10**6 + 1)
answer = 0

# Aにnがm個あるときcountList[n] = m
for i in A:
  countList[i] += 1

for j in range(minNum, maxNum + 1):
  # Aにjが含まれていれば、jの倍数をすべてcountListから除外
  # jの倍数pはjで割り切れるので除外可能
  # pの倍数qはjでも割り切れるのでjの時の処理によって除外される
  if countList[j] > 0:
    for k in range(2 * j, 10**6 + 1, j):
      countList[k] = 0
  # jが2個以上ある場合にはそれを正解としてカウントしない
  if countList[j] == 1:
      answer += 1

print(answer)

N=int(input())
A=list(map(int,input().split()))

A.sort()

dp=[False]*(10**6*2)
ans=0
for idx,i in enumerate(A):
  if dp[i]:continue
  tmp=i
  ans+=1
  while tmp<10**6*2-1:
    dp[tmp]=True
    tmp+=i
  if idx!=len(A)-1 and A[idx+1]==i:
    ans-=1
print(ans)

def resolve():
    n=int(input())
    a=list(map(int,input().split()))
    a.sort()
    M=int(1e6+1)
    f=[0]*M
    for x in a:
        if f[x]!=0:
            f[x]+=1
            continue
        for nx in range(x,M,x):
            f[nx]+=1
    ans=0
    for x in a:
        if f[x]==1:ans+=1
    print(ans)
resolve()


n = int(input())
a = list(map(int, input().split()))
dp = [0] * (max(a) + 1)
a.sort()

for i in a:
  temp = i
  while temp <= a[-1]:
    dp[temp] += 1
    temp += i
ans = 0
for i in a:
  if dp[i] == 1:
    ans += 1
             
print(ans)

n=int(input())
a=sorted(list(map(int,input().split())))
dp=[0]*(m:=a[-1]+1)
for i in a:
  for j in range(i,m,i):
    dp[j]+=1
ans=0
for i in a:
  if dp[i]==1:
    ans+=1
print(ans)

from collections import Counter

n = int(input())
a = list(map(int, input().split()))

c = Counter(a)
k = sorted(list(c.keys()))

kl =k[-1]
b = [1] * kl
cnt = 0
for i in k:
    if c[i] == 1 and b[i-1] == 1:
        cnt += 1
    for j in range(1, kl+1):
        if i*j > kl:
            break
        else:
            b[i*j-1] = 0
print(cnt)

n=int(input())
a=list(map(int,input().split()))
a.sort()
am=max(a)
dp=[[True,0] for _ in range(am+1)]
count=0
for i in a:
    if dp[i][0]==False:
        continue
    else:
        if dp[i][1]==1:
            dp[i][0]=False
            count-=1
        else:
            dp[i][1]=1
            count+=1
            for j in range(2*i,am+1,i):
                dp[j][0]=False
print(count)

n = int(input())
a = list(map(int,input().split()))
a.sort()
ma = a[-1]

dp = [0]*(ma+1)

for i in range(1,n):
    if a[i]==a[i-1]:
        dp[a[i]]=1

for i in a:
    for j in range(i*2,ma+1,i):
        #if dp[j]==1:
            #break
        dp[j]=1
        
ans = 0
for i in a:
    if dp[i]==0:
        ans+=1
        
print(ans)

#!/usr/bin/env python3
import sys
import collections

input = sys.stdin.readline


def ST():
    return input().rstrip()


def I():
    return int(input())


def MI():
    return list(map(int, input().split()))


def LI():
    return list(MI())


N = I()
A = LI()
A.sort()
cnt = collections.Counter(A)
end = A[-1] + 1

for a in A:
    if cnt[a] >= 2:
        del cnt[a]
    for i in range(a * 2, end, a):
        del cnt[i]

print((sum(cnt.values())))


from collections import Counter
N = int(input())
A = list(map(int,input().split()))
C = Counter(A)
A = set(A)
B = [True] * (10 ** 6 + 1)
for a in A:
    for i in range(2 * a,10**6 + 1 ,a):
        B[i] = False
cnt = 0
for a in A:
    if (B[a] == True) and (C[a] == 1):
        cnt += 1
print(cnt)

N = int(input())
A = list(map(int, input().split()))

M = 10**6 + 1

cnt = [0] * M

for a in A:
    if cnt[a] != 0:
        cnt[a] += 1
        continue
    for b in range(a, M, a):
        cnt[b] += 1

ans = 0
for a in A:
    if cnt[a] == 1:ans += 1

print(ans)


import numpy as np
from collections import Counter

n = int(input())
A = list(map(int,input().split()))

cnt = Counter(A)

b = np.array([0]*(max(A)+1))

A.sort()
ans = 0
for a in A:
    if cnt[a] == 1 and not b[a]:
        ans += 1
    b[a::a] = 1

print(ans)

import numpy as np
import random

rand = False
if rand:
    N = 10 ** 5
    A = random.choices(list(range(1, 10**6)), k=N)
else:
    N = int(input())
    A = list(map(int, input().split()))

A.sort()
MX = max(A)
ret = np.zeros(MX+1, dtype=np.bool)
A = np.array(A, dtype=np.int32)
ret[ A ] = True

for i in range(N-1):
    m = A[i] * 2
    if A[i] == A[i+1]: m = A[i]
    ret[ np.arange(m, MX+1, A[i]) ] = False

print((np.sum(ret)))

    




N = int(input())
A = list(map(int, input().split()))
A.sort()
INF = 10**6+1
lis = [1]*INF
exist = [0]*INF
for i in range(N):
    a = A[i]
    if lis[a] and exist[a] < 1:
        q = 2
        while a*q < INF:
            lis[a*q] = 0
            q += 1
    exist[a] += 1
cnt = 0
for a in A:
    if lis[a] and exist[a] == 1:
        cnt += 1
print(cnt)

N = int(input())
A = list(map(int, input().split()))
A.sort()
minNum = A[0]
maxNum = A[N - 1]
countList = [0]*(10**6 + 1)
answer = 0

# Aにnがm個あるときcountList[n] = m
for i in A:
  countList[i] += 1

for j in range(minNum, maxNum + 1):
  # Aにjが含まれていれば、jの倍数をすべてcountListから除外
  # jの倍数pはjで割り切れるので除外可能
  # pの倍数qはjでも割り切れるのでjの時の処理によって除外される
  if countList[j] > 0:
    for k in range(2 * j, maxNum + 1, j):
      countList[k] = 0
  # jが2個以上ある場合にはそれを正解としてカウントしない
  if countList[j] == 1:
      answer += 1

print(answer)

#!/usr/bin/env python

n = int(input())
a = list(map(int, input().split()))

a = sorted(a)
ma = a[-1]
div = [0 for _ in range(ma+1)]

for i in range(n):
    for j in range(a[i], ma+1, a[i]):
        div[j] += 1

ans = 0 
for i in range(n):
    if div[a[i]] == 1:
        ans += 1
print(ans)

n = int(input())
a = list(map(int, input().split()))
MAX = 10 ** 6 + 5
cnt = [0] * MAX
ok = [True] * MAX

for x in a:
    cnt[x] += 1

ans = 0

for i in range(1,MAX):
    if cnt[i] > 0:
        for j in range(i*2, MAX, i):
            ok[j] = False
        if ok[i] and cnt[i] == 1:
            ans += 1
print(ans)

#!/usr/bin/env python3
import sys
from itertools import chain
import numpy as np

# from itertools import combinations as comb
# form bisect import bisect_left, bisect_right, insort_left, insort_right
# from collections import Counter


def solve(N: int, A: "List[int]"):
    check = np.zeros(max(A) + 1, dtype=np.uint8)
    for ai in A:
        if check[ai] == 0:
            check[ai::ai] += 1
        else:
            check[ai] = 2

    answer = 0
    for ai in A:
        if check[ai] == 1:
            answer += 1

    return answer


def main():
    tokens = chain(*(line.split() for line in sys.stdin))
    # N, A = map(int, line.split())
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    answer = solve(N, A)
    print(answer)


def __starting_point():
    main()

__starting_point()

n = int(input())
a = list(map(int, input().split()))

a.sort()
d = {}
for x in a:
    d[x] = d.get(x, 0) + 1

ans = 0
ok = [1] * (10 ** 6 + 1)
for x in list(d.keys()):
    if ok[x]:
        for j in range(2, (10 ** 6) // x + 1):
            ok[j * x] = 0
        if d[x] == 1:
            ans += 1

print(ans)


n = int(input())
nums = list(map(int,input().split()))
nums.sort()
ans = 0
cnt = {}
flag = [0]*1000005
for i in nums:
  cnt[i] = cnt.get(i,0) + 1

for i in nums:
  if flag[i] == 0 and cnt[i] == 1:
    ans += 1
  if flag[i] == 1:
    continue
  for j in range(i,1000001,i):
    flag[j] = 1

print(ans)

import sys
import math
def input(): return sys.stdin.readline().rstrip()
from decimal import Decimal

M = 10 ** 6 + 5
N = int(input())
A = list(map(int, input().split()))

count = [0] * M
for a in A:
    if count[a] != 0:
        count[a] = 2
        continue
    for i in range(1, M):
        if i * a >= M:
            break
        count[a*i] += 1

ans = 0
for a in A:
    if count[a] == 1:
        ans += 1
    
print(ans)

from collections import Counter as c
n = int(input())
a = list(map(int,input().split()))
a.sort()

count, a_max = 0, a[-1]
li = [True] * (a_max+1)

for i in a:
  if li[i] == "x":
    count -= 1
    li[i] = "y"

  if li[i] == True:
    count += 1
    li[i] = "x"

  j = 2
  while i * j <= a_max:
    li[i*j] = False
    j += 1

print(count)

import sys

n = int(input())
arr= list(map(int,sys.stdin.readline().split()))
arr = sorted(arr)
max_num = max(arr)
dp = [0 for i in range(max_num+1)]
for i in arr:
    j = i
    while j<=max_num:
        dp[j]+=1
        j+=i
ans = 0
for i in arr:
    if dp[i] == 1:
        ans+=1
print(ans)

import collections
n = int(input())
line = list(map(int, input().split( )))
arr = sorted(line)
coll = collections.Counter(arr)
#最大値
Ma = arr[-1]
#ソートしたn番目のやつの判定はn+1以降でおっけい. 
#同じ数字がある敵は無視
s = set()
for i in range(n):
  if coll[arr[i]] >= 2:
    s.add(arr[i])
  for j in range(2, Ma//arr[i]+1):
    s.add(arr[i]*j)
cnt = 0

#print(s)
for a in arr:
  if a in s: continue
  cnt += 1
print(cnt)

n=int(input())
an=[int(i) for i in input().split()]
an.sort()
maxA=an[-1]

ans_table=[0]*(maxA+1)


for ai in an:
    for k in range(1,int(maxA/ai)+1):
        ans_table[ai*k]+=1
ans=0
for ai in an:
    if ans_table[ai]==1:
        ans+=1

print(ans)

N = int(input())
A = list(map(int, input().split()))
countList = [0]*(10**6 + 1)
answer = 0

# Aにnがm個あるときcountList[n] = m
for i in A:
  countList[i] += 1

for j in range(10**6 + 1):
  # Aにjが含まれていれば、jの倍数をすべてcountListから除外
  # jの倍数pはjで割り切れるので除外可能
  # pの倍数qはjでも割り切れるのでjの時の処理によって除外される
  if countList[j] > 0:
    for k in range(2 * j, 10**6 + 1, j):
      countList[k] = 0
  # jが2個以上ある場合にはそれを正解としてカウントしない
  if countList[j] == 1:
      answer += 1

print(answer)

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
C = Counter(A)

A = set(A)
MAX_A = 10 ** 6
X = [0] * (MAX_A + 1)
for a in A:
    for i in range(a, MAX_A + 1, a):
        X[i] += 1

ans = len([a for a in A if (X[a] == 1) and (C[a] == 1)])
print(ans)

from collections import Counter
n = int(input())
A = sorted(map(int, input().split()))
m = A[-1]
C = Counter(A)
flags = [True for _ in range(m + 1)]
for a in A:
    if flags[a]:
        i = 2
        x = a * i
        while x <= m:
            flags[x] = False
            i += 1
            x = a * i
ans = 0
for a in set(A):
    if C[a] == 1 and flags[a]:
        ans += 1
print(ans)


N=int(input())
A=list(map(int,input().split()))
A.sort()
Amax=A[-1]
dp=[True]*(Amax+1)
ans=0
for i in range(N-1):
    p=A[i]
    if dp[p]:
        for j in range(1,Amax//p+1):
            dp[p*j]=False
        if p!=A[i+1]:
            ans+=1
if dp[Amax]:
    ans+=1
print(ans)

        




    









        

    









    

        




    















    



    





    






        






    
















        


























            
    


    


    
    














    


    














def main():
  n=int(input())
  a=sorted([int(x) for x in input().split()])
  cnt=[0]*(10**6+5)
  ans=0
  for ai in a:
    j,x=2,ai
    while x<=10**6:
      if j==2 and cnt[x]>=1: cnt[x]+=1; break;
      cnt[x]+=1
      x=ai*j; j+=1;
 
  for ai in a:
    if cnt[ai]<=1: ans+=1;
      
  print(ans)
      
def __starting_point():
  main()
__starting_point()

n = int(input())
a = sorted(map(int, input().split()))
l = [0]*(10**6+1)
M = max(a)

for i in a:
  if l[i] == 0:
    l[i] = 1
    for j in range(i*2, M+1, i):
      l[j] = -1
  else:
    l[i] = -1
print(l.count(1))

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
a.sort()
dp = [0] * a[-1]
c = Counter(a)
for i in a:
    for j in range(i, a[-1]+1, i):
        dp[j-1] += 1
ans = 0
for i in a:
    if dp[i-1] == 1 and c[i]:
        ans += 1
print(ans)

import collections
n = int(input())
a = sorted([int(i) for i in input().split()])
cnt = collections.Counter(a)
max_i = a[-1] + 1
for i in a:
  if cnt[i] >= 2:
    del cnt[i]
  for j in range(i*2, max_i, i):
    del cnt[j]
print(len(cnt))

n = int(input())
a = list(map(int,input().split()))

cnt = [0] * 1000005
for x in a:
    if cnt[x] != 0: 
        cnt[x] = 2
    else: 
        for i in range(x,1000005,x):
            cnt[i] += 1

ans = 0
for x in a:
    if cnt[x] == 1:
        ans += 1

print(ans)


N = int(input())
A = list(map(int, input().split()))


def solve2(N, A):
    A.sort()
    amax = A[-1]
    dp = [True] * (amax + 1)
    cnt = [0] * (amax + 1)

    for a in A:
        cnt[a] += 1

    for i in range(amax):
        x = i + 1
        if cnt[x] > 1:
            dp[x] = False

        if cnt[x] > 0:
            y = x * 2
            while y <= amax:
                dp[y] = False
                y += x

    ansval = [x for x in A if dp[x]]

    # print(ansval)
    ans = len(ansval)

    return ans


def solve1(N, A):
    ans = 0
    for i in range(N):
        is_ans = True
        for j in range(N):
            if i != j:
                if A[i] % A[j] == 0:
                    is_ans = False
                    break

        if is_ans:
            ans += 1

    return ans


print((solve2(N, A)))


from collections import Counter
N = int(input())
A = list(map(int, input().split()))
C = Counter(A)

A = set(A)
MAX_A = 10 ** 6
X = [0] * (MAX_A + 1)
for a in A:
    for i in range(a, MAX_A + 1, a):
        X[i] += 1

ans = len([a for a in A if (X[a] == 1) and (C[a] == 1)])
print(ans)

N = int(input())
A = list(map(int, input().split()))
M = 10**6 + 1
cnt = [0] * M
for a in A:
    if cnt[a] != 0:
        cnt[a] += 1
        continue
    for b in range(a, M, a):
        cnt[b] += 1
ans = 0
for a in A:
    if cnt[a] == 1:ans += 1
print(ans)


def abc170d_not_divisible():
    n = int(input())
    cnt = 0
    a = sorted(list(map(int, input().split())))
    flgs = [True] * (a[-1]+1)
    if n == 1:
        print(1)
        return
    for i in range(n):
        if i != n - 1 and a[i] == a[i + 1]:
            flgs[a[i]] = False
            continue
        for j in range(a[i] * 2, a[-1] + 1, a[i]):
            flgs[j] = False
        if flgs[a[i]]:
            cnt += 1
    print(cnt)


abc170d_not_divisible()

import math
n=int(input())
a=list(map(int,input().split()))
a.sort()
maxa=max(a)
arr=[0]*(maxa+1)
for i in a:
  if arr[i]==0:
    t=math.ceil((maxa+1)/i)
    for j in range(t):
      arr[i*j]+=1
  elif arr[i]==1:
    arr[i]=2
ans=0
for i in a:
  if arr[i]==1:
    ans+=1
print(ans)

N = int(input())
A = sorted(list(map(int,input().split())))
lim = max(A)
B = [0] * (lim+1)
for i in range(N):
    B[A[i]] += 1
ans = N
for i in range(1,lim+1):
    if B[i] == 0:
        continue
    if B[i] >= 2:
        ans -= B[i]
        B[i] = 0
    for j in range(i*2,lim+1,i):
        ans -= B[j]
        B[j] = 0

print(ans)


n=int(input())
a=list(map(int,input().split()))

a.sort()

x=a[-1]

dp=[0 for _ in range(x+1)]

for b in a:
  y=b
  while y<=x:
    dp[y]+=1
    y+=b

    
ans=0
for c in a:
  if dp[c]==1:
    ans+=1
    
print(ans)


n=int(input())
a=list(map(int,input().split()))
a=sorted(a)
b=list(set(a))
m=len(b)

p=[0]*(10**6+1)
for i in b:
    if p[i]==0:
        j=2
        while i*j<=10**6:
            p[i*j]=1
            j+=1
a.append(-1)
a.insert(0,-1)
ans=0
for i in range(1,n+1):
    if a[i]!=a[i+1] and a[i]!=a[i-1] and p[a[i]]==0:
        ans+=1
print(ans)


import collections
n = int(input())
A = list(map(int, input().split()))
A.sort()
cnt = collections.Counter(A)
#print(cnt)
for a in A:
    if cnt[a] >= 2:
        del cnt[a]
    for j in range(2*a, A[-1]+1, a):
        del cnt[j]
#print(cnt)
print((len(cnt)))


n = int(input())
a = sorted(list(map(int, input().split())))
ans = 0
dp = [0]*(a[-1]+1)

for i in a:
    for j in range(i, a[-1]+1, i):
        dp[j] += 1

for i in a:
    if dp[i]==1:
        ans += 1
print(ans)


import collections as c
n,a1=int(input()),[*map(int,input().split())]
a2,a3,b=set(a1),c.Counter(a1),[0]*(10**6+1)
for i in a2:
  for j in range(i,10**6+1,i):
    b[j]+=1
print(sum(b[i]==1 and a3[i]==1 for i in a2))

import bisect
N=int(input())
A=[int(x) for x in input().split()]
A=sorted(A)
maxA=max(A)
ans=0
so_list=[1]*(maxA+1)
index=0
i=0

while(i<N):
    flag=0
    now=A[i]
    if so_list[now]==1:
        index=0
        flag=1
        while(index+now<=maxA):
            so_list[index+now]=0
            index+=now
    right=bisect.bisect_right(A,now)#同じ数字はいくつある？
    if right-i==1:
        if flag==1:
            ans+=1
            #print(now)
        i=right
    else:
        i+=1

print(ans)

def main():
	N = int(input())
	A = [int(a) for a in input().split(" ")]
	A.sort()
	l = A[-1]
	p = [1] * l
	for i in range(len(A)):
		a = A[i]
		if p[a-1] == 1:
			p[a-1] = 2
			for j in range(2 * a - 1, l, a):
				p[j] = 0
		elif p[a-1] == 2:
			p[a-1] = 0
	print(len([x for x in A if p[x - 1] in [1, 2]]))

main()

def main():

    N = int(input())
    A = list(map(int, input().split()))

    A = sorted(A)
    Amax = A[-1]
    count = [0 for _ in range(Amax+1)]

    for a in A:
        for i in range(1, Amax//a+1):
            count[i*a] += 1

    ans = 0
    for i in range(N):
        a = A[i]
        if count[a] == 1:
#            print(i)                                                                                                                                            
            ans += 1

    print(ans)

def __starting_point():
    main()

__starting_point()

N = int(input())
A = list(map(int,input().split()))
A.sort()
M = 10**6+5
cnt = [0]*M
for x in A:
    if cnt[x] != 0:
        cnt[x] = 2
        continue
    for i in range(x,M,x):
        cnt[i] += 1
ans = 0
for i in A:
    if cnt[i] == 1:
        ans += 1
print(ans)

import math
from math import gcd,pi,sqrt
INF = float("inf")
MOD = 10**9 + 7

import sys
sys.setrecursionlimit(10**6)
import itertools
import bisect
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
  N = i_input()
  A = i_list()

  P = [True]*(10**6+1)
  C = Counter(A)

  s = list(set(A))

  for x in s:
    t = x*2
    while t<= 10**6:
      P[t] = False
      t += x
  ans = 0
  for x in A:
    if C[x] == 1 and P[x] == True:
      ans += 1
  print(ans)

 
 
def __starting_point():
    main()
__starting_point()

N = int(input())
MAX = 10**6
table = [0]*(MAX+1)
for x in map(int,input().split()):
    table[x] += 1
for i in range(MAX+1):
    if table[i]:
        for j in range(2*i if table[i] == 1 else i, MAX+1, i):
            table[j] = 0
print(sum(table))

n = int(input())
a = list(map(int,input().split()))

ma = max(a)
m = [0]*(ma + 1)

for i in a:
    if m[i] == 1:
        m[i] = 2
        continue
    for j in range(i,ma+1,i):
        m[j]+=1
ans = 0
for i in a:
    if m[i] == 1:
        ans += 1
print(ans)

import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n = int(input())
    A = list(map(int,input().split()))
    A.sort()
    max_A = max(A)
    dp = [True] * (max_A+1) # iより小さいiの約数がAに存在しない
    multi = [0] * (max_A+1) #重複個数
    for a in A:
        multi[a] += 1
        if multi[a] > 1: continue
        x = a
        while x + a <= max_A:
            x += a
            dp[x] = False
    ans = 0
    for a in A:
        if dp[a] and multi[a]==1:
            ans += 1
    print(ans)

def __starting_point():
    main()
__starting_point()

N = int(input())
A = list(map(int, input().split()))
max_a = max(A) + 1
counter = [0 for _ in range(max_a)]

for i in A:
    for j in range(i, max_a, i):
        counter[j] += 1

res = 0

for a in A:
    if counter[a] == 1:
        res += 1

print(res)


'''
Created on 2020/08/23

@author: harurun
'''
def main():
  from collections import Counter
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write

  ans=0
  N=int(pin())
  A=list(map(int,pin().split()))
  c=Counter(A)
  t=max(A)
  dp=[True]*t
  for i in A:
    if dp[i-1]:
      n=2*i
      while n<=t:
        dp[n-1]=False
        n+=i
  for k in A:
    if c[k]==1 and dp[k-1]:
      ans+=1
  print(ans)
  return
main()


N = int(input())
A = list(map(int, input().split()))
 
M = 10**6 + 1
 
cnt = [0] * M
 
for a in A:
    if cnt[a] != 0:
        cnt[a] += 1
        continue
    for b in range(a, M, a):
        cnt[b] += 1
 
ans = 0
for a in A:
    if cnt[a] == 1:ans += 1
 
print(ans)

import sys
input = sys.stdin.readline
n=int(input())
a=list(map(int, input().split()))
a.sort()
m=max(a)
arr=[0]*(m+1)
flag=[True]*(m+1)
ans=0
for i in range(n):
    if flag[a[i]]:
        arr[a[i]]+=1
        if not arr[a[i]]==1:
            continue
        for j in range(a[i]*2,m+1,a[i]):
            flag[j]=False
print(arr.count(1))

import sys
input = sys.stdin.readline

#n = int(input())
#l = list(map(int, input().split()))

'''
a=[]
b=[]
for i in range():
    A, B = map(int, input().split())
    a.append(A)   
    b.append(B)'''
def cal(n,li):
    lis=[True]*(n+1)
    for item in li:
        if lis[item]:
            for i in range(item*2,n+1,item):
                lis[i]=False
    return lis
from collections import Counter

n=int(input())
a=list(map(int,input().split()))
a.sort()
l=cal(a[-1],a)
ll=Counter(a)
#print(l,ll)
ans=0
for i in range(n):
    if ll[a[i]]==1:
        if l[a[i]]:
            ans+=1

print(ans)


N = int(input())
A_list = list(map(int, input().split()))

yakusu = [0] * (10 ** 6 + 10)
for i in range(N):
    a = A_list[i]
    if yakusu[a] != 0:
        yakusu[a] = 2
        continue
    for j in range(a, 10 ** 6 + 10, a):
        yakusu[j] += 1

ans = 0
for a in A_list:
    if yakusu[a] == 1:
        ans += 1
print(ans)

n = int(input())
a = list(map(int,input().split()))
m = max(a)
flag = [True]*(m+1)
c = [0]*(m+1)
b = list(sorted(a))
for i in b:
    x = i + i
    while x <= m:
        flag[x] = False
        x += i
    c[i] += 1
ans = 0
x = 0
l = []
ans = 0
for i in a:
    if flag[i] and c[i] <= 1:
        ans += 1
print(ans)

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
C = Counter(A)

A = set(A)
MAX_A = 10 ** 6
X = [0] * (MAX_A + 1)
for a in A:
    for i in range(a, MAX_A + 1, a):
        X[i] += 1

ans = len([a for a in A if (X[a] == 1) and (C[a] == 1)])
print(ans)

#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from math import gcd
from itertools import combinations,permutations,accumulate, product # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
import math
import bisect
import heapq
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入g
#
# インデックス系
# int min_y = max(0, i - 2), max_y = min(h - 1, i + 2);
# int min_x = max(0, j - 2), max_x = min(w - 1, j + 2);
#
#
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
#mod = 998244353
INF = float('inf')
from sys import stdin
readline = stdin.readline
def readInts():
  return list(map(int,readline().split()))
def readTuples():
    return tuple(map(int,readline().split()))
def I():
    return int(readline())
n = I()

A = readInts()

is_ok = [0] * (10**6+1)
se = set(A)
C = Counter(A)
for a in se:
    for b in range(a,10**6+1,a):
        is_ok[b] += 1
ans = 0
for i in range(n):
    if C[A[i]] >= 2:
        continue
    if is_ok[A[i]] == 1:
        ans += 1
print(ans)


N = int(input())
A = list(map(int, input().split()))
A = sorted(A)
L = [0] * (A[-1]+1)
for a in A:
    L[a] = 1

for p in A:
    if not L[p]: continue 
    L[p] += 1
    n = 2
    while p*n <= A[-1]:
        L[p*n] = 0
        n += 1

ans = L.count(2)
print(ans)

from collections import Counter
n,*a = map(int,open(0).read().split())
s = set(a)
c = Counter(a)
m = max(s)
l = [True]*(m+1)
ans = 0
for i in range(1,m+1):
  if i in s and l[i]:
    if c[i] == 1:
      ans += 1
    for j in range(1,m//i+1):
      l[i*j] = False
print(ans)

n=int(input())
a=sorted(list(map(int,input().split())))
dp=[0]*(m:=a[-1]+1)
for i in a:
  dp[i]+=1
for i in a:
  for j in range(i*2,m,i):
    dp[j]+=1
ans=0
for i in a:
  if dp[i]==1:
    ans+=1
print(ans)

#!/usr/bin/env python

n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
ma = a[-1]

dup = [0 for _ in range(ma+1)]
div = [0 for _ in range(ma+1)]

for i in range(n):
    dup[a[i]] += 1
#print('dup =', dup)

for i in range(n):
    for j in range(a[i], ma+1, a[i]):
        div[j] += 1
#print('div =', div)

ans = 0 
for i in range(n):
    if div[a[i]] == 1:
        ans += 1
print(ans)


n=int(input())
a=list(map(int,input().split()))
ans=0
a.sort()
num=a[-1]
dp=[True]*num
seen=[0]*num
for i in range(n):
    num2=a[i]
    if dp[num2-1]==True:
        if seen[num2-1]==1:
            dp[num2-1]=False
        for j in range(2,num//num2+1):
            dp[j*num2-1]=False
    seen[a[i]-1]=1
ans=0
for i in range(n):
    if dp[a[i]-1]==True:
        ans+=1
print(ans)


# -*- coding: utf-8 -*-
"""
Created on Sat Sep 12 00:21:05 2020

@author: liang
"""

N = int(input())
A = [int(x) for x in input().split()]

A.sort()
A += [-1]
dp = [0] + [True]*10**6
def Solve():
    if A[0] == 1:
        if len(A) >= 2 and A[1] == 1:
            return 0
        else:
            return 1
    k = 0
    for i in range(1,10**6+1):
        if i == A[k]:
            #print("A",i)
            #kの処理
            tmp = A[k]
            cnt = 0
            while k <= N-1 and A[k] == tmp:
                #print("B",k,tmp)
                cnt += 1
                if cnt == 2:
                    dp[tmp] = False
                k += 1
            #倍数の消去
            for j in range(2*i,10**6+1,i):
                #print("C")
                dp[j] = False
    ans = 0
    for a in A[:-1]:
        if dp[a]:
            ans += 1
    return ans

ans = Solve()
print(ans)