CodeEff/ECCO huggingface dataset:
# Original solution
from collections import Counter


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

    A_set = set(A)
    A_dict = Counter(A)

    for key, count in list(A_dict.items()):
        if count > 1:
            A_set.discard(key)

        k = key * 2
        while k <= max(A):
            A_set.discard(k)
            k += key

    print((len(A_set)))


if __name__ == '__main__':
    main()


# Optimized solution

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

    m = max(A) + 1
    dp = [0] * m

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

    print((sum(dp[i] == 1 for i in A)))


if __name__ == '__main__':
    main()
# Original solution
from collections import Counter 
n = int(eval(input()))
a = sorted(list(map(int, input().split())))
s = sorted(set(a))
c = Counter(a)
t = [0] * (10**6 + 1)
for i in a:
    for j in range(i, 10**6+1, i):
        t[j] += 1

ans = sum(1 for i in a if t[i] == 1 and c[i] == 1)
print(ans)



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

ans = len([1 for i in s if t[i] == 1 and c[i] == 1])
print(ans)
# Original solution
N = int(eval(input()))
A = [int(n) for n in input().split()]
ans = 0

for i in range(N):
    for j in range(N):
        if A[i] % A[j] == 0 and i != j:
            break
        if j == N-1:
            ans += 1

print(ans)

# Optimized solution
N = int(eval(input()))
A = [int(n) for n in input().split()]
maxA = max(A)

C = {a:0 for a in A}
D = {a:0 for a in A}
for a in A:
    C[a] += 1
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
# -*- coding: utf-8 -*-
n = int(eval(input()))
a = list(map(int, input().split()))

count = 0
for i in range(n):
    is_divisible = False
    for j in range(n):
        divisible_num = []
        if a[i] % a[j] == 0 and i != j:
            divisible_num.append(a[j])
            is_divisible = True
        if len(divisible_num) >= 1:
            continue
    if is_divisible:
        continue
    else:
        count += 1

print(count)


# Optimized solution
# -*- coding: utf-8 -*-
n = int(eval(input()))
a = sorted(list(map(int, input().split())))

# 探索範囲は数列aの最大値まで
max_a = a[-1]
b = [0] * (max_a + 1)
ans = set()
for i in a:
    if b[i] == 1:
        if i in ans:
            ans.remove(i)
        continue
    # 探索範囲内のiの倍数をチェック
    for j in range(i, max_a+1, i):
            b[j] = 1
    ans.add(i)

print((len(ans)))
# Original solution
N = int(eval(input()))
A = list(map(int, input().split()))
A.sort()

F = [0 for i in range(A[-1]+1)]
for i in A:
  F[i] = 1

c_set = set()
for i in A:
  if F[i] == 0:
    continue
  c_set.add(i)
  for j in range(i, A[-1]+1, i):
    F[j] = 0

ans = len(c_set)
d = 0
for i in c_set:
  if A.count(i) > 1:
    d += 1

print((ans - d))

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

F = [0 for i in range(A[-1]+1)]
for i in A:
  F[i] = 1

c_set = set()
for i in A:
  if F[i] == 0:
    continue
  c_set.add(i)
  for j in range(i, A[-1]+1, i):
    F[j] = 0

ans = len(c_set)
d = 0
d_set = set()
for i in range(N):
  if i == 0 and N > 1:
    if A[i] == A[i+1]:
      d_set.add(A[i])
  elif i < N - 1 and A[i-1] != A[i] and A[i] == A[i+1]:
    d_set.add(A[i])

print(( len(c_set - d_set) ))
# Original solution
from itertools import chain
from collections import Counter

def factors(n):
    yield from chain.from_iterable(({i, n//i} for i in range(1, int(n ** 0.5) + 1) if n % i == 0))

def get_non_divisible():
    n, *lst = list(map(int, open(0).read().split()))
    c = Counter(lst)
    d = {val: sum((-c.get(f, 0) for f in factors(val)), len(lst)) for val in c}
    res = 0
    for i in lst:
      if d[i] == n - 1:
        res += 1
    return res
  
if __name__ == '__main__':
    print((get_non_divisible()))

# Optimized solution
from collections import defaultdict, Counter

def main():
  n, *A = list(map(int, open(0).read().split()))
  A.sort()
  n = A[-1]
  isPrime = [True] * (n + 1)
  prep = 0
  for i in A:
    if prep == i:
      isPrime[prep] = False
      continue
    if isPrime[i]:
      for j in range(i * 2, n + 1, i):
        isPrime[j] = False
    prep = i

  prep = res = 0
  for i in A:
    if prep == i:
      continue
    if isPrime[i]:
      res += 1
    prep = i
  print(res)
if __name__ == '__main__':
  main()
# Original solution
def main():
    n, *A = list(map(int, open(0).read().split()))
    A.sort()
    n = A[-1]
    isPrime = [True] * (n + 1)
    prep = 0
    for i in A:
        if prep == i:
            isPrime[prep] = False
            continue
        if isPrime[i]:
            for j in range(i * 2, n + 1, i):
                isPrime[j] = False
        prep = i

    prep = res = 0
    for i in A:
        if prep == i:
            continue
        if isPrime[i]:
            res += 1
        prep = i
    print(res)


if __name__ == '__main__':
    main()


# Optimized solution
def main():
  n, *A = list(map(int, open(0).read().split()))
  A.sort()
  m = A[-1]
  lst = [0] * (m + 1)
  prep = 0
  for i in A:
    if i == prep:
      lst[i] = 1
      continue
    lst[2 * i::i] = [1] * len(lst[2 * i::i])
    prep = i
  res = 0
  for i in A:
    if lst[i] == 0:
      res += 1
  print(res)

if __name__ == '__main__':
  main()
# Original solution
from collections import Counter
n = int(eval(input()))
a = list(map(int, input().split()))
a.sort()
b = [True] * n
c = Counter(a)
for i in range(n):
    if b[i]:
        for j in range(i+1, n):
            if a[j] % a[i] == 0 and i != j:
                b[j] = False
ans = 0
for i in range(n):
    if b[i] and c[a[i]] == 1:
        ans += 1
print(ans)

# Optimized solution
from collections import Counter
n = int(eval(input()))
a = list(map(int, input().split()))
a.sort()
dp = [0] * a[-1]
c = Counter(a)
for i in a:
    for j in range(i, a[-1]+1, i):
        dp[j-1] += 1
ans = 0
for i in a:
    if dp[i-1] == 1 and c[i]:
        ans += 1
print(ans)
# Original solution
# review
def main():
    N = int(eval(input()))
    A = list(map(int, input().split()))
    A.sort()
    ans = 0
    OK = [True for i in range(10**6+1)]
    CNT = [0 for i in range(10**6+1)]
    for x in A:
        CNT[x] += 1
        for i in range(2, 10**6+1):
            if i*x > 10**6:
                break
            OK[i*x] = False
    for x in A:
        if CNT[x] == 1 and OK[x]:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

# Optimized solution
# review
def main():
    N = int(eval(input()))
    A = list(map(int, input().split()))
    A.sort()
    ans = 0
    OK = [True for i in range(10**6+1)]
    CNT = [0 for i in range(10**6+1)]
    for x in A:
        CNT[x] += 1
        if CNT[x] == 1:
            for i in range(2, 10**6+1):
                if i*x > 10**6:
                    break
                OK[i*x] = False
    for x in A:
        if CNT[x] == 1 and OK[x]:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()
# Original solution
N = 5
ARR = [24, 11, 8, 3, 16]


N = 4
ARR = [5, 5, 5, 5]


N = 10
ARR = [33, 18, 45, 28, 8, 19, 89, 86, 2, 4]

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

def calculate(n, arr):

    prr = [0 for i in range(2000005)]

    for i in range(n):
        start = arr[i]
        #
        # if prr[start] > 0:
        #     prr[start] = 2
        #     continue

        for j in range(start, 2000005, start):
            prr[j] = prr[j] + 1


    result = 0
    for i in range(n):
        start = arr[i]
        if prr[start] == 1:
            result += 1


    print(result)

calculate(N, ARR)


# Optimized solution
N = 5
ARR = [24, 11, 8, 3, 16]


N = 4
ARR = [5, 5, 5, 5]


N = 10
ARR = [33, 18, 45, 28, 8, 19, 89, 86, 2, 4]

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

def calculate(n, arr):

    prr = [0 for i in range(2000005)]

    for i in range(n):
        start = arr[i]
        #
        if prr[start] > 0:
            prr[start] = 2
            continue

        for j in range(start, 2000005, start):
            prr[j] = prr[j] + 1


    result = 0
    for i in range(n):
        start = arr[i]
        if prr[start] == 1:
            result += 1


    print(result)

calculate(N, ARR)
# Original solution
N = 5
ARR = [24, 11, 8, 3, 16]


N = 4
ARR = [5, 5, 5, 5]


N = 10
ARR = [33, 18, 45, 28, 8, 19, 89, 86, 2, 4]

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

def calculate(n, arr):

    prr = [0 for i in range(2000005)]

    for i in range(n):
        start = arr[i]
        #
        if prr[start] > 0:
            prr[start] = 2
            continue

        for j in range(start, 2000005, start):
            prr[j] = prr[j] + 1


    result = 0
    for i in range(n):
        start = arr[i]
        if prr[start] == 1:
            result += 1


    print(result)

calculate(N, ARR)


# Optimized solution
N = 5
ARR = [24, 11, 8, 3, 16]

N = 4
ARR = [5, 5, 5, 5]

N = 10
ARR = [33, 18, 45, 28, 8, 19, 89, 86, 2, 4]

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

def calculate(n, arr):
    krr = [0 for i in range(1, 1000007)]

    for i in range(n):
        start = arr[i]

        if krr[start] > 0:
            krr[start] = 2
            continue

        for j in range(start, 1000006, start):
            krr[j] += 1

    result = 0
    for i in range(n):
        if krr[arr[i]] == 1:
            result += 1

    print(result)


calculate(N, ARR)
# Original solution
n = int(eval(input()))
A = sorted(map(int, input().split()))

U = 10**6
line = [1]*(U+1)
ans = set()
depricated = set()
cnt = [0]*(U+1)
for a in A:
    cnt[a] += 1
    if cnt[a] == 2 and line[a]:
        depricated.add(a)
    if line[a]:
        ans.add(a)
        for p in range(2*a, U+1, a):
            line[p] = 0
print((len(ans)-len(depricated)))


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

U = A[-1]
line = [1]*(U+1)
ans = set()
depricated = set()
cnt = [0]*(U+1)
for a in A:
    cnt[a] += 1
    if cnt[a] == 2 and line[a]:
        depricated.add(a)
    if line[a]:
        ans.add(a)
        for p in range(2*a, U+1, a):
            line[p] = 0
print((len(ans-depricated)))
# Original solution
n = int(eval(input()))
A = sorted(map(int, input().split()))

U = 10**6
line = [1]*(U+1)
ans = set()
depricated = set()
cnt = [0]*(U+1)
for a in A:
    cnt[a] += 1
    if cnt[a] == 2 and line[a]:
        depricated.add(a)
        continue
    if 2 < cnt[a]:
        continue
    if line[a]:
        ans.add(a)
        for p in range(2*a, U+1, a):
            line[p] = 0
print((len(ans-depricated)))


# Optimized solution
n = int(eval(input()))
A = sorted(map(int, input().split()))
U = A[-1]
line = [1]*(U+1)
ans = set()
depricated = set()
cnt = [0]*(U+1)
for a in A:
    if a in ans:
        depricated.add(a)
        continue
    if line[a]:
        ans.add(a)
        for p in range(2*a, U+1, a):
            line[p] = 0
print((len(ans-depricated)))
# Original solution
def main():
    N = int(eval(input()))
    AList = list(map(int, input().split()))

    answer = 0

    for i in range(N):

        for j in range(N):

            if((i != j) and AList[i] % AList[j] == 0):
                break

        else:
            answer = answer + 1

    print(answer)


if __name__ == "__main__":
    main()

# Optimized solution
def main():
    N = int(eval(input()))
    AList = list(map(int, input().split()))
    AList.sort()
    AMax = AList[-1] + 1

    dp = [True] * AMax
    answer = 0

    ACheckSet = set()
    ACheckSetCheckSet = set()

    for A in AList:

        if dp[A]:
            answer = answer + 1
            ACheckSet.add(A)

            for x in range(A, AMax, A):
                dp[x] = False

        elif A in ACheckSet:

            if A in ACheckSetCheckSet:
                pass
            else:
                answer = answer - 1
                ACheckSetCheckSet.add(A)

    print(answer)


if __name__ == "__main__":
    main()
# Original solution
def resolve():
    n = int(eval(input()))
    a = list(map(int, input().split()))
    a = sorted(a)
    ans = [1]*n
    for i in range(n):
        if ans[i] == 1:
            for j in range(i+1, n):
                if a[j] == a[i]:
                    ans[i] = 0
                if a[j]%a[i] ==0:
                    ans[j] = 0
    print((sum(ans)))
resolve()

# Optimized solution
def resolve():
    n = int(eval(input()))
    a = list(map(int, input().split()))
    a1 = {}
    for i in range(len(a)):
        if a[i] in a1:
            a1[a[i]] += 1
        else:
            a1[a[i]] = 1
    a = sorted(list(a1.keys()))
    ans = [1] * a[-1]

    for i in a:
        if ans[i-1] == 1:
            for j in range(i-1, len(ans), i):
                ans[j] = 0
            ans[i-1] =1
    ans1 = 0
    for i in a:
        if a1[i] == 1:
            ans1 += ans[i-1]
    print(ans1)
resolve()
# Original solution
from sys import stdin
data = stdin.readlines()

x = int(data[0].split()[0])
a = [int(s) for s in data[1].split()]
a = sorted(a, reverse = True)

counter = 0
for i in range(len(a)):
    for j in range(len(a)):
        if i != j and a[i] % a[j] == 0:
            break
    else:
        counter += 1
print(counter)

# Optimized solution
from sys import stdin
data = stdin.readlines()

n = int(data[0].split()[0])
a = [int(s) for s in data[1].split()]
a = sorted(a)

max = a[-1]

l = [0]*(max+1)

for i in a:
    l[i] += 1
    if l[i] == 1:
        for j in range(i*2,max+1,i):
            l[j] = 2
print((l.count(1)))
# Original solution
n = int(eval(input()))
a = sorted(list(map(int,input().split())))
arr = [0]*(max(a)+1)

for i in a:
  arr[i]+=1
  tmp = i
  if arr[i]<=1:
      while (tmp+i)<=max(a):
        tmp += i
        if arr[tmp] !=0:
          arr[tmp] =2
        else:
          arr[tmp] +=1

cnt = 0
for i in a:
  if arr[i] ==1:
    cnt += 1
print(cnt)
      

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

      

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

for i in a:
  for j in range(i,m+1,i):
    arr[j]+=1

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

print(cnt)
# Original solution
import math

N = int(eval(input()))
A = list(map(int, input().split()))
A = sorted(A)
valid = [True] * len(A)
sqrt = A[len(A)-1] // 2
stop = -1
for i in range(len(A)):
    if A[i] > sqrt:
        stop = i
        break
    if valid[i] == False:
        continue
    for j in range(i+1, len(A)):
        if valid[j] == False:
            continue
        if A[j] % A[i] == 0:
            valid[j] = False
        if A[j] == A[i]:
            valid[i] = False
if stop != -1:
    cur = A[stop]
    for i in range(stop+1, len(A)):
        if cur == A[i]:
            valid[i-1] = valid[i] = False
        else:
            cur = A[i]
print((valid.count(True)))


# Optimized solution
import math

N = int(eval(input()))
A = list(map(int, input().split()))
A = sorted(A)
maxA = A[len(A)-1]
valid = [True] * maxA

for i in range(len(A)):
    if valid[A[i]-1] == False:
        continue
    if i != 0 and A[i-1] == A[i]:
        valid[A[i]-1] = False
    else:
        for j in range(A[i]*2, maxA+1, A[i]):
            valid[j-1] = False

count = 0
for i in range(len(A)):
    if valid[A[i]-1] == True:
        count += 1
print(count)
# Original solution
if __name__ == "__main__":
    n = int(eval(input()))
    l_a = list(map(int, input().split()))
    s_a = list(set(l_a))

    s_a.sort()

    dub_a = [0]*(max(s_a)+1)

    for i in l_a:
        dub_a[i] += 1

    dp = [1]*(max(s_a)+1)

    for i in s_a:
        if 2*i > len(dp)-1:
            pass
            '''
            elif dp[2*i] == 0:
            pass
            '''
        else:
            for j in range(2*i, len(dp), i):
                dp[j] = 0


    count = 0
    for i in s_a:
        if dp[i]==1 and dub_a[i]==1:
            count += 1
    print(count)


# Optimized solution
if __name__ == "__main__":
    n = int(eval(input()))
    l_a = list(map(int, input().split()))
    s_a = list(set(l_a))

    s_a.sort()

    dub_a = [0]*(max(s_a)+1)

    for i in l_a:
        dub_a[i] += 1

    dp = [1]*(max(s_a)+1)

    for i in s_a:
        if dp[i] == 0:
            pass
        else:
            for j in range(2*i, len(dp), i):
                dp[j] = 0


    count = 0
    for i in s_a:
        if dp[i]==1 and dub_a[i]==1:
            count += 1
    print(count)
# Original solution
import collections
N = int(eval(input()))
A = list(map(int,input().split()))
counter = collections.Counter(A)
B = list(set(A))
count = 0
for i in range(len(B)):
    if counter[B[i]]>1:
        continue
    if B[i]==1:
        count += 1
        continue
    else:
        check = 0
        for j in range(1,int(B[i]**0.5)+1):
            if (j != 1 and B[i]%j==0 and (j in counter or B[i]//j in counter)) or (j==1 and j in counter):
                check += 1
                break
        if check==0:
            count += 1
print(count)
    

# Optimized solution
import collections
N = int(eval(input()))
A = list(map(int,input().split()))
S = set()
D = set()
for a in A:
    if a in S:
        D.add(a)
    else:
        S.add(a)
M = max(S)
A = [0]*(M+1)
for s in S:
    if s in D:
        A[s] += 1
    for i in range(2*s,M+1,s):
        A[i]+=1
count = 0
for s in S:
    if A[s]==0:
        count += 1
print(count)
# Original solution
n=int(eval(input()))
a=list(map(int,input().split()))
a=sorted(a)
p=[0]*(10**6+1)
for i in range(n):
    if p[a[i]]==0:
        j=2
        while a[i]*j<=10**6:
            p[a[i]*j]=1
            j+=1
a.append(-1)
a.insert(0,-1)
ans=0
for i in range(1,n+1):
    if a[i]!=a[i+1] and a[i]!=a[i-1] and p[a[i]]==0:
        ans+=1
print(ans)


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

p=[0]*(10**6+1)
for i in b:
    if p[i]==0:
        j=2
        while i*j<=10**6:
            p[i*j]=1
            j+=1
a.append(-1)
a.insert(0,-1)
ans=0
for i in range(1,n+1):
    if a[i]!=a[i+1] and a[i]!=a[i-1] and p[a[i]]==0:
        ans+=1
print(ans)
# Original solution
import sys
input=sys.stdin.readline #文字列入力はするな！！

n=int(eval(input()))
a=list(map(int,input().split()))
z=[0]*(10**6+1)
ans=0
for i in a:
    z[i]+=1
for i in a:
    j=2
    f=0
    if z[i]>=2:
        f=1
    if z[1]>=2:
        f=1
    if i!=1 and z[1]==1:
        f=1
    while j*j<=i:
        if i%j==0:
            if z[j]>=1 or z[i//j]>=1:
                f=1
        j+=1
    if f==0:
        ans+=1
print(ans)


# Optimized solution
import sys
input=sys.stdin.readline #文字列入力はするな！！

n=int(eval(input()))
a=list(map(int,input().split()))
z=[0]*(10**6+1)
ans=0
for i in a:
    z[i]+=1
for i in a:
    if i%2==0:
        j=2
    else:
        j=3
    f=0
    if z[i]>=2:
        f=1
    if z[1]>=2:
        f=1
    if i!=1 and z[1]==1:
        f=1
    while j*j<=i:
        if i%j==0:
            if z[j]>=1 or z[i//j]>=1:
                f=1

        if i%2==0:      
            j+=1
        else:
            j+=2
    if f==0:
        ans+=1
print(ans)
# Original solution
import sys
input=sys.stdin.readline #文字列入力はするな！！
sys.setrecursionlimit(10**9) #再帰の上限をあげる
n=int(eval(input()))
a=list(map(int,input().split()))
z=[0]*(10**6+1)
ans=0
for i in a:
    z[i]+=1

x=[-1]*(10**6+1) #2以上の自然数に対して最小の素因数を表す
x[0]=0
x[1]=1
i=2
prime=[]
while i<=10**6:
    if x[i]==-1:
        x[i]=i
        prime.append(i)
    for j in prime:
        if i*j>10**6 or j>x[i]:break
        x[j*i]=j
    i+=1

for i in a:
    f=0
    u=i
    if z[u]>=2:
        f=1
    w=[[1,1]]
    p=x[u]
    cnt=1
    while u>1:
        if p==x[u//p]:
            cnt+=1
            u=u//p
        else:
            w.append([p,cnt])
            cnt=1
            u=u//p
            p=x[u]

    m=len(w)

    def s(d,h,y):
        global m
        global i
        global f
        if d==m-1:
            p=y*(w[d][0]**h)
            if p!=i and z[p]>=1:
                f=1
        else:
            y*=w[d][0]**h
            for j in range(w[d+1][1]+1):
                s(d+1,j,y)

    s(0,1,1)
    if f==0:
        ans+=1
print(ans)


# Optimized solution
import sys
input=sys.stdin.readline #文字列入力はするな！！
sys.setrecursionlimit(10**9) #再帰の上限をあげる
n=int(eval(input()))
a=list(map(int,input().split()))
z=[0]*(10**6+1)
ans=0
for i in a:
    z[i]+=1

x=[-1]*(10**6+1) #2以上の自然数に対して最小の素因数を表す
x[0]=0
x[1]=1
i=2
prime=[]
while i<=10**6:
    if x[i]==-1:
        x[i]=i
        prime.append(i)
    for j in prime:
        if i*j>10**6 or j>x[i]:break
        x[j*i]=j
    i+=1

for i in a:
    f=0
    u=i
    if z[u]>=2:
        f=1
    w=[[1,1]]
    p=x[u]
    cnt=1
    while u>1:
        if p==x[u//p]:
            cnt+=1
            u=u//p
        else:
            w.append([p,cnt])
            cnt=1
            u=u//p
            p=x[u]

    m=len(w)

    def s(d,y):
        global m
        global i
        global f
        if d==m-1:
            p=y
            if p!=i and z[p]>=1:
                f=1
        else:
            for j in range(w[d+1][1]+1):
                s(d+1,y*(w[d+1][0]**j))

    s(0,1)
    if f==0:
        ans+=1
print(ans)
# Original solution
N=int(eval(input()))
A=list(map(int,input().split()))
ans=0
for a in range(N):
  newA = [A[a]%n for n in A]
  newA.pop(a)
  if 0 in newA:
    ans = ans
  else:
    ans += 1
  
print(ans)

# Optimized solution
N = int(eval(input()))
A = list(map(int, input().split()))
A.sort()
Amax = A[-1]
dp = [1]*(Amax+1)
ans = 0
for i in range(len(A)-1):
  p = A[i]
  if dp[p] == 1:
    for q in range(Amax//p+1):
      dp[p*q] = 0
    if A[i] != A[i+1]: 
      ans += 1
if dp[Amax] == 1:
  ans += 1
print(ans)
# Original solution
def main():
    N = int(eval(input()))
    A = list(map(int, input().split()))
    A.sort()

    ans = 0
    temp = 0
    if N == 1:
        return 1

    if A[0] == 1 and A[1] != 1:
        return 1
    elif A[0] == 1 and A[1] == 1:
        return 0

    for i in range(N):
        if i == 0 and A[i+1] != A[i]:
            ans += 1
            continue

        temp = A[i]
#同じ数があるかどうか
        if i == N-1 and temp == A[i-1]:
            continue
        elif i != N-1:
            if temp == A[i+1] or temp == A[i-1]:
                continue

        for j in range(N):
            if A[j] == -1:
                continue
            elif A[j] <= temp/2 and A[i]%A[j] == 0:
                A[i] = -1
                break
            elif A[j] <= temp//2 and A[i]%A[j] != 0:
                continue
            elif A[j] > temp//2:
                ans += 1
                break
    return ans

print((main()))


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

    A.sort()
    dict = {}
    for i in range(1,A[N-1]+1):
        dict[i] = 0

    if N == 1:
        return 1

    if A[0] == 1 and A[1] != 1:
        return 1
    elif A[0] == 1 and A[1] == 1:
        return 0

    temp = 1

    for num in A:
        while True:
            if num*temp <= A[N-1]:
                dict[num*temp] += 1
                temp += 1
            else:
                temp = 1
                break

    ans = 0
    for num2 in A:
        if dict[num2] <= 1:
            ans += 1

    return ans


print((main()))