CodeEff/ECCO huggingface dataset:
# Original solution
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

from collections import deque

N = int(eval(input()))
a = [int(y) for y in input().split()]
a.sort()

q = deque()
for i in range(N):
    q.append(a[i])

cnt = 0

while N > 0:
    flag = True
    res = q.popleft()

    for i in range(N-1):
        now = q.popleft()
        if now == res and flag:
            cnt -= 1
            flag = False
        if now % res != 0:
            q.append(now)
    
    N = len(q)
    cnt += 1

print(cnt)

# Optimized solution
n = int(eval(input()))
a = [int(i) for i in input().split()]

max_a = max(a)
flag = [True for i in range(max_a+1)]

dup = set()
for i in range(n):
    if a[i] in dup:
        flag[a[i]] = False
    else:
        dup.add(a[i])
    for j in range(2*a[i], max_a+1, a[i]):
        flag[j] = False

ans = 0
for i in a:
    ans += flag[i]
print(ans)
# Original solution
n = int(eval(input()))
a = [int(i) for i in input().split()]

max_a = max(a)
flag = [True for i in range(max_a+1)]

dup = set()
for i in range(n):
    if a[i] in dup:
        flag[a[i]] = False
    else:
        dup.add(a[i])
    for j in range(2*a[i], max_a+1, a[i]):
        flag[j] = False

ans = 0
for i in a:
    ans += flag[i]
print(ans)

# Optimized solution
n = int(eval(input()))
a = [int(i) for i in input().split()]

max_a = max(a)
flag = [True for i in range(max_a+1)]

dup = set()
for i in range(n):
    if a[i] in dup:
        flag[a[i]] = False
    else:
        dup.add(a[i])
        for j in range(2*a[i], max_a+1, a[i]):
            flag[j] = False

ans = 0
for i in a:
    ans += flag[i]
print(ans)
# Original solution
N = int(eval(input()))
A = list(map(int, input().split()))
A.sort()
used = [0 for _ in range(int(1e6+1))]

ans = 0
for i in A:
    if used[i] == 1:
        used[i] += 1
        continue
    for j in range(i, len(used), i):
        used[j] += 1
for a in A:
    if used[a] == 1:
        ans += 1
print(ans)


# Optimized solution
N = int(eval(input()))
A = list(map(int, input().split()))
A.sort()
used = [0 for _ in range(int(1e6+1))]

ans = 0
for i in A:
    if used[i] > 0:
        used[i] += 1
        continue
    for j in range(i, len(used), i):
        used[j] += 1
for a in A:
    if used[a] == 1:
        ans += 1
print(ans)
# Original solution
from collections import Counter
N = int(eval(input()))
A = list(map(int, input().split()))
A.sort()
count_of_a = Counter(A)
# すでに出現した倍数の場合はアウト
ans = 0
max_A = max(A)
dp = [True] * (max_A+1)
happpend = set()
for a in A:
    if count_of_a[a] >= 2:
        # 複数出現するとしても，初めての要素の場合は処理を行う
        if a in happpend:
            continue
        x = a*2
        while x <= max_A:
            dp[x] = False
            x += a
        happpend.add(a)
    else:
        if dp[a]:
            ans += 1
        x = a*2
        while x <= max_A:
            dp[x] = False
            x += a
        happpend.add(a)
print(ans)


# Optimized solution
from collections import Counter
N = int(eval(input()))
A = list(map(int, input().split()))
A.sort()
count_of_a = Counter(A)
# すでに出現した倍数の場合はアウト
ans = 0
max_A = max(A)
dp = [True] * (max_A+1)
happpend = set()
for a in A:
    if count_of_a[a] >= 2:
        # 複数出現するとしても，初めての要素の場合は処理を行う
        if a in happpend:
            continue
        x = a*2
        while x <= max_A:
            dp[x] = False
            x += a
        happpend.add(a)
    else:
        if dp[a]:
            ans += 1
        x = a*2
        while x <= max_A:
            dp[x] = False
            x += a
print(ans)
# Original solution
from collections import Counter
import bisect
N = int(eval(input()))
A = list(map(int,input().split()))



cnt = Counter(A)
A.sort()
ans = 0
P = [0] * (10**6+1)
#print(cnt)
for a in A:
    if P[a]==0 and cnt[a]==1:
        ans += 1
    for i in range(10**7):
        x = a*i
        if x>10**6:
            break
        P[x] = 1

print (ans)




# Optimized solution
from collections import Counter
import bisect
N = int(eval(input()))
A = list(map(int,input().split()))



cnt = Counter(A)
A.sort()
ans = 0
P = [0] * (10**6+1)
#print(cnt)
for a in A:
    if P[a]==0:
        for i in range(10**7):
            x = a*i
            if x>10**6:
                break
            P[x] = 1
        if cnt[a]==1:
            ans +=1

print (ans)
# Original solution
import math
from collections import Counter

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

cnt = Counter(a)
a.sort()

cand = a
ans = 0
while cand:
    p = cand[0]
    if cnt[p] == 1:
        ans += 1
    nex = []
    for num in cand:
        if num == p:
            continue
        if num % p:
            nex.append(num)
    cand = nex

print(ans)

# Optimized solution
n = int(eval(input()))
a = list(map(int, input().split()))

a.sort()
am = a[-1]

memo = [0] * (am+1)

for ai in a:
    memo[ai] = 1

p = -1

for ai in a:
    if ai == p:
        memo[ai] = 0
        continue
    for j in range(2, am // ai + 1):
        memo[ai * j] = 0
    p = ai

print((sum(memo)))
# Original solution
M = int(eval(input()))
A=list(map(int,input().split()))
A.sort()
ma=A[-1]
is_prime = [True] * (ma + 1)
for i in A:
    if not is_prime[i]:
        continue
    for j in range(i * 2, ma + 1, i):
        is_prime[j] = False
k=[i for i in range(ma + 1) if is_prime[i]]
A=[x for x in set(A) if A.count(x) == 1]
s=set(k) & set(A)
print((len(s)))

# Optimized solution
M = int(eval(input()))
A=list(map(int,input().split()))
A.sort()
ma=A[-1]
is_prime = [True] * (ma + 1)
for i in A:
    if not is_prime[i]:
        continue
    for j in range(i * 2, ma + 1, i):
        is_prime[j] = False
k=[i for i in range(ma + 1) if is_prime[i]]
N=[]
if len(A)==1:
    print((1))
else:
    if A[0] !=A[1]:
        N.append(A[0])
    for i in range(1,len(A)-1):
        if A[i-1]!=A[i] and A[i]!=A[i+1]:
            N.append(A[i])
    if A[len(A)-2] != A[len(A)-1]:
        N.append(A[len(A)-1])
    s=set(k) & set(N)
    print((len(s)))
# Original solution
from collections import Counter
import math

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

a.sort()

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

is_prime[0] = False

for i in set(a):
    for j in range(2 * i, max(a)+1, i):
        is_prime[j] = False

result = 0
c = Counter(a)

for e in set(a):
        if is_prime[e] and c[e] == 1:
    #        print('e = {}'.format(e))
             result += 1

print(result)



# Optimized solution
from collections import Counter
import math

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

a.sort()

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

is_prime[0] = False

maxA = max(a)

for i in set(a):
    for j in range(2 * i, maxA+1, i):
        is_prime[j] = False

result = 0
c = Counter(a)

for e in set(a):
        if is_prime[e] and c[e] == 1:
    #        print('e = {}'.format(e))
             result += 1

print(result)
# Original solution
from collections import Counter

def main():
    n = int(eval(input()))
    a = sorted([int(i) for i in input().split()])
    table = [True for i in range(max(a))]
    res = 0
    amax = max(a)

    for i in a:
        if (amax/2) + 1 < i:
            break
        if table[i-1] is False:
            continue
        for j in range(i*2, amax+1, i):
            table[j-1] = False

    c = Counter(a)
    for i in set(a):
        if table[i-1]:
            if c[i] == 1:
                res += 1
    print(res)

if __name__ == '__main__':
    main()



# Optimized solution
from collections import Counter

def main():
    n = int(eval(input()))
    a = sorted([int(i) for i in input().split()])
    table = [True for i in range(max(a))]
    res = 0
    amax = max(a)

    for i in a:
        if table[i-1] is False:
            continue
        for j in range(i*2, amax+1, i):
            table[j-1] = False

    c = Counter(a)
    for i in set(a):
        if table[i-1]:
            if c[i] == 1:
                res += 1
    print(res)

if __name__ == '__main__':
    main()
# Original solution
c=[0]*8**7
for a in[*open(i:=0)][1].split():c[int(a)]+=1
while i<1e6:
 i+=1;j=i
 while j<1e6:j+=i;c[j]*=c[i]<1
print((c.count(1)))

# Optimized solution
m=8**7
c=[0]*m
for a in[*open(0)][1].split():c[int(a)]+=1
i=r=0
while~i+m:
 i+=1;r+=c[i]==1
 if c[i]:c[::i]=[0]*-(-m//i)
print(r)
# Original solution
n = int(eval(input()))
A = sorted(list(map(int, input().split())))
dp = [0] * (10 ** 6 + 10)
for x in A:
    i = 0
    while x + i <= 10 ** 6 + 10:
        dp[(x-1) + i] += 1
        i += x

cnt = 0
for x in A:
    if dp[x-1] == 1:
        cnt += 1

print(cnt)

# Optimized solution
n = int(eval(input()))
A = sorted(list(map(int, input().split())))
dp = [0] * (10 ** 6 + 10)
for x in A:
    i = 0
    while x + i <= 10 ** 6 + 10:
        if dp[(x-1)] == 2:
            break
        else:
            dp[(x-1) + i] += 1
            i += x

cnt = 0
for x in A:
    if dp[x-1] == 1:
        cnt += 1

print(cnt)
# Original solution
import sys
input = sys.stdin.readline

n = int(eval(input()))

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

c = [0] * (10**6+1)
for i in a:
    c[i] += 1

uni = []

for i in a:
    if c[i] == 1:
        uni.append(i)

b = [0 for _ in range(10**6+1)]

for i in a:
    for j in range(i*2, 10**6+1, i):
        b[j] = 1

cnt = 0
for i in uni:
    if b[i] == 0:
        cnt += 1

print(cnt)

# Optimized solution
n = int(eval(input()))

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

c = [0] * (10**6+1)
for i in a:
    c[i] += 1

uni = []
a = list(set(a))

for i in a:
    if c[i] == 1:
        uni.append(i)

b = [0 for _ in range(10**6+1)]

for i in a:
    for j in range(i*2, 10**6+1, i):
        b[j] = 1

cnt = 0
for i in uni:
    if b[i] == 0:
        cnt += 1

print(cnt)
# Original solution
n = int(eval(input()))
a = list(map(int,input().split()))
m = max(a) + 10
li = [0]*m 
for x in a:
    li[x] += 1
ans = 0
for i in range(1,m):
    if li[i]: 
        if li[i]==1: 
            ans += 1 
        for j in range(i,m,i): 
            li[j] = 0
print(ans)

# Optimized solution
n = int(eval(input()))
a = list(map(int,input().split()))
m = max(a) + 1
li = [0]*m 
for x in a:
    li[x] += 1
ans = 0
for i in range(1,m):
    if li[i]: 
        if li[i]==1: 
            ans += 1 
        for j in range(i,m,i): 
            li[j] = 0
print(ans)
# Original solution
N = int(eval(input()))
A = list(map(int,input().split()))

D = [0] * (10**6 + 1)
A.sort()
for i in range(N):
    D[A[i]] += 1
    
ans = 0
for i in range(1, 10**6+1):
    if D[i]:
        if D[i]==1:
            ans += 1
        for j in range(i,A[-1]+1,i):
            D[j] = 0
print(ans)

# Optimized solution
N = int(eval(input()))
A = list(map(int,input().split()))
m = max(A) + 1
cnt = [0]*m
for i in A:
    cnt[i] += 1
ans = 0
for i in range(1,m):
    if cnt[i]:
        if cnt[i]==1:
            ans += 1
        for j in range(i,m,i):
            cnt[j] = 0
print(ans)
# Original solution
N = int(eval(input()))
A = list(map(int, input().split()))
A = sorted(A)
B = []
for i in range(N):
  if A.count(A[i]) != 1:
    continue
  else:
    p = 0
    for j in B:
      if A[i] % j == 0:
        p = 1
    if p == 0:
      B.append(A[i])
      
print((len(B)))

# Optimized solution
N = int(eval(input()))
As = list(map(int,(input().split())))

As.sort()
# print(As)

all_nums = [0] * (As[-1] + 1)

for A in As:
    all_nums[A] += 1
#print(all_nums)
dup = 0

for i, num in enumerate(all_nums):
    if num == 0: #その数が一つもないなら無視
        continue
    if num > 1: #同じ数が複数ある場合はあとで除くためにカウント
        dup += num
    j = 2
    while i * j <= As[-1]:
        all_nums[i*j] = 0
        j += 1
    #print(all_nums)

print((sum(all_nums)-dup))
# Original solution
def resolve():
    n = int(eval(input()))
    A = list(map(int, input().split()))

    uni = sorted(list(set(A)))
    dup = [x for x in set(A) if A.count(x) > 1]
    m = set()

    ans = 0

    for a in uni:
        if a in m: continue

        i = 0
        a_max = uni[len(uni)-1]

        while True:
            m.add(a * i)
            if a*i < a_max:
                i += 1
            else:
                break
        
        if a not in dup:
            ans += 1
 
    print(ans)
 
resolve()

# Optimized solution
def resolve():
    n = int(eval(input()))
    A = list(map(int, input().split()))
    max_a = max(A)
    m = set()
    checked = set()
    duplicated = set()

    for a in A:
        if a in checked:
            duplicated.add(a)
            continue

        i = 2
        while a*i <= max_a:
            m.add(a*i)
            i += 1

        checked.add(a)

    ans = 0
    for a in A:
        if a in duplicated: continue

        if a not in m:
            ans += 1
    
    print(ans)
 
resolve()
# Original solution
from collections import Counter
N=int(eval(input()))
A=list(map(int, input().split()))
S=Counter(A)
T=set(S)
# print(S)
# print(T)
# 篩？
ct=0
L=list(S.keys())
L.sort()
# print(L)

for i in range(len(L)):
    a=L[i]
    if a not in T:
        continue
    T.remove(a)
    if S.get(a)==1:
        ct+=1
    tmp=T.copy()
    # print(tmp)
    for n in T:
        if n%a==0:
            tmp.difference_update({n,})
    T=tmp
print(ct)

# Optimized solution
N = int(eval(input()))
A = list(map(int, input().split()))
A.sort()
m = max(A)
sieve = [True]*(m+1)
sieve[0] = False
ct = 0
for i in range(N):
    n = A[i]
    if sieve[n] == False:
        continue
    if i < N-1 and n == A[i+1]:
        sieve[n] = False
    if sieve[n] == True:
        ct += 1
    for k in range(n*2, m+1, n):
        sieve[k] = False
print(ct)
# Original solution
n = int(eval(input()))
a = list(map(int,input().split()))

m = [0]*(10**6 + 1)

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

# Optimized solution
n = int(eval(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)
# Original solution

N=int(eval(input()))
A=list(map(int, input().split()))
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]

ans=0

for i in range(N):
    Acp=A.copy()
    kkk=Acp.pop(i)
    a=set(make_divisors(A[i]))
    b = a&set(Acp)
    if len(b)==0:
        ans+=1
print(ans)

# Optimized solution
N= int(eval(input()))
a =list(map(int,input().split()))
a.sort()
ans=0
Amax=max(a)
DP=[1]*(Amax+1)#これが0のとき、該当する数はカウント済み
#上から順に攻めていく
for i in range(N-1):
    p=a[i]
    if DP[p]==1:#まだ数えられていなかったら
        for j in range(Amax//p+1):#倍数をすべて0にする
            DP[p*j]=0
        if p!=a[i+1]:#隣の数と違うならば
            ans+=1
if DP[Amax]==1:#最後の数は隣の数と比べられんので個別判断
    ans+=1

print(ans)
# Original solution
import sys
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
INF = 1000000000000

n = I()
a = LI()

a.sort()
f = [False]*n

if(n > 1):
    for i in range(1,n):
        if(a[i-1] == a[i]):
            f[i-1] = True
        for j in range(0,i):
            if(a[i] % a[j] == 0):
                f[i] = True
                break

count = 0
for i in range(n):
    if(not f[i]):
        count += 1

print(count)

# Optimized solution
import sys
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
INF = 1000000000000

n = I()
a = LI()

a.sort()
m = a[n-1]
flg = [False]*(m+1)

count = 0
for x in range(n):
    v = a[x]
    if(not flg[v]):
        i = v
        while(i <= m):
            flg[i] = True
            i += v
        if(x == n-1 or v != a[x+1]):
            count += 1

print(count)
# Original solution
N = int(eval(input()))
M = 10 ** 6
A = list(map(int, input().split()))
B = [0] * (M + 1)
for a in A:
    B[a] +=1
C = [1] * (M + 1)
for i in A:
    for j in range(i, M + 1, i):
        if i == j:
            if B[i] > 1:
                C[i] = 0
        else:
            C[j] = 0
A = set(A)
ans = 0
for a in A:
    if C[a]:
        ans += 1
print(ans)


# Optimized solution
N = int(eval(input()))
M = 10 ** 6
A = list(map(int, input().split()))
B = [0] * (M + 1)
for a in A:
    B[a] +=1
C = [1] * (M + 1)
A = set(A)
for i in A:
    for j in range(i, M + 1, i):
        if i == j:
            if B[i] > 1:
                C[i] = 0
        else:
            C[j] = 0
ans = 0
for a in A:
    if C[a]:
        ans += 1
print(ans)
# Original solution
n = int(eval(input()))
arr = list(map(int, input().split()))
arr = sorted(arr)
m = arr[-1]
tf = [True] * (m+1)
cnt = 0
        
for i in range(n):
  ai = arr[i]
  if tf[ai] == True:
    cnt += 1
    for j in range(ai, m+1, ai):
      tf[j] = False
    if ai in arr[i+1:]:
      cnt -= 1
    

print(cnt)

# Optimized solution
n = int(eval(input()))
arr = list(map(int, input().split()))
arr = sorted(arr)
m = arr[-1]
li = [0]*(m+1)
cnt = 0
        
for i in arr:
  for j in range(i, m+1, i):
    li[j] += 1

for i in arr:
  if li[i] == 1:
    cnt += 1

print(cnt)
# Original solution
import sys
import time

def main():
    N = int(eval(input()))
    As = list(map(int, input().split()))
    As.sort()
    made = As[-1]
    lis = [True for _ in range(made)]
    for i in range(len(As)):
        if As.count(As[i]) > 1:
            lis[As[i]-1] = False

    for i in As:
        for j in range(2, int(made/i)+1):
            if lis[i*j-1] == False:
                continue
            lis[i*j-1] = False
    answer = len([int(x) for x in As if lis[x-1]])
    

    print(answer)

if __name__ == '__main__':
    #start = time.time()
    main()
    #elapsed_time = time.time() - start
    #print("経過時間:{}".format(elapsed_time * 1000) + "[msec]")

# Optimized solution
#import time

def main():
    N = int(eval(input()))
    As = list(map(int, input().split()))

    As.sort()
    amax = max(As) + 1
    lis = [True] * amax
    ans = 0

    for i in range(N-1):
        if lis[As[i]]:
            for j in range(As[i], amax, As[i]):
                lis[j] = False
            if As[i] < As[i+1]:
                ans += 1
    if lis[-1]:
        ans += 1

    return ans

if __name__ == '__main__':
    #start = time.time()
    print((main()))
    #elapsed_time = time.time() - start
    #print("経過時間:{}".format(elapsed_time * 1000) + "[msec]")
# Original solution
N = int(eval(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]+=10

print((B.count(1)))

# Optimized solution
N = int(eval(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)))
# Original solution
N = int(eval(input()))
A = list(map(int, input().split()))
A.sort()

flag = 1 
cnt = 0 

for i in range(N):
        if i + 1 > len(A):
                break
        flag = 1 
        for j in reversed(list(range(i + 1, len(A)))):
                if A[j] == A[i]:
                        flag = -1
                if A[j] % A[i] == 0:
                        del A[j]
        if flag == -1: 
                cnt += 1

print((len(A) - cnt))

# Optimized solution
N = int(eval(input()))
A = list(map(int, input().split()))

A.sort()

l = [0] * (A[N - 1] + 1)

for i in A:
        j = i 
        while j <= A[N - 1]: 
                l[j] += 1
                j += i 

cnt = 0 
for k in A:
        if l[k] == 1:
                cnt += 1

print(cnt)
# Original solution
def divisor(n,A):
    ass = []
    for i in range(1,int(n**0.5)+1):
        if n%i == 0:
            if i in A:
                return False
            ass.append(i)
            if i**2 == n:
                continue
            if n//i in A:
                return False
    return True

def main():
    N = int(eval(input()))
    A = list(map(int, input().split()))
    A.sort(reverse=True)
    cnt = 0
    for i in range(N):
        if i > 0 and A[i] == A[i-1]:
            continue
        if divisor(A[i],A[i+1:]):
            cnt += 1

    print(cnt)


if __name__ == "__main__":
    main()

# Optimized solution
def primes(n):
    ass = []
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass

def main():
    N = int(eval(input()))
    A = list(map(int, input().split()))
    max_A = max(A)
    ans = [0] * (max_A + 1)
    A.sort()
    for a in A:
        tmp = 1
        b = 0
        while b <= max_A:
            b = a * tmp
            if b > max_A:
                break
            ans[b] += 1
            tmp += 1
    cnt = 0
    for a in A:
        if ans[a] == 1:
            cnt += 1

    print(cnt)


if __name__ == "__main__":
    main()
# Original solution
n = int(eval(input()))
*A, = list(map(int, input().split()))
maxA = max(A)
# C[a] = A内のaの個数
C = {a: 0 for a in A}
for a in A:
    C[a] += 1
# D[a]=1: Aにaより小さいaの約数が存在する
D = {a: 0 for a in A}
for a in A:
    if C[a] > 0:
        t = 2
        while a * t <= maxA:
            D[a * t] = 1
            t += 1
ans = 0
for a in A:
    if C[a] == 1 and D[a] == 0:
        ans += 1
print(ans)

# Optimized solution
n = int(eval(input()))
A = list(map(int, input().split()))
maxA = max(A)
# C[a] = A内のaの個数
C = {a: 0 for a in A}
for a in A:
    C[a] += 1
# D[a]=1: Aにaより小さいaの約数が存在する
D = {a: 0 for a in A}
for a in A:
    if C[a] > 0:
        t = 2
        while a * t <= maxA:
            D[a * t] = 1
            t += 1
ans = 0
for a in A:
    if C[a] == 1 and D[a] == 0:
        ans += 1
print(ans)
# Original solution
_,*a=list(map(int,open(0).read().split()))
a=[i for i in a if a.count(i)==1]
a.sort()
b=0
while a:
    b+=1
    a=[i for i in a[1:] if i%a[0]!=0]
print(b)

# Optimized solution
N  = int(eval(input()))
c = list(map(int,input().split()))

c.sort()
a = c[N-1]
list_c = [0]*(a+1)
for i in c:
  mal = 2
  b = i
  while i<=a:
    list_c[i]+=1
    i = b*mal
    mal+=1
count = 0
for i in c:
  if list_c[i]==1:
    count+=1
print(count)
# Original solution
n=int(eval(input()))
a=list(map(int,input().split()))
a.sort()

# 小さい側から処理する。a[i]について、10**6 以下のすべての倍数をset()として持つ。
# ただし、set内に存在しない==初出の約数のみ倍数計算をしてカウントする。
# 例えば、2,6,... となった場合、(6の倍数セットは2の倍数セットの下位集合となるため計算不要)

s=set()
cnt=0
for i,aa in enumerate(a):
  if aa not in s:
    # 同値が複数ある場合、カウントしない。sortしているため、同値は並ぶ
    if i+1 == len(a) or aa != a[i+1]:
      cnt+=1
    
    for i in range(1,10**6+1):
      ma=aa*i
      if ma > 10**6:
        break
      s.add(ma)

print(cnt)
    


# Optimized solution
# 30分ぐらい？で溶けた！計算量は直感だよりだったが。
# → エラトステネスの篩 に相当する実装らしい。

# リスト内の倍数・約数関係を判定し、カウントする。
# 二重ループで判定するとTLEになるため、小さい値の可能な倍数を計算して保存するようにした。
# メモを set() ではなく 配列 で実装するテスト

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

# 小さい側から処理する。a[i]について、10**6 以下のすべての倍数をset()として持つ。
# ただし、set内に存在しない==初出の約数のみ倍数計算をしてカウントする。
# 例えば、2,6,... となった場合、(6の倍数セットは2の倍数セットの下位集合となるため計算不要)

s=[False]*(10**6+1)
cnt=0
for i,aa in enumerate(a):
  if s[aa]:
    continue

  # 同値が複数ある場合、カウントしない。
  if i+1 == len(a) or aa != a[i+1]:
    cnt+=1
  for i in range(1,10**6+1):
    ma=aa*i
    if ma > 10**6:
      break
    s[ma]=True

print(cnt)