CodeEff/ECCO huggingface dataset:
# Original solution
n = int(eval(input()))
a = list(map(int, input().split()))
checker = [1 for _i in range(10**6+1)]
a.sort()
a.append(-1)
result = 0
for i in range(n):
    if a[i] == a[i+1]:
        checker[a[i]] = 0
    result += checker[a[i]]
    checker[a[i]] = 0
    x = 2
    while a[i]*x <= 10**6:
        checker[a[i]*x] = 0
        x += 1
print(result)

# Optimized solution
n = int(eval(input()))
a = list(map(int, input().split()))
checker = [1 for _i in range(10**6+1)]
a.sort()
a.append(-1)
result = 0
for i in range(n):
    if a[i] == a[i-1]:
        continue
    if a[i] == a[i+1]:
        checker[a[i]] = 0
    result += checker[a[i]]
    checker[a[i]] = 0
    x = 2
    while a[i]*x <= 10**6:
        checker[a[i]*x] = 0
        x += 1
print(result)
# Original solution
def make_divisors(n):
    i = 1
    flg = True
    while i*i <= n:
        if n % i == 0:
            if i in s and i != n:
                flg = False
                break
            ii = n//i
            if i != ii:
                if ii in s and ii != n:
                    flg = False
                    break
        i += 1
    return flg

def main():
    cnt = 0
    from collections import Counter
    c = Counter(a)
    for i in range(n):
        if c[a[i]] > 1:
            continue
        if make_divisors(a[i]):
            cnt += 1
    print(cnt)

if __name__ == '__main__':
    n = int(eval(input()))
    a = list(map(int,input().split()))
    s = set(a)
    main()

# Optimized solution
def main():
    n = int(eval(input()))
    a = list(map(int,input().split()))
    ans = set(a)
    ma = max(a)
    from collections import Counter
    c = Counter(a)
    for i in range(n):
        t = a[i]
        if c[t] > 1 and t in ans:
            ans.remove(t)
            continue
        j = 2
        tmp = t*j
        while tmp <= ma:
            if tmp in ans:
                ans.remove(tmp)
            j += 1
            tmp = t*j
    print((len(ans)))

if __name__ == '__main__':
    main()
# Original solution
from math import sqrt
from collections import Counter


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

    ans = 0
    p = [0] * (10**6 + 1)
    c = Counter(A)

    for a in list(c.keys()):
        tmp = a * 2
        while tmp <= 10**6:
            p[tmp] = 1
            tmp += a

    for a in A:
        if p[a] == 0 and c[a] == 1:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()


# Optimized solution
from math import sqrt
from collections import Counter


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

    ans = 0
    p = [0] * (10**6 + 1)
    c = Counter(A)

    for a in list(c.keys()):
        tmp = a * 2
        while tmp <= 10**6:
            p[tmp] = 1
            tmp += a

    for a in A:
        if p[a] == 0 and c[a] == 1:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()
# Original solution
import sys
def input():
    return sys.stdin.readline()[:-1]

from itertools import count
from collections import Counter

def test():
    n = int(eval(input()))
    a = sorted([int(i) for i in input().split()])
    mxn = a[-1]
    c = Counter(a)
    a = sorted(list(set(a)))
    r = dict()
    for i in a:
        for j in count(1):
            if i * j > mxn: break
            r[i * j] = r.get(i * j, 0) + 1
    print((len([k for k in a if r[k] == 1 and c[k] == 1])))


test()

# Optimized solution
# https://qiita.com/HUVEC/items/97739696ab51cacd10f2
N = int(eval(input()))
A = list(map(int, input().split()))
A.sort()                  #エラトステネスの篩にかけるためソート
Amax = A[-1]
dp = [1]*(Amax+1)         #Aの最大値までのエラトステネスの篩を作る。
ans = 0
for i in range(len(A)-1):
  p = A[i]
  if dp[p] == 1:          #A[i]がA[j]の倍数でないかをエラトステネスの篩でチェック
    for q in range(Amax//p+1):
      dp[p*q] = 0         #A[i]の倍数をすべて0にする
    if A[i] != A[i+1]: 
      ans += 1            #A[i]が重複していなければカウント
if dp[Amax] == 1:         #重複チェック時にレンジオーバーするためAmaxだけ別で判定 
  ans += 1
print(ans)
# Original solution
n = int(eval(input()))
a = list(map(int, input().split()))
count = 0
for i in range(n):
    for j in range(n):
        if i != j and a[i] % a[j] == 0:
            break
    else:
        count += 1
print(count)


# Optimized solution
def func(n, a):
    mx = max(a)
    x = [0] * (mx + 1) # len(x)
    for i in a:
        x[i] += 1
    for i in range(1, mx + 1):
        if x[i] != 0:
            for j in range(2 * i, mx + 1, i):
                x[j] = 0
        if x[i] > 1:
            x[i] = 0
    print((sum(x))) # 31401

n = int(eval(input()))
a = list(map(int, input().split()))
func(n, a)
# Original solution
#エラストテネスのふるいを用いることを考える
#出たものの倍数をいれるダメリストを準備しておく。
#各a[i]についてダメリストに入っていないものが求める個数である
#同じものが複数回出てくるもの（Counterを使えばいい）に関してはダメリストにその数もいれれば良い
from collections import Counter
n=int(eval(input()))
a=list(map(int,input().split()))
a.sort()
min_a=a[0]
max_a=a[n-1]
#同じものが複数回出てくるもののcheck
dic=Counter(a)
#別リスト
check=set()

for i in range(n):
  if a[i] not in check:
    if dic[a[i]]>=2:
      check.add(a[i])
    for j in range(2,int((max_a)/a[i])+1):
      check.add(a[i]*j)
ans=0
for i in range(n):
  if a[i] not in check:
    ans=ans+1

print(ans)

  
    
    

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

num_list=set()
prime_list=set()

from collections import Counter
dic=Counter(a)
a=set(a)

for i in dic:
  if dic[i]>=2:
    dic[i]=0
  if i not in num_list:
    for j in range(i*2,k+1,i):
      if j in a:
        dic[j]=0
        num_list.add(j)

print((sum(dic.values())))
# Original solution
N = int(eval(input()))
a_list = sorted(list(map(int, input().split())))
dp = [True] * N

for i, ai in enumerate(a_list):
  if dp[i] == False:
    continue
  
  for j, aj in enumerate(a_list[i+1:]):
    if ai == aj:
      dp[i] = False
    if aj%ai == 0:
      dp[i+1+j] = False
  if dp[i] > a_list[-1]**0.5+1:
    break
print((sum(dp)))

# Optimized solution
N = int(eval(input()))
a_list = sorted(list(map(int, input().split())))
a_max = a_list[-1]

count = [0] * (a_max+1)

for a in a_list:
  for j in range(a, a_max+1, a):
    count[j] += 1
  
ans = 0
for a in a_list:
  if count[a] == 1:
    ans += 1
print(ans)
# Original solution
import math
import collections
n=int(eval(input()))
a=list(map(int,input().split()))

l=[]
d=collections.Counter(a)
count=0

for i in list(set(a)):
    c=0
    d[i]-=1
    if d[i]==0:
        del d[i]
    for j in range(1,math.floor(math.sqrt(i))+1):
        if i%j==0:
            if j in d:
                c=1
                break
            if i%(i//j)==0:
                if (i//j) in d:
                    c=1
                    break
    
    if c==0:
        count+=1
    if i not in d:
        d[i]=1
    else:
        d[i]+=1
print(count)

# Optimized solution
n = int(eval(input()))
a = sorted(list(map(int,input().split())))
am = a[-1]+1
b = [0]*am
for i in a:
    b[i]+=1
    if b[i]==1:
        for j in range(i*2,am,i):
            b[j]=2
print((b.count(1)))
# Original solution
import sys

from collections import defaultdict

I=sys.stdin.readline

n=int(I())
arr=sorted(list(map(int,I().split())))
d=defaultdict(int)

for i in arr:
	d[i]+=1

ans=0
visited=[0]*(10**6+1)
for i in arr:
	if d[i]==1 and visited[i]==0:
		ans+=1

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

print(ans)


# Optimized solution
import sys

from collections import defaultdict

I=sys.stdin.readline

n=int(I())
arr=sorted(list(map(int,I().split())))
d=defaultdict(int)

for i in arr:
	d[i]+=1

ans=0
visited=[0]*(arr[-1]+1)
for i in arr:
	if d[i]==1 and visited[i]==0:
		ans+=1

	for j in range(i,arr[-1]+1,i):
		visited[j]=1

print(ans)
# Original solution
n= int(eval(input()))
l=list(map(int,input().split()))

flag=[0]*n

for i in range(len(l)):
    for j in range(len(l)):
        if i==j:
            continue
        elif flag[i]==1:
            continue
        elif l[i]%l[j]==0:
            flag[i]=1
            break
print((flag.count(0)))


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

l.sort()
maxnum=l[len(l)-1]
flag=[0]*(maxnum+1)

for num in l:
    flag[num]+=1
    if flag[num]>1:
        continue
    for j in range(num*2, maxnum+1, num):
        flag[j]+=1
#print(flag)
ans=0

for num in l:
    if flag[num]==1:
        ans+=1
print(ans)
# Original solution

def main():

    MAX_VALUE = 10**6 + 5

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

    cnt = [0] * MAX_VALUE

    ans = 0

    for x in a:

        for i in range(x, MAX_VALUE, x):
            cnt[i] += 1

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

    print(ans)


if __name__ == "__main__":
    main()


# Optimized solution

def main():

    MAX_VALUE = 10**6 + 5

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

    cnt = [0] * MAX_VALUE

    ans = 0

    for x in a:

        if cnt[x] != 0:
            cnt[x] = 2
            continue

        for i in range(x, MAX_VALUE, x):
            cnt[i]+=1

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

    print(ans)


if __name__ == "__main__":
    main()
# Original solution
MAX = 10 ** 6 + 5
N = int(eval(input()))
A = list(map(int, input().split()))
cnt = [0] * MAX
for a in A:
    cnt[a] += 1
for i in range(N):
    a = A[i]
    if cnt[a] == 0:
        continue
    for j in range(2 * a, MAX, a):
        cnt[j] = 0
res = 0
for a in A:
    if cnt[a] == 1:
        res += 1
print(res)

# Optimized solution
MAX = 10 ** 6 + 1
N = int(eval(input()))
A = list(map(int, input().split()))
cnt = [0] * MAX
f = [True] * MAX
for a in A:
    cnt[a] += 1
    if not f[a] or cnt[a] > 1:
        continue
    for j in range(2 * a, MAX, a):
        f[j] = False
res = 0
for a in A:
    if f[a] and cnt[a] == 1:
        res += 1
print(res)
# Original solution
from collections import Counter
N = int(eval(input()))
A = [int(v) for v in input().split()]

l = [1 for i in range(max(A)+1)]
for v in sorted(A):
    for j in range(2*v, max(A)+1, v):
        l[j] = 0

ans = 0
c = Counter(A)
for a in A:
    if c[a] > 1:continue
    ans += l[a]
print(ans)

# Optimized solution
from collections import Counter
N = int(eval(input()))
A = [int(v) for v in input().split()]

m = max(A)
l = [1 for i in range(m+1)]
for v in sorted(A):
    for j in range(2*v, m+1, v):
        l[j] = 0

ans = 0
c = Counter(A)
for a in A:
    if c[a] > 1:continue
    ans += l[a]
print(ans)
# Original solution
from collections import Counter


#nの約数列挙
def divisor(n):
    ass = []
    for i in range(1, int(n**0.5)+1):
        if n%i == 0:
            ass.append(i)
            if i**2 == n:
                continue
            ass.append(n//i)
    return ass  # sortされていない


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

a.sort()
a_max = a[-1]
div = [0]*(a_max+1)
c = Counter(a)
#print(c)
count = 0
already = []
for i in range(n):
    if c[a[i]] != 1:
        div[a[i]] = 1
        continue
    div_a = divisor(a[i])
    for j in div_a:
        if div[j] == 1:
            break
    else:
        count += 1
        div[a[i]] = 1

print(count)

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

a.sort()
a_max = a[-1]
ban = [0]*(a_max+1)

count = 0
for i in range(n):
    if ban[a[i]]:
        continue
    else:
        if i == n-1 or a[i+1] != a[i]:
            count += 1
        x = a[i]
        while x <= a_max:
            ban[x] = 1
            x += a[i]
#print(ban)
print(count)
# Original solution
n=int(eval(input("")))
aa=input("").split(" ")
lista=[]
for i in range(n):
    lista+=[int(aa[i])]
s=0
lista.sort()
listde=set()
for i in range(n-1):
    if(lista[i]==lista[i+1]):
        listde.add(lista[i])
t=0
for i in range(n):
    t=0
    for k in listde:
        if (lista[i]%k==0):
            t=1
            break
    if (t==0):
        s+=1
        listde.add(lista[i])
print(s)
    
        


# Optimized solution
n=int(eval(input("")))
aa=input("").split(" ")
lista=[]
for i in range(n):
    lista+=[int(aa[i])]
lista.sort()
listtf=[]
s=0
for i in range(lista[n-1]):
    listtf+=[True]
for i in range(n):
    
    if(listtf[lista[i]-1]):
        if(i<n-1 and lista[i]==lista[i+1]):
            s-=1
        s+=1
        t=1
        while(t*lista[i]<=lista[n-1]):
            listtf[lista[i]*t-1]=False
            t+=1
print(s)
# Original solution
N = int(eval(input()))
A = sorted(list(map(int, input().split()))) + [0]
 
memo = ['Y'] * (10**6+1)
count = 0
 
for i in range(N):
    if memo[A[i]] == 'N':
        continue
    for j in range(A[i], max(A)+1, A[i]):
        memo[j] = 'N'
    if A[i] == A[i+1]:
        continue
    
    count += 1
 
print(count)

# Optimized solution
N = int(eval(input()))
A = sorted(list(map(int, input().split()))) + [0]
 
memo = ['Y'] * (10**6+1)
mx = max(A) + 1 
count = 0
 
for i in range(N):
    if memo[A[i]] == 'N':
        continue
    for j in range(A[i], mx, A[i]):
        memo[j] = 'N'
    if A[i] == A[i+1]:
        continue
    
    count += 1
 
print(count)
# Original solution

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

alist.sort()
blist=alist
blist=list(set(alist))

for i in range(n-1):
    for j in range(i+1,n):
        if alist[j]%alist[i]==0:
            if alist[j] in blist:
                blist.remove(alist[j])
'''
ans=0
for i in range(len(blist)):
    if blist[i]>0:
        ans+=1

print(ans)
'''
print((len(blist)))

# Optimized solution

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


alist.sort()

hurui=[0]*(alist[-1]+1)

for i in range(n):
    for j in range(1,alist[-1]//alist[i]+1):
        hurui[alist[i]*j]+=1
ans=0
for i in range(n):
    if hurui[alist[i]]==1:
        ans+=1
print(ans)
# Original solution
#maspyさんを参考に
import sys
#import numpy as np
#from numba import njit
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# この最適化がよくわからん。Numpyループなら行けるらしい
# 400msくらいは最低でもかかるけど、N=10^5でも2でも変わらんと言う
#@njit('(i4[::1],)', cache=True)
def solve(A):
  # エラトステネス古いって値側のバリエーションとして配列をとるんや
  # maxA = 10**6って言うのがポイントっぽいなあ。。
    count = np.zeros(10**6 + 10, np.int32)
    for x in A:
        if count[x] > 1:
            continue
        count[::x] += 1
    ret = 0
    for x in A:
        ret += count[x] == 1
    return ret

def solve2(A):
  count = [0 for _ in range(10**6 + 10)]
  for x in A:
    if count[x] > 1:
      continue
    for a in range(0,len(count),x):
      count[a] += 1
  ret = 0
  for x in A:
    ret += (1 if count[x] == 1 else 0)
  #print(count[:24])
  return ret
  
# このコードわからなかった。一行目のNをSKIPしたリストになっている。。
#A = np.array(read().split(), np.int32)[1:]
N = int(eval(input()))
A = list(map(int, input().split()))
# この手法だとソート不要なのか？？だから早いのか？？
print((solve2(A)))


# Optimized solution
#maspyさんを参考に
import sys
#import numpy as np
#from numba import njit
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# この最適化がよくわからん。Numpyループなら行けるらしい
# 400msくらいは最低でもかかるけど、N=10^5でも2でも変わらんと言う
#@njit('(i4[::1],)', cache=True)
def solve(A):
  # エラトステネス古いって値側のバリエーションとして配列をとるんや
  # maxA = 10**6って言うのがポイントっぽいなあ。。
    count = np.zeros(10**6 + 10, np.int32)
    for x in A:
        if count[x] > 1:
            continue
        count[::x] += 1
    ret = 0
    for x in A:
        ret += count[x] == 1
    return ret

def solve2(A):
  count = [0 for _ in range(10**6 + 10)]
  for x in A:
    if count[x] > 1:
      continue
    for a in range(0,len(count),x):
      count[a] += 1
  ret = 0
  for x in A:
    ret += (1 if count[x] == 1 else 0)
  #print(count[:24])
  return ret
  
# このコードわからなかった。一行目のNをSKIPしたリストになっている。。
#A = np.array(read().split(), np.int32)[1:]
N = int(eval(input()))
A = list(map(int, input().split()))
# この手法だとソート不要なのか？？だから早いのか？？
print((solve2(sorted(A))))
# Original solution
#import numpy as np
import time

N = int(eval(input()))
A = list(map(int, input().split()))
A.sort()#わるほう
remove_list = []

kouho = sorted([x for x in set(A) if A.count(x) == 1])
#maxA = 10**5

#target = kouho[:]
if kouho != []:
    maxA = kouho[-1]

for i in range(len(A)):
    if kouho == []:
        break
    maxN = int(maxA/A[i])
    for n in range(2,maxN+1):
        buf = A[i]*n
        remove_list.append(buf)
            #print(A[i]*n)

#target = kouho[:]
kouho = list(set(kouho) - set(remove_list))

print((len(kouho)))

# Optimized solution
#import numpy as np

N = int(eval(input()))
A = list(map(int, input().split()))
A.sort()#わるほう

#kouho = sorted([x for x in set(A) if A.count(x) == 1])
#maxA = 10**5

#target = kouho[:]
maxA = A[-1]
work=[0]*(A[-1]+1)

for i in range(len(A)):
    if work[A[i]]<=1:
        maxN = int(maxA/A[i])
        for n in range(1,maxN+1):
            buf = A[i]*n
            #remove_list.append(buf)
            work[buf]+=1
                #print(A[i]*n)

#target = kouho[:]
#kouho = list(set(kouho) - set(remove_list))

sm=0
for s in A:
    if work[s]==1: sm+=1
print(sm)

#print(len(kouho))
# Original solution
#import numpy as np

N = int(eval(input()))
A = list(map(int, input().split()))
A.sort()#わるほう

#kouho = sorted([x for x in set(A) if A.count(x) == 1])
#maxA = 10**5

#target = kouho[:]
maxA = A[-1]
work=[0]*(A[-1]+1)

for i in range(len(A)):
    if work[A[i]]<=1:
        maxN = int(maxA/A[i])
        for n in range(1,maxN+1):
            buf = A[i]*n
            #remove_list.append(buf)
            work[buf]+=1
                #print(A[i]*n)

#target = kouho[:]
#kouho = list(set(kouho) - set(remove_list))

sm=0
for s in A:
    if work[s]==1: sm+=1
print(sm)

#print(len(kouho))

# Optimized solution
#import numpy as np

N = int(eval(input()))
A = list(map(int, input().split()))
A.sort()#わるほう

#kouho = sorted([x for x in set(A) if A.count(x) == 1])
#maxA = 10**5

#target = kouho[:]
maxA = A[-1]
work=[0]*(A[-1]+1)

for i in range(len(A)):
    maxN = int(maxA/A[i])
    for n in range(1,maxN+1):
        buf = A[i]*n
        #remove_list.append(buf)
        work[buf]+=1
            #print(A[i]*n)
#target = kouho[:]
#kouho = list(set(kouho) - set(remove_list))

sm=0
for s in A:
    if work[s]==1: sm+=1
print(sm)

#print(len(kouho))
# Original solution
from collections import Counter
N=list(map(int,input().split()))
A=list(map(int,input().split()))

counter = Counter(A)

A=list(set(A))
A.sort()

check=A.copy()
search=[]

while True:
    if len(check)<=0:
        break
    
    c = check.pop(0)
    search.append(c)

    check = [ _ for _ in check if (_%c !=0)or(_ < c**(1/2)) ]

ans=[s for s in search if counter[s]==1]
print((len(ans)))

# Optimized solution
# %%time
# from collections import Counter

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

# A=list(range(2,10**6))

# counter = Counter(A)

A.sort()
max=A[-1]
dp=[0]*(max+1)

for i in A:
    if dp[i]!=0:
        dp[i]+=1
        continue
    for j in range(1*i,max+1,i):
        dp[j]+=1
        
ans=[]
for a_idx,a in enumerate(A):
    if dp[a] == 1:
        ans.append(a)
        
print((len(ans)))
# Original solution
n = int(eval(input()))

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

a.sort()

dp = [True] * (a[-1] + 1)

ans = 0

m = a[-1]

for i, x in enumerate(a[:-1]):
    if not a[i+1] == x and dp[x]:
        ans += 1
    for b in range(x, m + 1, x):
        dp[b] = False

if dp[a[-1]]:
    ans += 1

print(ans)

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

a.sort()

max_a = a[-1]
is_available = [True] * (max_a + 1)

ans = 0

for i, x in enumerate(a[:-1]):
    if not a[i+1] == x and is_available[x]:
        ans += 1
    for b in range(x, max_a + 1, x):
        is_available[b] = False

if is_available[a[-1]]:
    ans += 1

print(ans)
# Original solution
n = int(eval(input()))
a = list(map(int, input().split()))

dp = [0]*(10**6)
count = [0]*(10**6)
for i in a:
  count[i-1] += 1
  for j in range(i*2, 10**6+1, i):
    dp[j-1] = 1
    
ans = 0
for i in a:
  if count[i-1] == 1 and dp[i-1] == 0:
    ans +=1
    
print(ans)

# Optimized solution
n = int(eval(input()))
a = list(map(int, input().split()))
 
dp = [0]*(10**6)
count = [0]*(10**6)

for i in a:
  count[i-1] += 1
 
b = list(set(a))
for i in b:
  for j in range(i*2, 10**6+1, i):
    dp[j-1] = 1
    
ans = 0
for i in a:
  if count[i-1] == 1 and dp[i-1] == 0:
    ans +=1
    
print(ans)
# Original solution
import io,sys
sys.setrecursionlimit(10**6)

def main():
    import bisect
    n = int(eval(input()))
    A = list(map(int,sys.stdin.readline().rstrip().split()))
    A.sort()

    ans = 0
    a_max = A[-1]
    note = [True]*(a_max+1)
    for j in range(n):
        a = A[j]
        if note[a]:
            if j != n-1 and A[j]==A[j+1]:
                ans-=1
            ans+=1
            # for i in range(a,a_max+1):
            #     if i%a==0:
            #         note[i] = False
            temp = a 
            while temp <= a_max:
                note[temp]=False
                temp+=a

        
    
    print(ans)
main()

# Optimized solution
def main():
    n = int(eval(input()))
    A = list(map(int,input().split()))
    A.sort()
    A_max = A[-1]
    g = []
    table = [True]*(A_max+1)
    for i,a in enumerate(A):
        if table[a]:
            temp = a
            while A_max >= temp:
                table[temp] = False
                temp+=a
            if i==n-1 or a!=A[i+1]:
                g.append(a)
    print((len(g)))
main()
# Original solution
from collections import Counter
import math


def factors(n):
    fhead = []
    ftail = []
    for x in range(1, int(math.sqrt(n)) + 1):
        if n % x == 0:
            fhead.append(x)
            if x * x != n:
                # This check is to not insert sqrt(n) twice in head and tail portion of the list
                ftail.append(n // x)
    return fhead + ftail[::-1]


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

freq = Counter(A)
count = 0
for x in A:
    bad = False
    for d in factors(x):
        if (d == x and freq[d] >= 2) or (d != x and freq[d]):
            bad = True
            break

    if not bad:
        count += 1
print(count)


# Optimized solution
from collections import Counter
(N,) = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

freq = Counter(A)
if freq[1] == 1:
    print((1))
elif freq[1] >= 2:
    print((0))
else:
    bad = set()
    for k, v in list(freq.items()):
        if v >= 2:
            bad.add(k)

    mx = max(A)

    for x in list(freq.keys()):
        for times in range(2, 10 ** 6 + 1):
            if x * times > mx:
                break
            if x * times in freq:
                bad.add(x * times)

    count = 0
    for x in A:
        if x not in bad:
            count += 1
    print(count)
# Original solution
N = int(eval(input()))
A = list(map(int, input().split()))
A.sort()
b = [False] * len(A)

for i in range(N):
  for j in range(N):
    if b[j] or i == j or A[i] > 500000:
      continue
    if A[j] % A[i] == 0:
      b[j] = True

# print(b)

print((len(tuple([x for x in b if x == False]))))


# Optimized solution
N = int(eval(input()))
A = list(map(int, input().split()))
A.sort()
M = A[-1]
b = [True] * (M + 1)

count = 0
for i, a in enumerate(A):
  if not b[a]:
    continue
  for j in range(a, M+1, a):
    b[j] = False
  if i < N-1 and A[i+1] == a:
    continue
  count += 1

print(count)
# Original solution
n=int(eval(input()))
a=list(map(int,input().split()))


cnt=0
for i in range(n):
    flg=0
    for j in range(n):
        if i==j:
            continue

        if a[i]%a[j]==0:
            flg+=1

    if flg==0:
        cnt+=1

print(cnt)

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

a=sorted(a)
m=max(a)
dp=[0]*(m+1)
d={}
cnt=0
for i in range(n):
    b=a[i]
    if b in d:
        d[b]+=1
        continue
    else:
        d[b]=1
    j=b
    while b<=m+b:
        if b>m:
            break
        dp[b]+=1
        b+=j
        


for i in a:
    if dp[i]==1 and d[i]==1:
        cnt+=1

print(cnt)