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

for i in range(n):
    for j in range(n):
        if (i != j) and (a[i] % a[j] == 0):
            break
    else:
        dp[i] = True

print((dp.count(True)))

# Optimized solution
n = int(eval(input()))
*a, = sorted(map(int, input().split()))
a_max = a[n-1]
dp = [True] * a_max
ans = 0
recent = 0

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

for i in a:
    if recent == i:
        ans -= 1
        recent = 0
    if dp[i-1] == False:
        continue
    else:
        for j in range(i, a_max+1, i):
            dp[j-1] = False
        ans += 1
        recent = i

print(ans)
# Original solution
sieve=[0]*1000009
n=int(eval(input()))
s=sorted(map(int,input().split()))
for i in s:
    for j in range(i,1000009,i):sieve[j]+=1
print((sum(sieve[i]==1for i in s)))

# Optimized solution
sieve=[0]*1000009
n=int(eval(input()))
s=sorted(map(int,input().split()))
for i in s:
    if sieve[i]<2:
        for j in range(i,1000009,i):sieve[j]+=1
print((sum(sieve[i]==1for i in s)))
# Original 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)

# Optimized solution
from collections import Counter
N = int(eval(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)
# Original solution
n = int(eval(input()))
a = sorted([int(i) for i in input().split()])
set_a = set(a)
max_a = max(a)
dup_a = {ai for ai in set_a if a.count(ai) > 1}
nd = [True] * (max_a + 1)
cnt = 0
for ai in sorted(list(set_a)):
    if nd[ai] == True and ai not in dup_a:
        cnt += 1
    elif nd[ai] == False:
        continue
    multi = 2
    while ai*multi <= max_a:
        nd[ai*multi] = False
        multi += 1
print(cnt)

# Optimized solution
n = int(eval(input()))
a = sorted([int(i) for i in input().split()])
max_a = max(a)
cnt_d = [0] * (max_a + 1)

for ai in a:
    for multi in range(ai, max_a + 1, ai):
        cnt_d[multi] += 1

cnt_nd = 0
for ai in a:
    if cnt_d[ai] == 1:
        cnt_nd += 1
print(cnt_nd)
# Original solution
n = int(eval(input()))
a = sorted([int(i) for i in input().split()])
max_a = max(a)
cnt_d = [0] * (max_a + 1)

for ai in a:
    for multi in range(ai, max_a + 1, ai):
        cnt_d[multi] += 1

print((sum(cnt_d[ai] == 1 for ai in a)))

# Optimized solution
n = int(eval(input()))
a = [int(i) for i in input().split()]
max_a = max(a)
cnt_d = [0] * (max_a + 1)

for ai in a:
    for multi in range(ai, max_a + 1, ai):
        cnt_d[multi] += 1

print((sum(cnt_d[ai] == 1 for ai in a)))
# Original solution
# D - Not Divisible
N = int(eval(input())) # 【1行】1数字
num_list = list(map(int, input().split())) 
ind_list = [1 for _ in range(N)]
num_list.sort()
for i in range(N-1):
    if num_list[i+1] == num_list[i]:
        ind_list[i] = -1
        continue
    for j in range(i):
        if num_list[i] % num_list[j] == 0 :
            ind_list[i] = -1
            break
for i in range(N-1):
    if num_list[N-1] % num_list[i] == 0 :
        ind_list[N-1] = -1
        break
print((ind_list.count(1)))

# Optimized solution
# D - Not Divisible
N = int(eval(input()))
a = list(map(int, input().split()))
a.sort()
MAX = a[-1]
l = [0]*(MAX+1)
for i in range(N):
    l[a[i]] += 1
    
answer = 0
for i in range(N):
    if l[a[i]] == 1:
        answer += 1
    for g in range(a[i], MAX+1, a[i]):
        l[g] = 10
print(answer)
# Original solution
N = int(eval(input()))
A = list(map(int,input().split()))
ans = 0
import heapq
heapq.heapify(A)
while A != []:
    a = heapq.heappop(A)
    ans += 1
    AA = []
    if a in A:
        ans -= 1
    for i in range(len(A)):
        if not (A[i] % a == 0):
            AA.append(A[i])
    A = AA
print(ans)

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

s = A[-1]
p = [0 for _ in range(s+1)]
for i in A:
    p[i] += 1
    if p[i] > 1:
        continue
    for j in range(i*2,s+1,i):
        p[j] += 1
ans = 0
for i in A:
    if p[i] == 1:
        ans += 1
print(ans)
# Original solution
from collections import Counter

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

# サイズA_maxのbool配列dpを用意し、trueで初期化する
A_max = max(A)
dp = [True] * (A_max + 1)

# 数列の要素を昇順に見る O(nloglogn)
for x in range(A_max):
    # すでに計算していれば再度計算しない
    if not dp[x]:
        continue
    # xが数列Aに含まれているとき、xより大きいxの倍数yについて、dp[y]をfalseに変更する
    if x in A:
        t = 2
        while x * t <= A_max:
            dp[x * t] = False
            t += 1

# 同じ値が複数存在するかチェックする用のカウンタ
C = {a: 0 for a in A}
for a in A:
    C[a] += 1

ans = 0
for a in A:
    if C[a] == 1 and dp[a] is True:
        ans += 1

print(ans)


# Optimized solution
from collections import Counter

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

# 同じ値が複数存在するかチェックする用のカウンタ
counter = Counter(A)

# D[a] = True: Aにaより小さいaの約数が存在する
A_max = max(A)
dp = {a: False for a in A}

for a in A:
    # xが数列Aに含まれているとき、aより大きいaの倍数tについて、dp[a * t]をTrueに変更する
    if counter[a] > 0:
        t = 2
        while a * t <= A_max:
            dp[a * t] = True
            t += 1

ans = 0
for a in A:
    if counter[a] == 1 and dp[a] is False:
        ans += 1

print(ans)
# Original solution
N=int(eval(input()))
A=list(map(int,input().split()))
B=set(A)
A.sort()
ans=[1]*max(A)
for i in range(len(A)):
  if ans[A[i]-1]!=0:
    if i>0 and A[i]==A[i-1]:
      ans[A[i]-1]=0
    for j in range(A[i]*2,max(A)+1,A[i]):
      ans[j-1]=0
k=0
for i in A:
  if ans[i-1]==1:
    k+=1
print(k)

# Optimized solution
N=int(eval(input()))
A=list(map(int,input().split()))
B=set(A)
A.sort()
S=max(A)
ans=[1]*S
for i in range(len(A)):
  if ans[A[i]-1]!=0:
    if i>0 and A[i]==A[i-1]:
      ans[A[i]-1]=0
    for j in range(A[i]*2,S+1,A[i]):
      ans[j-1]=0
k=0
for i in A:
  if ans[i-1]==1:
    k+=1
print(k)
# Original solution
def solve():
    n=int(eval(input()))
    a=list(map(int,input().split()))
    ans=0
    a2=set(a)
    a2=list(sorted(a2))
    num3=0
    if a2[0]==1:
        if a.count(1)==1:
            ans=1
        else:
            ans=0
    else:
        len2=len(a2)
        def c1(num1):
            return a.count(num1)
        def l1():
            return len(a2)
        for i in range(len2):
            num=0
            if c1(a2[i-num3])==1:
                for j in range(i-num3):
                    if a2[i-num3]%a2[j]==0:
                        num=1
                        a2.remove(a2[i-num3])
                        num3+=1
                        break
                    if a2[i-num3]/2+1<a2[j]:
                        break
                if num==0:
                    ans+=1
    print(ans)

solve()


# Optimized solution
n=int(eval(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)
# Original solution
import sys
input = sys.stdin.readline

def main():
    N = int(eval(input()))
    Nmax = 10**6+1

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

    prime = [0]*Nmax
    for i in range(N):
        if prime[A[i]] == 0:
            prime[A[i]] = 1
        else:
            prime[A[i]] = -1

    for a in A:
        if prime[a] != 0:
            for q in range(a*2, Nmax, a):
                prime[q] = 0

    res = 0
    for a in prime:
        if a == 1:
            res += 1

    print(res)

if __name__ == '__main__':
    main()

# Optimized solution
import sys
input = sys.stdin.readline

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

    A = list(map(int, input().split()))
    A. sort()
    Nmax = A[-1] + 1

    prime = [0]*Nmax
    for i in range(N):
        if prime[A[i]] == 0:
            prime[A[i]] = 1
        else:
            prime[A[i]] = -1

    for a in A:
        if prime[a] != 0:
            for q in range(a*2, Nmax, a):
                prime[q] = 0

    res = 0
    for a in prime:
        if a == 1:
            res += 1

    print(res)

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

c = Counter(A)
minus = []
for i in list(c.items()):
  if i[1] > 1:
    minus.append(i[0])

flag = True
A = sorted(set(A))
i = 0
j = len(A)-1

while i < j:
  if A[j] % A[i] == 0:
    A.pop(j)
  j -= 1
  if j == i:
    j = len(A)-1
    i += 1
  
cnt = 0
for n in minus:
  if n in A:
    cnt += 1
ans = len(A) - cnt
print(ans)


# Optimized solution
N = int(eval(input()))
A = list(map(int, input().split()))
l = max(A)+1
li = [0]*(l)
A.sort()

for a in A:
  if li[a] == 0:
    li[a] = 1
    for i in range(a*2, l, a):
      li[i] = 2
  elif li[a] == 1:
    li[a] = 2
print((li.count(1)))
# Original solution
N = int(eval(input()))
A = sorted(list(map(int, input().split())))
THE_NUM = 10**6 + 1

dp = [True] * THE_NUM

prev_num = -1
for i in A:
  # if the same number appears as before, that number cannot be counted in the answer.
  if prev_num == i:
    dp[i] = False
  prev_num = i
  for j in range(i * 2, THE_NUM, i):
    dp[j] = False

ans = 0
for i in A:
  # the same number after the second will not counted in the answer.
  if dp[i] == True:
    ans += 1

print(ans)


# Optimized solution
N = int(eval(input()))
A = sorted(list(map(int, input().split())))
THE_NUM = 10**6 + 1

dp = [True] * THE_NUM

prev_num = -1
for i in A:
  # if the same number appears as before, that number cannot be counted in the answer.
  if prev_num != i:
    for j in range(i * 2, THE_NUM, i):
      dp[j] = False
  else:
    dp[i] = False
  prev_num = i

ans = 0
for i in A:
  # the same number after the second will not counted in the answer.
  if dp[i] == True:
    ans += 1

print(ans)
# Original solution
#!/usr/bin/env python3
from collections import Counter
n, *A = list(map(int, open(0).read().split()))
A.sort()
c, s = Counter(A), set()
M = max(A) + 1
ans = 0
for a in A:
    if a in s:
        continue
    ans += c[a] == 1
    for i in range(a, M, a):
        s.add(i)
print(ans)

# Optimized solution
from collections import Counter
n, *A = list(map(int, open(0).read().split()))
A.sort()
c, s = Counter(A), set()
M = max(A) + 1
ans = 0
for a in A:
    if a in s:
        continue
    ans += c[a] == 1
    for i in range(a, M, a):
        s.add(i)
print(ans)
# Original solution
import math
n = int(eval(input()))
a = [int(i) for i in input().split()]

a.sort()
b = set()
c = 0
for i, v in enumerate(a):
    flag = True
    for j in range(1, int(math.sqrt(v))+1):
        if v % j == 0 and (j in b or v/j in b):
            flag = False
            break
    if flag == True:
        b.add(v)
        if i+1 >= len(a):
            c += 1
        elif a[i+1] != v:
            c += 1
  
print(c)

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

a.sort()
b = [0 for _ in range(a[-1])]
c = 0
for i in a:
    x = i-1
    while len(b) > x:
        b[x] += 1
        x += i 
for i in a:
    if b[i-1] == 1:
        c += 1
print(c)
# Original solution
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy

if __name__ == "__main__":
    n = int(eval(input()))
    a = sorted(list(map(int,input().split())))
    M = 1000005
    dp = [0]*(max(a)+1)
    for i in range(n):
        if dp[a[i]] != 0:
            dp[a[i]] = 2
            continue
        for j in range(a[i],max(a)+1,a[i]):
            dp[j]+=1
    cnt = 0
    for i in range(n):
        if dp[a[i]] == 1:
            cnt+=1
    print(cnt)

# Optimized solution
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy

if __name__ == "__main__":
    n = int(eval(input()))
    a = sorted(list(map(int,input().split())))
    M = 1000005
    m = max(a)
    dp = [0]*(m+1)
    for i in range(n):
        if dp[a[i]] != 0:
            dp[a[i]] = 2
            continue
        for j in range(a[i],m+1,a[i]):
            dp[j]+=1
    cnt = 0
    for i in range(n):
        if dp[a[i]] == 1:
            cnt+=1
    print(cnt)
# Original solution
import sys
input = sys.stdin.readline

N = int(eval(input()))

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

AList.sort()

ResultList = []
PrimeList = []

tmp = 0

if N > 1:
    if AList[0] != AList[1]:
        ResultList.append(AList[0])
else:
    ResultList.append(AList[0])
PrimeList.append(AList[0])


for p in range(1, N - 1):
    tmp = 0
    if AList[p - 1] != AList[p] and AList[p] != AList[p + 1]:
        for q in PrimeList:
            if AList[p] % q == 0:
                tmp = 1
                break
        if tmp == 0:
            ResultList.append(AList[p])
            PrimeList.append(AList[p])
    else:
        PrimeList.append(AList[p])

tmp = 0
if N > 1:
    if AList[N - 2] != AList[N - 1]:
        for q in PrimeList:
            if AList[N - 1] % q == 0:
                tmp = 1
                break
        if tmp == 0:
            ResultList.append(AList[N - 1])

print((len(ResultList)))

# Optimized solution
import sys
input = sys.stdin.readline

N = int(eval(input()))

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

AList.sort()

dp = [0] *  (AList[-1] + 1)

for i in AList:
    dp[i] += 1
    
    if dp[i] == 1:
        for p in range(2 * i, len(dp), i):
            dp[p] += 2

print((dp.count(1)))
# Original solution
from collections import Counter
n = int(eval(input()))
a = list(map(int, input().split()))
c = Counter(a)
s = list(set(a))

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

for x in s:
    t = x
    while t <= 10**6:
        P[t] += 1
        t += x

ans = 0

for x in a:
    #print(P[x])
    if P[x] == 1 and c[x] == 1:
        ans += 1

print(ans)

# Optimized solution
from collections import Counter
n = int(eval(input()))
a = list(map(int, input().split()))
c = Counter(a)
p = [True] * (10 ** 6 + 1)
s = list(set(a))

for x in s:
    t = x * 2
    #print(t)
    while t <= 10 ** 6:
        p[t] = False
        t += x
ans = 0
for x in a:
    #print(x)
    if c[x] == 1 and p[x] == True:
        ans += 1
print(ans)
# Original solution
from sys import stdin, setrecursionlimit
from collections import deque


def main():
    input = stdin.buffer.readline
    n = int(eval(input()))
    a = list(map(int, input().split()))
    a.sort()

    q = deque(a)
    ans = 0

    while q:
        a = q.popleft()
        m = len(q)
        for i in range(m):
            b = q.popleft()
            if i == 0 and b == a:
                ans -= 1
            if b % a != 0:
                q.append(b)
        else:
            ans += 1
    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()


# Optimized solution
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n = int(eval(input()))
    a = list(map(int, input().split()))
    a.sort()
    max_a = max(a)

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

    for i in range(n):
        ai = a[i]
        if dp[ai]:
            if not (i < n - 1 and a[i] == a[i + 1]):
                ans += 1
            x = 1
            while ai * x < max_a + 1:
                dp[ai * x] = False
                x += 1

    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()
# Original solution
import sys
from collections import Counter

def ii(): return int(sys.stdin.readline())
def li(): return list(map(int, sys.stdin.readline().split()))

if __name__ == "__main__":
    n = ii()
    a = li()
    c = Counter(a)
    del_list = []
    for k, v in list(c.items()):
        if v >= 2:
            del_list.append(k)
    a = sorted(set(a))
    if len(a) == 0:
        print((0))
        exit()
    max_a = a[-1]
    b = [True] * (max_a + 1)
    def sived(x):
        for not_ans in range(x+x, max_a + 1, x):
            b[not_ans] = False
    for i in a:
        if b[i]:
            sived(i)
    ans = 0
    for i in a:
        if b[i]:
            if i in del_list:
                continue
            ans += 1
    print(ans)


# Optimized solution
import sys
from collections import Counter

def ii(): return int(sys.stdin.readline())
def li(): return list(map(int, sys.stdin.readline().split()))

if __name__ == "__main__":
    n = ii()
    a = li()
    a = sorted(a)
    a_max = a[-1]
    sive = [True] * (a_max + 1)

    def sived(x):
        for non_ans in range(x, a_max+1, x):
            sive[non_ans] = False
    ans = 0
    for i in range(len(a)-1):
        if sive[a[i]]:
            sived(a[i])
            if a[i] != a[i+1]:
                ans += 1
    if sive[a_max]:
        ans += 1
    print(ans)
# Original solution
N = int(eval(input()))
A = list(map(int, input().split()))

DP = [-1 for i in range(max(A)+1)]

A.sort()

for a in A:
  if DP[a] != 0:
    if DP[a] == 1:
      DP[a] = 0
      continue
    for i in range(2*a, max(A)+1, a):
      DP[i] = 0
    DP[a] = 1
  
    
ans = 0
for i in DP:
  if i == 1:
    ans += 1
    
print(ans)

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

A.sort()
maxA = A[-1]
DP = [-1 for i in range(maxA+1)]
for a in A:
  if DP[a] != 0:
    if DP[a] == 1:
      DP[a] = 0
      continue
    for i in range(2*a, maxA+1, a):
      DP[i] = 0
    DP[a] = 1
  
    
ans = 0
for i in DP:
  if i == 1:
    ans += 1
    
print(ans)
# Original solution
import heapq
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def make_divisors(n):
    divisors = set()
    i = 1
    while i*i <= n:
        if n % i == 0:
            divisors.add(i)
            if i != n // i:
                divisors.add(n//i)
        i += 1
    return divisors


def main():
    N = int(input().strip())
    divisors = set()
    ans = set()
    l = [int(i) for i in input().strip().split()]
    heapq.heapify(l)

    for _ in range(N):
        n = heapq.heappop(l)

        if n in divisors:
            if n in ans:
                ans.remove(n)
            continue

        divs = make_divisors(n)

        for d in divs:
            if d in divisors:
                divisors.add(n)
                break
        else:
            divisors.add(n)
            ans.add(n)

    return len(ans)


if __name__ == "__main__":
    print((main()))

# Optimized solution
import heapq
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def main():
    N = int(input().strip())
    l = [int(i) for i in input().strip().split()]
    ans = 0
    m = max(l)
    dp = [0] * (m+1)

    for n in l:
        for j in range(n, m + 1, n):
            dp[j] += 1

    for n in l:
        if dp[n] == 1:
            ans += 1

    return ans


if __name__ == "__main__":
    print((main()))
# Original solution
#import numpy as np
from operator import add
import sys
def calc_double(n,i):
    return float(n/i)

listA=[]
while True:
    try:
        listA.append(list(map(int,input().split())))
    except:
        break;
N=listA[0]
lis_0=[0]*N[0]
lis=listA[1]
for idx1,i in enumerate(lis):
    lis_=[]
    for val in lis:
      lis_.append(calc_double(val,i))
    for idx,num in enumerate(lis_):
        if idx!=idx1:
            if num.is_integer(): lis_[idx]=1
            else: lis_[idx]=0
        else:lis_[idx]=0
    lis_0 = list(map(add, lis_, lis_0))
        
print((lis_0.count(0)))

# Optimized solution
## 動画見てアルゴリズムを知った
listA=[]
while True:
    try:
        listA.append(list(map(int,input().split())))
    except:
        break;

lis=listA[1]
m=max(lis)
lis0=[0]*(m+1)
for i in lis:
    if lis0[i]!=2: 
        j=1
        while i*j<=m:
            lis0[i*j]+=1
            j+=1
            
count=0
for i in lis:
    if lis0[i]==1: count+=1
print(count)
# Original solution
N = int(eval(input()))
A = list(map(int,input().split()))
M = 1000001
cnt = [0]*M
ans = 0
for x in A:
    if cnt[x] != 0:
        cnt[x] = 2
    for i in range(x,M,x):
        cnt[i] += 1
for x in A:
    if cnt[x] == 1:
        ans += 1
print(ans)

    


# Optimized solution
N = int(eval(input()))
A = list(map(int,input().split()))
M = 1000001
cnt = [0]*M
ans = 0
for x in A:
    if cnt[x] != 0:
        cnt[x] = 2
        continue
    for i in range(x,M,x):
        cnt[i] += 1
for x in A:
    if cnt[x] == 1:
        ans += 1
print(ans)
# Original solution
from collections import Counter
import sys

def input():
    return sys.stdin.readline().strip()

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

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

n,*A = get_all_int()
A.sort()



C = dict(Counter(A))
keys = C.keys()
# log(C)

checks = [False] * (1000009)

B = []
for i,a in enumerate(A):
    if C[a] == 1:
        B.append(a)
    else:
        for j in range(a, 1000009, a):
            checks[j] = True

# log(B)

ans = 0

for i,a in enumerate(B):
    if not checks[a]:
        ans += 1
        for j in range(a, 1000009, a):
            checks[j] = True

print(ans)


# Optimized solution
from collections import Counter
import sys

def input():
    return sys.stdin.readline().strip()

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

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

n,*A = get_all_int()
A.sort()



C = dict(Counter(A))
keys = C.keys()
# log(C)

checks = [False] * (1000009)

B = []
for i,a in enumerate(A):
    if C[a] == 1:
        B.append(a)
    elif not checks[a]:
        for j in range(a, 1000009, a):
            checks[j] = True

# log(B)

ans = 0

for i,a in enumerate(B):
    if not checks[a]:
        ans += 1
        for j in range(a, 1000009, a):
            checks[j] = True

print(ans)
# Original solution
# D - Not Divisible
n = int(eval(input()))
a = list(map(int, input().split()))
dic = dict()

for ai in a:
	dic.setdefault(ai, 0)
	dic[ai] += 1

multiples = set()
upper = 10 ** 6

for k in list(dic.keys()):
  i = 2
  
  while True:
    if k * i <= upper:
      multiples.add(k * i)
      i += 1
    else:
      break

ans = 0

for k, v in list(dic.items()):
  if v == 1:
    if not k in multiples:
      ans += 1

print(ans)
  

# Optimized solution
import sys
input = sys.stdin.readline

# D - Not Divisible
n = int(eval(input()))
a = list(map(int, input().split()))
dic = dict()

for ai in a:
	dic.setdefault(ai, 0)
	dic[ai] += 1

multiples = set()
upper = 10 ** 6

for k in list(dic.keys()):
  i = 2
  
  while True:
    if k * i <= upper:
      multiples.add(k * i)
      i += 1
    else:
      break

ans = 0

for k, v in list(dic.items()):
  if v == 1:
    if not k in multiples:
      ans += 1

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

# Optimized solution
n = int(eval(input()))
a = list(map(int, input().split()))
a.sort()
cnt = [0 for _ in range(10**6+5)]
ans = 0
if n == 1:
    print((1))
    exit()
if a[0] == 1:
    if a[1] != 1:
        print((1))
    else:
        print((0))
    exit()
for x in a:
    for i in range(x, 10**6+5, x):
        cnt[i] += 1
for x in a:
    if cnt[x] == 1:
        ans += 1
print(ans)