CodeEff/ECCO huggingface dataset:
# Original solution
n = int(eval(input()))
a = list(map(int, input().split()))

m = 10 ** 6 + 7

count = [0] * m

for x in a:
    if count[x] != 0:
        count[x] = 2
        continue

    for i in range(x, m, x):
        count[i] += 1

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

print(ans)

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

m = max(a) + 1
a = sorted(a)

count = [0] * m

for x in a:
    if count[x] != 0:
        count[x] = 2
        continue

    for i in range(x, m, x):
        count[i] += 1

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

print(ans)
# Original solution
# ANSHUL GAUTAM
# IIIT-D

from math import *
from copy import *					# ll = deepcopy(l)
from heapq import *					# heappush(hp,x)
from string import *				# alpha = ascii_lowercase
from random import *				# l.sort(key=lambda l1:l1[0]-l1[1]) => ex: sort on the basis difference
from bisect import *				# bisect_left(arr,x,start,end)  => start and end parameters are temporary
from sys import stdin				# bisect_left return leftmost position where x should be inserted to keep sorted
from sys import maxsize				# minn = -maxsize
from operator import *				# d = sorted(d.items(), key=itemgetter(1))
from itertools import *				# pre = [0] + list(accumulate(l))
from decimal import Decimal 		# a = Decimal(a)	# use this for math questions
from collections import Counter		# d = dict(Counter(l))
from collections import defaultdict # d = defaultdict(list)

'''
5
24 11 8 3 16
'''

def solve(l):
	n = len(l)
	l.sort()
	maxx,ans = max(l),0
	cancel,p = [0]*(maxx+1),[0]*(maxx+1)
	for i in l:
		p[i] += 1
	for i in l:
		for j in range(2*i,maxx+1,i):
			cancel[j] = 1
	for i in l:
		if(p[i] == 1 and not cancel[i]):
			ans += 1
	return ans

N = int(stdin.readline())
l = list(map(int, stdin.readline().rstrip().split()))
ans = solve(l)
print(ans)



# Optimized solution
# ANSHUL GAUTAM
# IIIT-D

from math import *
from copy import *					# ll = deepcopy(l)
from heapq import *					# heappush(hp,x)
from string import *				# alpha = ascii_lowercase
from random import *				# l.sort(key=lambda l1:l1[0]-l1[1]) => ex: sort on the basis difference
from bisect import *				# bisect_left(arr,x,start,end)  => start and end parameters are temporary
from sys import stdin				# bisect_left return leftmost position where x should be inserted to keep sorted
from sys import maxsize				# minn = -maxsize
from operator import *				# d = sorted(d.items(), key=itemgetter(1))
from itertools import *				# pre = [0] + list(accumulate(l))
from decimal import Decimal 		# a = Decimal(a)	# use this for math questions
from collections import Counter		# d = dict(Counter(l))
from collections import defaultdict # d = defaultdict(list)

'''
5
24 11 8 3 16
'''

def solve(l):
	n = len(l)
	ans,maxx = 0,max(l)
	done = [0]*(maxx+1)
	l.sort()
	ans = 0
	d = dict(Counter(l))
	for i in l:
		zz = 2
		while(i*zz <= maxx):
			done[i*zz] = 1
			zz += 1
	for i in l:
		if(not done[i] and d[i] == 1):
			ans += 1
	return ans

N = int(stdin.readline())
l = list(map(int, stdin.readline().rstrip().split()))
ans = solve(l)
print(ans)
# Original solution

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

MAX = 10 ** 6 + 1
prime = [True] * MAX
counted = set()
for v in X:
    if v in counted:
        prime[v] = False
    for j in range(2 * v, MAX, v):
        prime[j] = False
    counted.add(v)

ans = 0
for v in X:
    ans += int(prime[v])
print(ans)


# Optimized solution

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

MAX = 10 ** 6 + 1
prime = [True] * MAX
counted = set()
for v in X:
    if v in counted:
        prime[v] = False
        continue
    for j in range(2 * v, MAX, v):
        prime[j] = False
    counted.add(v)

ans = 0
for v in X:
    ans += int(prime[v])
print(ans)
# Original solution

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

MAX = 10 ** 6 + 1
prime = [True] * MAX
counted = set()
for v in X:
    if v in counted:
        prime[v] = False
        continue
    for j in range(2 * v, MAX, v):
        prime[j] = False
    counted.add(v)

ans = 0
for v in X:
    ans += int(prime[v])
print(ans)


# Optimized solution

from collections import Counter

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


lim = 10 ** 6 + 10
ok = [True] * (lim + 1)
ans = 0
ctr = Counter(X)
for n in sorted(X):
    if ok[n]:
        if ctr[n] == 1:
            ans += 1
        for j in range(n, lim + 1, n):
            ok[j] = False

print(ans)
# Original solution
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
 
mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000
 
d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))
 

"""
3
1 1 2
のパターンが例外だった
"""

N = int(eval(input()))
A = LI()
A.sort()

table = [0 for i in range(10 ** 6 + 1)]
cnt = 0

cc = collections.Counter(A)
duplicate = []
for key in list(cc.keys()):
    if cc[key] > 1:
        duplicate.append(key)

for a in A:
    if table[a] != 0:
        pass
    else:
        if a not in duplicate:
            cnt += 1
        for i in range(1, 10 ** 6 + 1):
            if a * i > 10 ** 6:
                break
            table[a * i] = 1

print(cnt)


# Optimized solution
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N = int(eval(input()))
A = LI()

A.sort()
table = [0 for i in range(10**6 + 1)] # 約数のテーブル

cc = collections.Counter(A)


cnt = 0
for a in A:
    if table[a] == 0:
        for i in range(10 ** 6):
            if a * i > 10 ** 6:
                break
            table[a * i] = 1
        if cc[a] == 1:
            cnt += 1


print(cnt)
# Original solution
from collections import Counter
n = int(eval(input()))
A = sorted(list(map(int, input().split())))
c = Counter(A)
result = 0
piyo = []
for k, v in list(c.items()):
    if v > 1:
        piyo.append(k)
        A.remove(k)
for a in A:
    flag = False
    for hoge in piyo:
        if a % hoge == 0:
            flag = True
            break
    if not flag:
        piyo.append(a)
        result += 1
print(result)

# Optimized solution
def main():
    from collections import Counter
    n = int(eval(input()))
    A = sorted(list(map(int, input().split())))
    c = Counter(A)
    result = 0
    flag = [True] * (A[-1] + 1)
    for i in A:
        if flag[i]:
            result += 1
            for j in range(2*i, A[-1] + 1, i):
                flag[j] = False
    for k, v in list(c.items()):
        if v > 1:
            if flag[k]:
                result -= v
    print(result)
main()
# Original solution
# coding: utf-8


def yakusu(n):
    ans = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            ans.append(i)
            if n // i != i:
                ans.append(n // i)

    return sorted(ans)


def main():
    N = int(eval(input()))

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

    # is_in_A_flag = [0] * (10**6+1)
    is_in_A_flag = {f"{i}": 0 for i in range(10**6+1)}

    for a in A:
        is_in_A_flag[f"{a}"] += 1

    B = [None] * N
    for i in range(N):
        B[i] = yakusu(A[i])

    ans = 0
    for i in range(N):
        is_ans = True
        # for b in B[i][:-1]:
        for j in range(len(B[i])-1):
            b = B[i][j]
            if is_in_A_flag[f"{b}"] > 0:
                is_ans = False
                break

        if is_ans:
            if is_in_A_flag[f"{B[i][-1]}"] > 1:
                is_ans = False

        if is_ans:
            ans += 1

    return ans


print((main()))


# Optimized solution
# coding: utf-8

# 13:42- kaisetsu and try again
# -14:03 giveup (WA*6) -> testcase


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

    M = 10**6
    is_ans_flag = [0] * (M+1)
    n_appeared_in_A = [0] * (M+1)
    for a in A:
        n_appeared_in_A[a] += 1
        is_ans_flag[a] = 1

    for a in A:
        if n_appeared_in_A[a] == -1:
            continue

        if n_appeared_in_A[a] >= 2:
            is_ans_flag[a] = 0

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

        n_appeared_in_A[a] = -1

    return sum(is_ans_flag)


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

cnt = [0] * ((10**6) + 1)
ans = 0

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

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

print(ans)

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

a_max = max(a)
cnt = [0] * (max(a) + 1)
ans = 0

for ai in a:
    for multi in range(ai, a_max + 1, ai):
        cnt[multi] += 1

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

print(ans)
# Original solution
n=int(eval(input()))
import math
a=list(map(int,input().split()))
d=dict()
for i in range(n):
    if d.get(a[i],None)==None:
        d[a[i]]=0
    d[a[i]]+=1 
ans=0
s=list(d.keys())
for i in range(n):
    if d[a[i]]>1:
        continue 
    flag=True
    # print(a[i],end='    s\n')
    for ii in range(1,math.ceil(a[i]**(1/2))+1):
        if (a[i]%ii)==0:
            aa,bb=ii,a[i]//ii
            if aa!=a[i] and aa in s:
                # print(aa)
                # print('aa')
                flag=False
                break
            if bb!=a[i] and bb in s:
                # print('bb')
                # print(bb)
                flag=False
                break
    if(flag):
        # print(a[i])
        ans+=1
print(ans)
        
    

# Optimized solution
n=int(eval(input()))
a=list(map(int,input().split()))
m=max(a)
dp=[0 for i in range(m+1)]
ans=0
for i in range(n):
    if dp[a[i]]>=1:
        dp[a[i]]+=1
        continue
    for j in range(2*a[i],m+1,a[i]):
        dp[j]+=1 
    dp[a[i]]=1
for i in range(n):
    if dp[a[i]]==1:
        ans+=1 
print(ans)
# Original solution
from sys import stdin

def main():

    n = int(stdin.readline().strip())
    a = list(map(int, stdin.readline().strip().split()))

    if n == 1:
        print((1))
        exit()

    a.sort()

    # bにチェックする数を追加していく
    b = []
    ans = 0

    for i in range(n):

        if a[i] == a[i-1]:
            continue

        flag = True
        for j in b:
            if a[i] % j == 0:
                flag = False
                break

        if flag:
            b.append(a[i])
            if i == n-1 or a[i] != a[i+1]:
                ans += 1

    print(ans)

main()


# Optimized solution
from sys import stdin

def main():

    n = int(stdin.readline().strip())
    a = list(map(int, stdin.readline().strip().split()))

    if n == 1:
        print((1))
        exit()

    a.sort()

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

    for i in range(n):

        if a[i] == a[i-1]:
            continue

        if dp[a[i]]:

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

            if i == n-1 or a[i] != a[i+1]:
                ans += 1

    print(ans)

main()
# Original solution
n = int(eval(input()))
An = list(map(int, input().split()))

An.sort()

idx = 0

while True:
    if idx == len(An):
        ans = len(An) - An.count(0)
        print(ans)
        exit()

    flg = False
    if An[idx] != 0:
        for i in range(idx + 1, len(An)):
            if An[i] != 0 and An[i] % An[idx] == 0:
                if An[i] == An[idx]:
                    flg = True
                An[i] = 0
        if flg:
            An[idx] = 0

    idx += 1

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

An.sort()
max_num = An[-1]

primes = [True] * max_num
once = [False] * max_num

i = 0
while i < n:
    once[An[i] - 1] = True

    j = 1
    while i + j < n:
        if An[i] == An[i + j]:
            once[An[i] - 1] = False
            j += 1
        else:
            break

    i += j

for i in range(n):
    if primes[An[i] - 1]:
        base = An[i]
        idx = An[i] * 2 - 1
        while idx < max_num:
            primes[idx] = False
            idx += base

ans = [x and y for (x, y) in zip(once, primes)]
print((ans.count(True)))
# Original solution
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
def main():
    n, *a = list(map(int, read().split()))
    a.sort()
    a = tuple(a)
    TorF = [0] * (a[-1] + 1)
    for ae in a:
        TorF[ae] = 1
    for i1 in range(n - 1):
        if TorF[a[i1]]:
            t = a[i1] * 2
            while t <= max(a):
                TorF[t] = 0
                t += a[i1]
        if a[i1 + 1] == a[i1]:
            TorF[a[i1]] = 0
    r = sum(TorF)
    print(r)

if __name__ == '__main__':
    main()

# Optimized solution
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
def main():
    n, *a = list(map(int, read().split()))
    a.sort()
    a = tuple(a)
    TorF = [0] * (a[-1] + 1)
    for ae in a:
        TorF[ae] = 1
    for i1 in range(n - 1):
        a1 = a[i1]
        if TorF[a1]:
            m = a[-1] // a1 + 1
            for i2 in range(2, m):
                TorF[a1 * i2] = 0
        if a[i1 + 1] == a[i1]:
            TorF[a[i1]] = 0
    r = sum(TorF)
    print(r)

if __name__ == '__main__':
    main()
# Original solution
N = int(eval(input()))
A = list(map(int, input().split()))

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])
print(ans)


# Optimized solution
from collections import Counter
N = int(eval(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)
# Original solution
from collections import Counter
N = int(eval(input()))
A = sorted(map(int, input().split()), reverse=False)
m = max(A)+1
dp = [True] * m
for x in list(set(A)):
    t = x * 2
    while t < m:
        dp[t] = False
        t += x
ans = 0
for a in A:
    if Counter(A)[a] == 1 and dp[a]:
        ans += 1
print(ans)



# Optimized solution
from collections import Counter
N = int(eval(input()))
A = sorted(map(int, input().split()), reverse=False)
m = max(A)+1
c = Counter(A)
s = list(set(A))
dp = [True] * m
for x in s:
    t = x * 2
    while t < m:
        dp[t] = False
        t += x
ans = 0
for a in A:
    if c[a] == 1 and dp[a]:
        ans += 1
print(ans)
# Original solution
from collections import Counter
N = int(eval(input()))
A = sorted(map(int, input().split()), reverse=False)
m = max(A)+1
s = list(set(A))
dp = [True] * m
for x in s:
    t = x * 2
    while t < m:
        dp[t] = False
        t += x
ans = 0
for a in A:
    if Counter(A)[a] == 1 and dp[a]:
        ans += 1
print(ans)



# Optimized solution
from collections import Counter
N = int(eval(input()))
A = sorted(map(int, input().split()), reverse=False)
m = max(A)+1
c = Counter(A)
s = list(set(A))
dp = [True] * m
for x in list(set(A)):
    t = x * 2
    while t < m:
        dp[t] = False
        t += x
ans = 0
for a in A:
    if c[a] == 1 and dp[a]:
        ans += 1
print(ans)
# Original solution
from bisect import bisect_left, bisect_right

n = int(eval(input()))
a = list(map(int, input().split()))
a.sort()
m = a[-1]
c = [0] * (m + 1)

for ai in a:
    for i in range(ai, m + 1, ai):
        if bisect_right(a, i) - bisect_left(a, i) == 1:
            c[i] += 1

print((c.count(1)))

# Optimized solution
n = int(eval(input()))
a = list(map(int, input().split()))
a.sort()
m = a[-1]
c = [0] * (m + 1)

for ai in a:
    for i in range(ai, m + 1, ai):
        c[i] += 1

ans = 0
for ai in a:
    if c[ai] == 1:
        ans += c[ai]

print(ans)
# Original solution
from collections import defaultdict

def resolve():
	N = int(eval(input()))
	A = list(map(int, input().split()))
	a_max = max(A)+1
	B = defaultdict(int)
	for i in range(N):
		a = A[i]
		if B[a]>1:
			B[a] = 2
		else:
			for j in range(a, a_max, a):
				B[j] += 1
	Y = 0
	for a in A:
		if B[a]==1:
			Y+=1
	print(Y)
resolve()

# Optimized solution
def resolve():
	N = int(eval(input()))
	A = list(map(int, input().split()))
	a_max = max(A)+1
	B = {}
	for i in range(N):
		a = A[i]
		if a not in list(B.keys()):
			for j in range(a, a_max, a):
				B[j] = False
			B[a] = True
		else:
			B[a] = False
	Y = list(B.values()).count(True)
	print(Y)
resolve()
# Original solution
n = int(eval(input()))
a = [int(i) for i in input().split()]
table = [True for _ in range(10 ** 7)]
a.sort()
ans = 0
for i in range(n):
    if table[a[i]]:
        for j in range(a[i], 10 ** 7, a[i]):
            table[j] = False
        if i + 1 < n:
            if a[i + 1] != a[i]:
                ans += 1
        elif i + 1 == n:
            ans += 1
print(ans)


# Optimized solution
n = int(eval(input()))
a = [int(i) for i in input().split()]
table = [True for _ in range(2 * (10 ** 6))]
a.sort()
ans = 0
for i in range(n):
    if table[a[i]]:
        for j in range(a[i], 2 * (10 ** 6), a[i]):
            table[j] = False
        if i + 1 < n:
            if a[i + 1] != a[i]:
                ans += 1
        elif i + 1 == n:
            ans += 1
print(ans)
# Original solution
n = int(eval(input()))
a = [int(i) for i in input().split()]
table = [True for _ in range(2 * (10 ** 6))]
a.sort()
ans = 0
for i in range(n):
    if table[a[i]]:
        for j in range(a[i], 2 * (10 ** 6), a[i]):
            table[j] = False
        if i + 1 < n:
            if a[i + 1] != a[i]:
                ans += 1
        elif i + 1 == n:
            ans += 1
print(ans)

# Optimized solution
T = 10 ** 6 + 20
n = int(eval(input()))
a = [int(i) for i in input().split()]
table = [True for _ in range(T)]
a.sort()
ans = 0
for i in range(n):
    if table[a[i]]:
        for j in range(a[i], T, a[i]):
            table[j] = False
        if i + 1 < n:
            if a[i + 1] != a[i]:
                ans += 1
        elif i + 1 == n:
            ans += 1
print(ans)
# Original solution
n = int(eval(input()))
l = [int(x) for x in input().split()]
l.sort()
set_l = set(l)
set_l = sorted(set_l)
limit = 10**6
mp = [0]*(limit+1)
pre = None
for i in range(n):
    num = l[i]
    if(pre==num):
        mp[num] += 1
    pre = num

for x in set_l:
    num = x
    while(x <= limit):
        mp[x] += 1
        x += num

cnt = 0
for num in set_l:
    if(mp[num]==1):
        cnt += 1
print(cnt)





# Optimized solution
n = int(eval(input()))
l = [int(x) for x in input().split()]
l.sort()
set_l = set(l)
set_l = sorted(set_l)
limit = 10**6+1
mp = [0]*(limit)
pre = None
for i in range(n):
    num = l[i]
    if(pre==num):
        mp[num] += 1
    pre = num

for x in set_l:
    for y in range(x,limit,x):
        mp[y] += 1
        

cnt = 0
for num in set_l:
    if(mp[num]==1):
        cnt += 1
print(cnt)
# Original solution
n = int(eval(input()))
l = [int(x) for x in input().split()]
l.sort()
set_l = set(l)
set_l = sorted(set_l)
limit = 10**6+1
mp = [0]*(limit)
pre = None
for i in range(n):
    num = l[i]
    if(pre==num):
        mp[num] += 1
    pre = num

for x in set_l:
    for y in range(x,limit,x):
        mp[y] += 1
        

cnt = 0
for num in set_l:
    if(mp[num]==1):
        cnt += 1
print(cnt)





# Optimized solution
n = int(eval(input()))
l = [int(x) for x in input().split()]
D = set() #Duplication
S = set() #all
for x in l:
    if x in S:
        D.add(x)
    else:
        S.add(x)

limit = 10**6+1
mp = [0]*(limit)

cnt = 0
S = sorted(S)
for x in S:
    for y in range(x,limit,x):
        mp[y] += 1
    if(x in D):
        continue
    if(mp[x]==1):
        cnt += 1
        
print(cnt)
# Original solution
n = int(eval(input()))
l = [int(x) for x in input().split()]
D = set() #Duplication
S = set() #all
for x in l:
    if x in S:
        D.add(x)
    else:
        S.add(x)

limit = 10**6+1
mp = [0]*(limit)

cnt = 0
S = sorted(S)
for x in S:
    for y in range(x,limit,x):
        mp[y] += 1
    if(x in D):
        continue
    if(mp[x]==1):
        cnt += 1
        
print(cnt)





# Optimized solution
n = int(eval(input()))
l = [int(x) for x in input().split()]
D = set() #Duplication
S = set() #all
for x in l:
    if x in S:
        D.add(x)
    else:
        S.add(x)

M = max(S)
limit = M+1
mp = [0]*(limit)

cnt = 0
S = sorted(S)
for x in S:
    for y in range(x,limit,x):
        mp[y] += 1
    if(x in D):
        continue
    if(mp[x]==1):
        cnt += 1
        
print(cnt)
# Original solution
from collections import Counter

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

is_p=[1 for i in range(10**6+1)]

for i in range(n):
  v=a[i]
  if is_p[v]:
    for j in range(v+v,10**6+1,v):
#      print(j)
      is_p[j]=0

c=Counter(a)

cnt=0
for i in a:
  if is_p[i]==1 and c[i]==1:
    cnt+=1

print(cnt)

# Optimized solution
from collections import Counter

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

is_p=[1 for i in range(10**6+1)]

for i in set(a):
  v=i
  if is_p[v]:
    for j in range(v+v,10**6+1,v):
      is_p[j]=0

c=Counter(a)

cnt=0
for i in a:
  if is_p[i]==1 and c[i]==1:
    cnt+=1

print(cnt)
# Original solution
from collections import Counter

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

is_p=[1]*(10**6+1)
for i in a:
  if is_p[i]:
    for j in range(i+i,10**6+1,i):
      is_p[j]=0

c=Counter(a)

cnt=0
for i in a:
  if is_p[i] and c[i]==1:
    cnt+=1

print(cnt)

# Optimized solution
from collections import Counter

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

is_p=[1]*(10**6+1)
for i in set(a):
  if is_p[i]:
    for j in range(i+i,10**6+1,i):
      is_p[j]=0

c=Counter(a)

cnt=0
for i in a:
  if is_p[i] and c[i]==1:
    cnt+=1

print(cnt)
# Original solution
from collections import Counter

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

c=Counter(a)

def eratosthenes(lim):
  is_p=[1]*lim
  is_p[0]=1
  is_p[1]=1

  for i in a:
    if is_p[i]:
      for j in range(i*2,lim,i):
        is_p[j]=0

  return is_p

lim=10**6+5
is_p=eratosthenes(lim)

cnt=0
for i in a:
  if is_p[i]==1 and c[i]==1:
    cnt+=1

print(cnt)

# Optimized solution
from collections import Counter

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

c=Counter(a)

def eratosthenes(lim):
  is_p=[1]*lim
  is_p[0]=1
  is_p[1]=1

  for i in set(a):
    if is_p[i]:
      for j in range(i*2,lim,i):
        is_p[j]=0

  return is_p

lim=10**6+5
is_p=eratosthenes(lim)

cnt=0
for i in a:
  if is_p[i]==1 and c[i]==1:
    cnt+=1

print(cnt)
# Original solution
from sys import stdin
nii=lambda:list(map(int,stdin.readline().split()))
lnii=lambda:list(map(int,stdin.readline().split()))
from collections import Counter

n=int(eval(input()))
l=lnii()

def eratosthenes(lim):
  num=[1 for i in range(lim)]
  for i in l:
    for j in range(i+i,lim,i):
      num[j]=0
  return num

lim=10**6+5
num=eratosthenes(lim)

count=Counter(l)

ans=0
for i in l:
  if num[i]==1 and count[i]==1:
    ans+=1

print(ans)

# Optimized solution
from sys import stdin
nii=lambda:list(map(int,stdin.readline().split()))
lnii=lambda:list(map(int,stdin.readline().split()))
from collections import Counter

n=int(eval(input()))
l=lnii()

def eratosthenes(lim):
  num=[1 for i in range(lim)]
  for i in set(l):
    for j in range(i+i,lim,i):
      num[j]=0
  return num

lim=10**6+5
num=eratosthenes(lim)

count=Counter(l)

ans=0
for i in l:
  if num[i]==1 and count[i]==1:
    ans+=1

print(ans)