Problem:
 Score : 400 points    Problem Statement Given is a number sequence A of length N .  Find the number of integers i  \left(1 \leq i \leq N\right) with the following property:   For every integer j  \left(1 \leq j \leq N\right) such that i \neq j , A_j does not divide A_i .       Constraints  All values in input are integers.  1 \leq N \leq 2 \times 10^5  1 \leq A_i \leq 10^6         Input Input is given from Standard Input in the following format:  N  A_1  A_2  \cdots  A_N       Output Print the answer.        Sample Input 1 5
24 11 8 3 16      Sample Output 1 3  The integers with the property are 2 , 3 , and 4 .       Sample Input 2 4
5 5 5 5      Sample Output 2 0  Note that there can be multiple equal numbers.       Sample Input 3 10
33 18 45 28 8 19 89 86 2 4      Sample Output 3 5

Solution (Python):
import collections

n=int(input())
arr=list(map(int,input().split()))
arr=sorted(arr)
s=set()
cnt=collections.Counter(arr)
for i in range(n):
  if arr[i] in s:
    continue
  if cnt[arr[i]]>=2:
    s.add(arr[i])
  for j in range(2,10**6//arr[i]+1):
    s.add(arr[i]*j)
ans=0
for i in range(n):
  if arr[i] in s:
    continue
  ans+=1
print(ans)

Solution (Python):
def main():
    import sys
    from collections import Counter
    input = sys.stdin.readline

    N = int(input())
    A = sorted([int(a) for a in input().strip().split()])
    Acnt = Counter(A)
    if Acnt[1] == 1:
        print(1)
        return True
    elif Acnt[1] > 1:
        print(0)
        return True

    max_A = max(A)
    f = [True] * (max_A + 1)
    ans = 0
    for i in range(2, max_A + 1):
        if Acnt[i] > 0 and f[i]:
            if Acnt[i] == 1:
                ans += 1
            j = 1
            k = i
            while k <= max_A:
                f[k] = False
                j += 1
                k = i * j

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
if __name__ == "__main__":
    n = int(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)

Solution (Python):
N = int(input())
A = sorted(list(map(int, input().split())))

max_A = A[-1]

df = [True for _ in range(max_A + 1)]

for i, a in enumerate(A):
    if i > 0:
        if A[i] == A[i - 1]:
            df[a] = False
            continue
    if df[a]:
        for num in range(2*a, max_A+1, a):
            df[num] = False
count = 0
for a in A:
    if df[a]:
        count += 1
print(count)

Solution (Python):
from collections import defaultdict
import sys
n = int(input())
A = list(map(int, input().split()))





d = defaultdict(int)

for key in A:
    d[key] += 1





B = list(d)






m = max(d)
flag = [0 for i in range(m+1)]

for i in B:
    t = i
    while t <= m:
        flag[t] += 1
        t += i

ans = 0
for i in B:
    if flag[i] == 1 and d[i] == 1:
        ans += 1

print(ans)

Solution (Python):
if __name__ == "__main__":
    n = int(input())
    l_a = list(map(int, input().split()))
    s_a = list(set(l_a))

    

    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)

Solution (Python):
if __name__ == "__main__":
    n = int(input())
    l_a = list(map(int, input().split()))
    s_a = list(set(l_a))

    

    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:
        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)

Solution (Python):
n = int(input())
A = list(map(int, input().split()))

Cnt = [0 for i in range(10**6 + 8)]
for i in A:
    if Cnt[i] != 0:
        Cnt[i] = 2
        continue
    else:
        pass
    for j in range(i, 10**6 + 8, i):
        Cnt[j] += 1

ans = 0
for i in A:
    if Cnt[i] == 1:
        ans += 1
    else:
        pass

print(ans)

Solution (Python):
N= int(input())
a =list(map(int,input().split()))
a.sort()
ans=0
Amax=max(a)
DP=[1]*(Amax+1)

for i in range(N-1):
    p=a[i]
    if DP[p]==1:
        for j in range(Amax//p+1):
            DP[p*j]=0
        if p!=a[i+1]:
            ans+=1
if DP[Amax]==1:
    ans+=1

print(ans)

Solution (Python):
import collections
N = int(input())
A = list(map(int, input().split()))
cnt = collections.Counter(A)
A.sort()
dp = [True] * (max(A) + 1)
ans = 0
for n in A:
    ans += int(dp[n] and cnt[n] == 1)
    tmp = n
    while tmp < len(dp):
        dp[tmp] = False
        tmp += n
print(ans)

Solution (Python):
n = int(input())
A = list(map(int,input().split()))
A.sort()
import collections
co = collections.Counter(A)

ma = 10**6+1
div = [0]*ma 
cnt = 0
prev = -1
for a in A:
    if div[a] == 1:
        continue
    if co[a]==1:
        cnt+=1
    for i in range(a,ma,a):
        div[i] = 1

print(cnt)

Solution (Python):
from collections import Counter
n = int(input())
a = list(map(int, input().split()))

c = Counter(a)
b = [k for k, v in c.items() if v == 1]
b.sort()
d = {b: i for i, b in enumerate(b)}

gg = [True] * len(b)
mx = 10 ** 6 + 1
for i in c.keys():
    for j in range(2 * i, mx, i):
        if j in d:
            gg[d[j]] = False

print(sum(gg))

Solution (Python):

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



import numpy as np

A.sort()
MAX=10**6+1
L = [0]*MAX
used = set()

for a in A:
    if L[a] == 2:
        continue
    if a in used:
        for i in range(0,MAX,a):
            L[i] = 2
        
        continue
    used.add(a)
    
    L[a] = 1
    for i in range(2*a,MAX,a):
        L[i] = 2
    
count = 0
for a in A:
    if L[a] == 1:
        count += 1
print(count)

Solution (Python):
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N,*A = map(int, read().split())

    A.sort()
    table = [0] * (A[-1] + 1)
    n = len(table)

    for a in A:
        if table[a] > 1:
            continue

        if table[a] == 0:
            for i in range(2*a, n, a):
                table[i] = 2
        
        table[a] += 1

    ans = 0
    for a in A:
        if table[a] == 1:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import Counter

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

maxA = max(A)
C = Counter(A)

D = {a: 0 for a in A}
for a in A:
  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)

Solution (Python):
import numpy as np
n = int(input())
A = [int(i) for i in input().split()]
A.sort()
dp = np.array([True for _ in range(A[-1]+1)])
A = np.array(A)
prev = 0
for a in A:
  if dp[a]:
    if prev == a:
      dp[a] = False
    for i in range(A[-1]//a+1):
      if i > 1:
        dp[i*a] = False
  prev = a
print(dp[A.tolist()].sum())

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
ans=0
a.sort()
cnt=[0 for i in range(a[-1]+1)]
for i in a:
  cnt[i]+=1

dp=[True for i in range(a[-1]+1)]

for i in range(n):
  if dp[a[i]]==False:
    
    continue
  if a[i]*2<=a[-1]+1:
    for j in range(a[i]*2,a[-1]+1,a[i]):
      dp[j]=False
      
for i in range(len(cnt)):
  if cnt[i]>=2:
    dp[i]=False
    
for i in range(n):
  if dp[a[i]]:
    ans+=1
print(ans)

Solution (Python):
import collections
n = int(input())
a = list(map(int, input().split()))

a.sort()

ma = max(a)
f = [1] * (ma + 1)

count = collections.Counter(a)
ans = 0

for i in a:
    if f[i]:
        if count[i] == 1:
            ans += 1
        for j in range(i, min(ma + i, ma + 1), i):
            f[j] = 0

print(ans)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
A.sort()
MAX = A[-1]+1
num_tmp = [0]*MAX

for a in A:
    num_tmp[a] += 1
    if num_tmp[a] == 1:
        for i in range(2*a,MAX,a):
            num_tmp[i] = 2

print(num_tmp.count(1))

Solution (Python):
def main():
    N = int(input())
    A = list(map(int,input().split()))
    A.sort()
    MAX = A[-1]+1
    num_tmp = [0]*MAX

    for a in A:
        num_tmp[a] += 1
        if num_tmp[a] == 1:
            for i in range(2*a,MAX,a):
                num_tmp[i] = 2

    print(num_tmp.count(1))
    
main()

Solution (Python):

n=int(input())
List=list(map(int,input().split()))

List.sort()
seive=[0]*(List[~0]+1)
count=0
for each in List:
    for i in range(each,List[-1]+1,each):
        seive[i]+=1
        
for each in List:
    if(seive[each]==1):
        count+=1


print(count)

Solution (Python):
_,*A = map(int,open(0).read().split())
A.sort()
M = 10**6 + 1
l = [0] * (M)
for a in A:
    if l[a] == 0:
        l[a] = 2
        for x in range(a*2, M, a):
            l[x] = 1
    elif l[a] == 2:
        l[a] += 1
print(l.count(2))

Solution (Python):
def main():
    input()
    array = sorted(int(x) for x in input().split())
    maximum = array[-1] + 1
    counter = [0] * maximum

    for x in array:
        if counter[x] != 0:
            counter[x] = 2
            continue
        else:
            for multiple in range(x, maximum, x):
                counter[multiple] += 1
    ans = sum(counter[x] == 1 for x in array)
    print(ans)


main()

Solution (Python):
def main():
    input()
    array = sorted(int(x) for x in input().split())
    maximum = array[-1] + 1
    counter = [0] * maximum

    for x in array:
        if counter[x] != 0:
            counter[x] = 2
            continue
        else:
            for multiple in range(x, maximum, x):
                counter[multiple] += 1
    ans = sum(counter[x] == 1 for x in array)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    input()
    array = sorted(int(x) for x in input().split())
    maximum = array[-1] + 1
    counter = [0] * maximum

    for x in array:
        if counter[x] != 0:
            counter[x] = 2
            continue
        else:
            for multiple in range(x, maximum, x):
                counter[multiple] += 1
    ans = sum(counter[x] == 1 for x in array)
    print(ans)


main()

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque
def main():
    N = int(input())
    a = list(map(int, input().split()))
    arr = [0]*(10**6 + 1)
    for x in a:
        if arr[x] == 0:
            for i in range(x, 10**6 + 1, x):
                arr[i] += 1
        else:
            arr[x] += 1
    ans = 0
    for i in a:
        if arr[i] == 1:
            ans += 1
    print(ans)
        
if __name__ == '__main__':
    main()

Solution (Python):
def main():
    input()
    array = sorted(int(x) for x in input().split())
    maximum = array[-1] + 1
    counter = [0] * maximum

    for x in array:
        if counter[x] != 0:
            counter[x] = 2
            continue
        else:
            for multiple in range(x, maximum, x):
                counter[multiple] += 1
    ans = 0
    for x in array:
        if counter[x] == 1:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
a_list = list(map(int, input().split()))
ans_len = 10**6+10
is_ans = [0]*(ans_len)

for a in a_list:
    is_ans[a] += 1
    if is_ans[a] == 1:
        b = 2*a
        while b < ans_len:
            is_ans[b] += 2
            b += a

ans = 0
for a in a_list:
    
    ans += (is_ans[a] == 1)
print(ans)

Solution (Python):
from collections import defaultdict


def main():
    input()
    array = sorted(int(x) for x in input().split())
    maximum = 1000003

    counter = defaultdict(int)
    for x in array:
        counter[x] += 1
    maximum = array[-1] + 1
    candidates = [True] * maximum
    for key, value in counter.items():
        if value > 1:  
            candidates[key] = False
        for i in range(key * 2, maximum, key):
            candidates[i] = False

    ans = sum(candidates[x] for x in array)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
lis = list(map(int, input().split()))
maxL = max(lis)+1
t = [0] * maxL
lis.sort()
for k in lis:
    t[k] += 1
    if t[k] == 1:
        for p in range(k * 2, maxL, k):
            t[p] += 2
print(t.count(1))

Solution (Python):
def main():
    input()
    array = sorted(int(x) for x in input().split())
    maximum = 1000001
    counter = [0] * maximum

    for x in array:
        if counter[x] != 0:
            counter[x] = 2
            continue
        else:
            for multiple in range(x, maximum, x):
                counter[multiple] += 1
    ans = 0
    for x in array:
        if counter[x] == 1:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    numbers = int(input())
    array = [int(x) for x in input().split()]
    maximum = 1000001
    counter = [0] * maximum

    for x in array:
        if counter[x] != 0:
            counter[x] = 2
            continue
        else:
            for multiple in range(x, maximum, x):
                counter[multiple] += 1
    ans = 0
    for x in array:
        if counter[x] == 1:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
a = list(map(int, input().split()))

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

for elem in a:
    cnt[elem] += 1

unique = []

for i in range((10**6) + 1):
    if cnt[i] == 1:
        unique.append(i)

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

a = list(set(a))

for elem in a:
    for m in range(elem * 2, (10 ** 6) + 1, elem):
        cnt[m] = 1

ans = 0

for elem in unique:
    if cnt[elem] == 0:
        ans += 1

print(ans)

Solution (Python):

def main():
    import sys
    from collections import Counter
    import random
    N = int(sys.stdin.readline())
    A = list(map(int, sys.stdin.readline().split()))
    
    judge = [0 for _ in range(10**6+1)]
    A.sort()
    B = Counter(A)
    for a in A:
        judge[a] =1
    for a in A:
        if judge[a] ==1:
            if B[a] >=2:
                judge[a] = 0
            for i in range(2*a, 10**6+1, a):
                judge[i] = 0
                
    print(judge.count(1))

if __name__=='__main__':
    main()

Solution (Python):
def main():
  N=int(input())
  D=[0]*(10**6+1)
  A=sorted(map(int,input().split()))
  m=max(A)+1

  for a in A:
    if D[a]==0:
      D[a]=1
      for i in range(2*a,m,a):
        D[i]=-1
    else:
      D[a]=-1

  print(D.count(1))

main()

Solution (Python):
def main():
  N=int(input())
  D=[0]*(10**6+1)

  for a in sorted(map(int,input().split())):
    if D[a]==0:
      D[a]=1
      for i in range(2*a,10**6+1,a):
        D[i]=-1
    else:
      D[a]=-1

  print(D.count(1))

main()

Solution (Python):
n = int(input())
list_P = list(map(int, input().split()))
d = {}
q = max(list_P)

for p in list_P:
    d.setdefault(p, 0)
    d[p] += 1

list_P = set(list_P)
list_Ans = [True]*(q+1)

for p in list_P:
    if d[p] > 1:
        list_Ans[p] = False

    for i in range(2*p, q + 1, p):
        list_Ans[i] = False

ans = 0

for p in list_P:
    if list_Ans[p]:
        ans += 1

print(ans)

Solution (Python):
n=int(input())
A=list(map(int,input().split()))
A.sort()

box=[True]*(A[-1]+1)

for i in range(len(A)):
    if i<n-1 and A[i]==A[i+1]:
        box[A[i]]=False
    k=2
    while A[i]*k<len(box):
        box[A[i]*k]=False
        k+=1

ans=0
for i in A:
    if box[i]:
        ans+=1
print(ans)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
a.sort()
b = [1]*(10**6+1)
for i in range(n):
    if i + 1 < n and a[i] == a[i + 1]:
        b[a[i]] = 0
        continue
    for x in range(2*a[i], 10**6+1, a[i]):
        b[x] = 0
print(sum(b[x] for x in a))

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

mx=max(A)
f=[True]*(mx+1)
chk=[0]*(mx+1)

for a in A:
    chk[a]+=1

for a in A:
    cnt=2
    while a*cnt<=mx:
        f[a*cnt]=False
        cnt+=1
ans=0
for a in A:
    if f[a]==True and chk[a]<=1:
        ans+=1
print(ans)

Solution (Python):
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math


MOD = 10 ** 9 + 7




N = int(input())
A = list(map(int, input().split()))
A.sort()
countA = Counter(A)
maxA = A[-1]




ef = [True]*(maxA+1)
count = 0
prev = -1
for num in A:
    if num == prev:
        continue
    if ef[num] and countA[num] == 1:
        count += 1

    b = 2*num
    while b <= maxA:
        ef[b] = False
        b += num

    prev = num

print(count)

Solution (Python):
from collections import Counter

n = int(input())
a = list(map(int,input().split()))
A = list(set(a))
A.sort()
amax = A[-1]
sieve = [1]*(amax+1)
ans = []

for i in A:
  for j in range(2,amax//i + 1):
    sieve[i*j] = 0

for i in A:
  if sieve[i] == 1:
    ans.append(i)

c = Counter(a)
ansl =len(ans)

for k,v in c.items():
  if sieve[k] == 1 and v >= 2:
    ansl -= 1
    
print(ansl)

Solution (Python):
n = int(input())
A = list(map(int,input().split(" ")))
A.sort()
sieve = [True for i in range(A[-1] + 1)]
done = set()
ans = 0

for i, a in enumerate(A):
    if sieve[a] == True:
        num = 1
        while a*num <= A[-1]:
            sieve[num*a] = False
            num += 1
        if i ==len(A)-1:
            ans +=1
        elif (i < len(A) -1) and (A[i] != A[i+1]):
            ans +=1
        

print(ans)

Solution (Python):
n = input()
*A, = map(int, input().split())
max_A = max(A)
count = {a:0 for a in A}
for a in A:
    count[a] += 1
is_OK = {a:True for a in A}
for a in A:
    i = 2
    if not is_OK[a]:
        continue
    while a * i < max_A + 1:
        is_OK[a * i] = False
        i += 1
ans = 0
for a in A:
    if count[a] == 1 and is_OK[a]:
        ans += 1
print(ans)

Solution (Python):
n = int(input())
li = list(map(int,input().split()))
ans = 0
cnt_li = [0]*(10**6+1)

import math
import bisect
import collections
c = collections.Counter(li)
li = list(set(li))
li.sort()

for l in li:
    for x in range(2,10**7):
        if x*l > (10**6):
            break
        else:
            cnt_li[x*l] += 1


while len(li)>0:
    ba = li.pop(-1)
    if c[ba]>1:
        continue
    if cnt_li[ba] == 0:
        ans += 1
print(ans)

Solution (Python):
_,*a = map(int,open(0).read().split())
a.sort()
ans = 0

M = 10**6 + 1
l = [0] * (M)
ans = 0
for i in range(len(a)):
    if l[a[i]] == 0:
        l[a[i]] = 2
        ans += 1
        for x in range(a[i]*2, M, a[i]):
            l[x] = 1
    elif l[a[i]] == 2:
        ans -= 1
        l[a[i]] -= 1
print(ans)

Solution (Python):
import sys
readline = sys.stdin.readline


def main():
    N = int(readline())
    A = list(map(int, readline().rstrip().split()))
    A.sort()

    M = A[-1]
    flg = [0] * (M + 1)
    res = 0

    for a in A:
        if flg[a] == 0:
            res += 1
        if flg[a] == 2:
            res -= 1
            flg[a] = 1
        if flg[a] > 0:
            continue
        flg[a] = 2
        for i in range(2, 10**6):
            if a * i > M:
                break
            flg[a*i] = 1
    
    print(res)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
readline = sys.stdin.readline


def main():
    N = int(readline())
    A = list(map(int, readline().rstrip().split()))
    A.sort()

    M = A[-1]
    flg = [0] * (M + 1)
    res = 0

    for a in A:
        if flg[a] == 0:
            res += 1
        if flg[a] == 2:
            res -= 1
            flg[a] = 1
        if flg[a] > 0:
            continue
        flg[a] = 2
        for i in range(2, 10**6):
            if a * i > M:
                break
            flg[a*i] = 1
    
    print(res)


if __name__ == '__main__':
    main()

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

A_max = max(A)

dp = [True for i in range(A_max)]
counter = [0 for i in range(A_max)]

for a in A:
    counter[a - 1] += 1

for a in A:
    multiple = a + a
    while (multiple <= A_max):
        dp[multiple - 1] = False
        multiple = multiple + a
ans = 0

for i in A:
    if dp[i - 1] and counter[i - 1] <= 1:
        ans += 1

print(ans)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
a.sort()

table = [0] * (a[n - 1] + 1)

for i in range(n):
    p = a[i]
    for j in range(2 * p, a[n - 1] + 1, p):
        
        table[j] = 1
        
from collections import Counter
cnt = Counter(a)
ans = 0
for i in range(n):
    
    if cnt[a[i]] != 1:
        continue
    
    if table[a[i]] != 1:
        ans += 1
print(ans)

Solution (Python):
n = int(input())
a = sorted(map(int, input().split()))

cnt = [0] * (a[-1] + 1)
for i in a:
    cnt[i] += 1
for i in set(a):
    if cnt[i] >= 1:
        for j in range(i * 2, a[-1] + 1, i):
            cnt[j] = 0
print(cnt.count(1))

Solution (Python):
import sys
from collections import Counter

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

Amx = max(A)
A.sort()
As = set(A)

ca = Counter(A)
ans = 0
dp = [True] * (Amx + 1)
for a in A:
    if ca[a] <= 1 and dp[a]:
        ans += 1
    k = 1
    while k * a <= Amx:
        dp[k * a] = False
        k += 1
print(ans)

Solution (Python):
n = int(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)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
cnt = [0]*((10**6) + 1)


for elem in a:
    cnt[elem] += 1


unique = []

for i in range((10**6) + 1):
    
    if cnt[i] == 1:
        unique.append(i)


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


a = list(set(a))

for elem in a:
    for m in range(elem * 2,(10**6)+1,elem):
        cnt[m] = 1

ans = 0

for elem in unique:
    if cnt[elem] == 0:
        ans += 1
print(ans)

Solution (Python):
import math
from collections import defaultdict
def r():
    return int(input())
def rm():
    return map(int,input().split())
def rl():
    return list(map(int,input().split()))

'''D'''
n=r()
a=rl()
ma=max(a)
b=[0]*(ma+1)
a.sort()
for i in a:
    if b[i]!=0:
        b[i]+=1
        continue
    else:
        b[i]+=1
    for j in range(2*i,ma+1,i):
        b[j]+=1
ans=0
for i in a:
    if b[i]==1:
        ans+=1
print(ans)

Solution (Python):

from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase
import sys
from bisect import *
from math import floor,sqrt,ceil,factorial as F,gcd,pi,log
from itertools import chain,combinations,permutations,accumulate
from collections import Counter,defaultdict,OrderedDict,deque
from functools import cmp_to_key,reduce
INT_MAX = sys.maxsize
INT_MIN = -(sys.maxsize)-1
mod = 1000000007
ch = "abcdefghijklmnopqrstuvwxyz"
lcm = lambda a,b : (a*b)//gcd(a,b)
setbit = lambda x : bin(x)[2:].count("1")

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

def solve():
    nn = int(sys.stdin.readline())
    a = list(map(int,sys.stdin.readline().split()))
    tra = Counter(a)
    s = dict()
    n = len(a)
    max_ele = INT_MIN
    for i in range(n):
        s[a[i]] = 1
        max_ele = max(max_ele,a[i])

    res = dict()
    for i in range(n):
        if a[i] !=0 :
            for j in range(a[i]*2,max_ele+1,a[i]):
                if j in s.keys():
                    res[j]  = 1
    
    c =0
    for k,v in tra.items():
        if k not in res:
            if v == 1:
                c += 1


    print(c)




BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)


if __name__ == '__main__':
    
    
    
    
    solve()

Solution (Python):
n=int(input())
a=sorted(list(map(int,input().split())))
m=max(a)
b=[1]*m
c=[0]*m
for i in a:
  c[i-1]+=1
  if b[i-1]:
    for j in range(i*2-1,m,i):
      b[j]=0
x=0
for i in range(m):
  if b[i] and c[i]==1:
    x+=1
print(x)

Solution (Python):






def main():
    N = int(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())

Solution (Python):
n,*a=map(int,open(0).read().split())
ma=1001001
nums=[0]*ma

for q in a:
  nums[q]+=1
  if nums[q]==1:
    for j in range(2*q,ma,q):
      nums[j]+=2

cnt=0
for elem in nums:
  if elem==1:
    cnt+=1
    
print(cnt)

Solution (Python):
n,*a=map(int,open(0).read().split())
ma=1001001
nums=[0]*ma

for q in a:
  nums[q]+=1
  if nums[q]==1:
    for j in range(2*q,ma,q):
      nums[j]+=2

cnt=0
for elem in nums:
  if elem==1:
    cnt+=1
    
print(cnt)

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**6)

N=int(input().rstrip())
a=[int(i) for i in input().split()]
l=max(a)+1
cnt=[0]*l
for i in a:
    for j in range(i,l,i):cnt[j]+=1

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

Solution (Python):
import collections
N = int(input()) 
A = sorted(list(map(int, input().split())))
unique_count = collections.Counter(A)
A_count1 = []
A_unique = list(set(A))
baisu = [0]*(10**6+1)

for k,v in unique_count.items():
    if v == 1: A_count1.append(k)

for a_unique in A_unique:
    for i in range(a_unique*2,10**6+1,a_unique):
        baisu[i] = 1

ans = 0

for a_count1 in A_count1:
    if baisu[a_count1]==0: ans += 1

print(ans)

Solution (Python):
def main():
  
  

  
  

  
  
  
  if 'get_ipython' in globals(): 
    
    n = 5
    A = [24, 11, 8, 3, 16]

  else:
    
    n = int(input())
    A = list(map(int, input().split()))

  
  MAX_N = max(A)+1
  cnt = [0] * MAX_N 

  for a in A:
    for i in range(a, MAX_N, a):
      if cnt[i] <= 2: cnt[i] += 1

  ans = 0
  for a in A:
    if cnt[a] == 1: ans += 1
  print(ans)
  
main()

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
b = max(a)
che = [1 for i in range(b)]
for i in a:
    if che[i-1] == 1:
        c = b // i
        for j in range(2,c+1):
            che[i*j-1] = 0
        che[i-1] = 2
    elif che[i-1] == 2:
        che[i-1] = 0
ans = 0
for i in a:
    if che[i-1] == 2:
        ans += 1
print(ans)

Solution (Python):
from collections import Counter
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines


def main():
    N, *A = map(int, read().split())

    t = Counter(A)
    A.sort()
    table = [True] * (A[-1] + 1)
    n = len(table)

    seen = set()
    for a in A:
        if a in seen:
            continue
        for i in range(2*a, n, a):
            table[i] = False
        seen.add(a)

    ans = 0
    for k, v in t.items():
        if v > 1:
            continue
        else:
            if table[k]:
                ans += 1

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np

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

num_array = np.zeros(max(a_list)+1)
for a in a_list:
    num_array[a::a] += 1
    
count = 0
for a in a_list:
  if num_array[a] == 1:
    count += 1
print(count)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
m=max(a)
a.sort()
dp=[True]*(m+1)
h=dict()
for i in a:
    if i not in h:
        h[i]=1
    else:
        h[i]+=1
    j=2
    while j*i<=m:
        dp[i*j]=False
        j+=1
ans=0
for i in a:
    if dp[i]==True and h[i]==1:
        ans+=1
print(ans)

Solution (Python):
from collections import Counter
max_=10**6+1
ans=0

n=int(input())
data=list(map(int,input().split()))

b=[True]*(max_+1)
data.sort()
c=Counter(data)


for d in data:
    if b[d]:
        for j in range(d,max_,d):
            b[j]=False
        if c[d]==1:
            ans+=1
print(ans)

Solution (Python):
import sys
from collections import Counter
input = lambda: sys.stdin.readline().rstrip()

MAX = 1000001
dp = [True for _ in range(MAX)]
n = int(input())
a = list(map(int, input().split()))
cnt = Counter(a)
a = sorted(list(set(a)))
ans = 0
for v in a:
   if cnt[v] <= 1 and dp[v]:
      ans += 1
   m = v
   while m < MAX:
      dp[m] = False
      m += v
print(ans)

Solution (Python):
from collections import deque
import collections
import math
"""


n = 10**5
A = [int(i)+1 for i in range(10**5,0,-1)]
A.sort()
ans = 0
ans_list = []
kaburi = {}
for i in A:
    Flag = True
    for j in ans_list:
        if i==j:
            kaburi[i]=True
            Flag = False
            break
        if i%j==0:
            Flag = False
            break
    if Flag:
        ans_list.append(i)
        ans += 1
print(ans-len(kaburi))
"""


n = int(input())
A = [int(i) for i in input().split()]
A.sort()
Max = max(A)
cnt_dict = collections.Counter(A)

Dict = {a:True for a in A}
for a in A:
    times = 2
    while a*times<=Max:
        Dict[a*times]=False
        times +=1
ans = 0
for a in A:
    if cnt_dict[a]==1 and Dict[a]:
        ans +=1
print(ans)