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):
def examA():
    X = LI()
    for i in range(len(X)):
        if X[i]==0:
            ans = i+1
    print(ans)
    return

def examB():
    X, Y = LI()
    ans = "No"
    for i in range(X+1):
        if i*2+(X-i)*4==Y:
            ans = "Yes"
    print(ans)
    return

def examC():
    X, N = LI()
    P = LI()
    P = set(P)
    cur = inf
    ans = -1
    for i in range(-1,102):
        if i in P:
            continue
        now = abs(i-X)
        if now<cur:
            ans = i
            cur = now
    print(ans)
    return

def examD():
    N = I()
    A = LI()
    n = max(A)
    C = set()
    D = set()
    for a in A:
        if a in D:
            C.discard(a)
            continue
        D.add(a)
        C.add(a)
    if 1 in D:
        if 1 in C:
            print(1)
        else:
            print(0)
        return
    C2 = deepcopy(C)
    for a in D:
        for i in range(2,1+n//a):
            if (i*a) in C2:
                C2.discard(i*a)
    ans = len(C2)
    print(ans)
    return

def examE():
    N, Q = LI()
    AB = [LI()for _ in range(N)]



    ans = 0
    print(ans)
    return

def examF():
    H, W, K = LI()
    x1,y1,x2,y2 = LI()
    x1 -= 1; y1 -= 1; x2 -= 1; y2 -= 1
    C = [SI()for _ in range(H)]

    def bfs_grid(h, w, s, maze):
        distance = [[inf] * w for _ in range(h)]

        def bfsg():
            queue_up = deque()
            queue_d = deque()
            queue_r = deque()
            queue_l = deque()
            queue_up.append(s)
            queue_d.append(s)
            queue_r.append(s)
            queue_l.append(s)
            distance[s[0]][s[1]] = 0
            while (len(queue_up) or len(queue_r) or len(queue_d) or len(queue_l)):
                if queue_up:
                    y, x = queue_up.popleft()
                    for k in range(1, K + 1):
                        nx, ny = x, y + k
                        if (0 <= nx < w and 0 <= ny < h and maze[ny][nx] != '@'):
                            if distance[ny][nx] <= distance[y][x] + 1:
                                continue
                            queue_r.append((ny, nx))
                            queue_l.append((ny, nx))
                            distance[ny][nx] = distance[y][x] + 1
                        else:
                            break
                        if k == K:
                            queue_up.append((ny, nx))
                if queue_d:
                    y, x = queue_d.popleft()
                    for k in range(1, K + 1):
                        nx, ny = x, y - k
                        if (0 <= nx < w and 0 <= ny < h and maze[ny][nx] != '@'):
                            if distance[ny][nx] <= distance[y][x] + 1:
                                continue
                            queue_r.append((ny, nx))
                            queue_l.append((ny, nx))
                            distance[ny][nx] = distance[y][x] + 1
                        else:
                            break
                        if k == K:
                            queue_d.append((ny, nx))
                if queue_r:
                    y, x = queue_r.popleft()
                    for k in range(1, K + 1):
                        nx, ny = x + k, y
                        if (0 <= nx < w and 0 <= ny < h and maze[ny][nx] != '@'):
                            if distance[ny][nx] <= distance[y][x] + 1:
                                continue
                            queue_up.append((ny, nx))
                            queue_d.append((ny, nx))
                            distance[ny][nx] = distance[y][x] + 1
                        else:
                            break
                        if k == K:
                            queue_r.append((ny, nx))
                if queue_l:
                    y, x = queue_l.popleft()
                    for k in range(1, K + 1):
                        nx, ny = x - k, y
                        if (0 <= nx < w and 0 <= ny < h and maze[ny][nx] != '@'):
                            if distance[ny][nx] <= distance[y][x] + 1:
                                continue
                            queue_up.append((ny, nx))
                            queue_d.append((ny, nx))
                            distance[ny][nx] = distance[y][x] + 1
                        else:
                            break
                        if k == K:
                            queue_l.append((ny, nx))

            return distance

        return bfsg()
    L = bfs_grid(H,W,(x1,y1),C)
    
    ans = L[x2][y2]
    if ans==inf:
        ans = -1
    print(ans)
    return

from decimal import Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Solution (Python):



def mp(): return map(int, input().split())
def lmp(): return list(map(int, input().split()))


n = int(input())
a = lmp()
a.sort()
cnt = 0
amax = max(a)
num = [0]*int(amax+5)
for i in range(n-1):
    if num[a[i]] == 0 and a[i] != a[i+1]:
        cnt += 1
    for j in range(a[i], len(num), a[i]):
        num[j] = 1
if num[a[-1]] == 0:
    cnt += 1


print(cnt)

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

def eratosthenes(n):
    is_prime = [True] * n
    is_prime[0] = is_prime[1] = False
    is_prime[4::2] = [False] * (n // 2 - 2)
    m = int(n**.5) + 1
    for i in range(3, m, 2):
        if is_prime[i]:
            is_prime[i*i::2*i] = [False] * ((n - i*i - 1) // (2*i) + 1)
    
    return is_prime


l = [0] * (10**6+1)
for a in A:
    l[a] += 1
ans = 0
for i in range(10**6+1):
    if l[i] == 1:
        
        ans += 1
    if l[i] >= 1:
        for j in range(i, 10**6+1, i):
            l[j] = 0
print(ans)

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

def eratosthenes(n):
    is_prime = [True] * n
    is_prime[0] = is_prime[1] = False
    is_prime[4::2] = [False] * (n // 2 - 2)
    m = int(n**.5) + 1
    for i in range(3, m, 2):
        if is_prime[i]:
            is_prime[i*i::2*i] = [False] * ((n - i*i - 1) // (2*i) + 1)
    
    return is_prime


l = [0] * (10**6+1)
for a in A:
    l[a] += 1
ans = 0
for i in range(10**6+1):
    if l[i] == 1:
        
        ans += 1
    if l[i] >= 1:
        for j in range(i, 10**6+1, i):
            l[j] = 0
print(ans)

Solution (Python):
import collections
N = int(input())
A = sorted([int(i) for i in input().split()])
maxA = A[-1]

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

C = collections.Counter(A)
cand = set(A)

ans = 0
for i in range(N):
    if C[A[i]] >= 2:
        cand -= set([A[i]*j for j in range(1, maxA//A[i]+1)])
        continue

    if A[i] in cand:
        ans += 1
        cand -= set([A[i]*j for j in range(1, maxA//A[i]+1)])
print(ans)

Solution (Python):

import sys

stdin = sys.stdin
ns = lambda: stdin.readline().rstrip() 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))


def BinarySearch(num, List):
    if len(List) == 0:
        print("Erorr : list has no element")
        return
    left,right = 0,len(List)
    while left < right:
        mid  = (left+right)//2
        if num < List[mid]:
            right = mid
        else:
            left = mid + 1
    return right


def main():
    n = ni()
    a = sorted(na())
    asub = [i for i in a]

    for i in range(n):
        ai = a[i]
        right = BinarySearch(ai, a)
        if right-1 != i:
            asub[right-1] = -1
            asub[i] = -1
            continue
        cnt = 2
        while right != n:
            right = BinarySearch(ai*cnt, a)
            if asub[right-1] == ai*cnt:
                asub[right-1] = -1
            cnt += 1
    
    ans = 0
    for i in range(n):
        if asub[i] != -1:
            ans += 1
    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
def factor(N):
    arr=[]
    for i in range(1,int(N**0.5)+1):
        if(N%i==0):
            arr.append(i)
            if(N//i!=i):
                arr.append(N//i)
    return arr

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

cnt=[0]*1000001
for i in range(N):
    cnt[A[i]]+=1
ng=set()
for i in range(N):
    if cnt[A[i]]>1:
        ng.add(A[i])

s=set(A)
min_=min(A)

ans=0
for i in reversed(range(N)):
    if A[i] in ng:
        continue
    if A[i]<min_*2:
        ans+=1
        continue
    s.remove(A[i])
    arr=factor(A[i])
    ok=True
    for x in arr:
        if x in s:
            ok=False
            break
    if ok:
        ans+=1
    s.add(A[i])
print(ans)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
S = set()
T = set()
def counter(array):
    from collections import Counter
    return Counter(array)
c = counter(A)
for x in A:
    S.add(x)
    T.add(x)
cnt = 0
maxi = max(S)
for x in sorted(S):
    i = 2
    while x * i <= maxi:
        if x * i in T:
            T.remove(x*i)
        i += 1
ans = 0
for x in T:
    if c[x] == 1:
        ans += 1
print(ans)

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

if 1 in sa:
    if sa[1]>1:
        print(0)
    else:
        print(1)
    exit()









ans=0
for ai in sa:
    if sa[ai]>1:
        continue
    
    ans+=1
    if ai%2==0:
        for i in range(2,min(int(ai**(1/2)+7),ai)):
            if ai%i==0:
                if i in sa or ai//i in sa:
                    ans-=1
                    break
    else:
        for i in range(3,min(int(ai**(1/2)+7),ai),2):
            if ai%i==0:
                if i in sa or ai//i in sa:
                    ans-=1
                    break
print(ans)

Solution (Python):
def solve():
	n = int(input())
	arr = list(map(int,input().split()))
	dic = {}
	for i in arr:
		if i not in dic:
			dic[i]=1
		else:
			dic[i]+=1
	arr.sort()
	ele = arr[n-1]
	count = [0]*(ele+1)
	for i in arr:
		mul = i
		k=2
		if dic[i]>1:
			count[i]=1
		while mul*k<=ele:
			if mul*k in dic:
				count[mul*k]+=1
			k+=1
	ans=0
	for i in range(0,n):
		if count[arr[i]]==0:
			ans+=1
		
		
	print(ans)
	


if __name__ == "__main__":
	solve()

Solution (Python):
from math import floor,ceil,sqrt
import fractions
from collections import deque
import itertools
from collections import deque
import collections
import heapq
N=int(input())
A=list(map(int,input().split()))
A.sort()
nums={}
for i in range(N):
    if nums.get(A[i])==None:
        nums[A[i]]=1
    else:
        nums[A[i]]=nums[A[i]]+1

for i in range(len(A)):
    if nums[A[i]]!=0:
        for j in range(A[i]*2,10**6+1,A[i]):
            if nums.get(j)!=None:
                nums[j]=0
    if nums[A[i]]!=1:
        nums[A[i]]=0
ans=0
for i in range(len(A)):
    if nums[A[i]]==1:
        ans=ans+1
print(ans)

Solution (Python):
from collections import Counter
def main():
    n = int(input())
    A = list(map(int, input().split()))
    A.sort()
    p = set()
    no_count = set([k for k, v in Counter(A).items() if v >= 2])
    ans = 0
    for a in A:
        if a not in p:
            b = a
            while b <= A[-1]:
                p.add(b)
                b += a
            if a not in no_count:
                ans += 1
    print(ans)





if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter

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

c = Counter(a)
nu = {k for k, v in c.items() if v > 1}

s = set()
u = set()
for aa in a:
    m = 2
    if aa in s or aa in u:
        continue
    u.add(aa)
    while aa*m <= mx:
        s.add(aa*m)
        m += 1

o = 0
for aa in a:
    if aa in s or aa in nu:
        continue
    o += 1

print(o)

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

a.sort()

is_divisible = [-1] * (10 ** 6 + 1)
is_divisible[0] = 1

ans = 0
for num in a:
    if is_divisible[num] == -1:
        ans += 1
        is_divisible[num] = 0
        for i in range(num * 2, 10 ** 6 + 1, num):
            is_divisible[i] = 1
    elif is_divisible[num] == 0:
        ans -= 1
        is_divisible[num] = 1
    else:
        continue

print(ans)

Solution (Python):
import collections

n = int(input())
d = list(map(int, input().strip().split()))

counts = collections.Counter(d)
dic = {a: True for a, c in counts.items()}

keys = sorted(dic.keys())
last = keys[-1]

for k in keys:
    if dic[k]:
        n = 2
        while k * n <= last:
            if k * n in dic:
                dic[k * n] = False
            n += 1
    
    if counts[k] > 1:
        dic[k] = False

count = len([True for v in dic.values() if v])
print(count)

Solution (Python):
import collections
n = map(int, raw_input().split(' '))
ais = map(int, raw_input().split(' '))
cc = collections.Counter(ais)
ais.sort()
m = max(ais)
p = [True for _ in range(m + 1)]

count = 0
for ai in ais:
	if p[ai] is True:
		x = 2 * ai
	 	while(x < len(p)): 
	 		p[x] = False
	 		x += ai
for ai in ais:
	if p[ai] is True:
		if cc[ai] == 1:
			count +=1
print count

Solution (Python):
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
cntA = Counter(A)

A.sort()
V = set()

ans = 0
mx = max(A)
for a in A:
    if a in V:
        continue
    if cntA[a] == 1:
        ans += 1

    p = a
    while p <= mx:
        V.add(p)
        p += a

print(ans)

Solution (Python):
from sys import stdin
from copy import deepcopy
from functools import reduce
from fractions import gcd
import math
import itertools
from collections import Counter
from itertools import chain  
from heapq import heappush, heappop
import bisect


"""
N = int(input())
A, B = map(int,input().split())
A = list(map(int,input().split())) 
A = [int(input()) for _ in range(N)] 
lst = [list(map(int,input().split())) for i in range(M)] 
"""


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


if N == 1:
  print(1)
  exit()
elif N > 1 and A[0] == 1:
  if A[1] == 1:
    print(0)
    exit()
  else:
    print(1)
    exit()
elif A[0] == A[-1]:
  print(0)
  exit()


MAXINT = int(1e6)

lst = [False for _ in range(MAXINT+1)]
for i in range(N):
  lst[A[i]] = True

pre = 0
for i in range(N):
  
  if lst[A[i]]:
    if A[i] == pre:
      lst[A[i]] = False
      continue
    else:
      pre = A[i]
      j = 2 * A[i]
      while j <= MAXINT:
        lst[j] = False
        j += A[i]
    

solver = [i for i in range(MAXINT+1) if lst[i]]
ans = len(solver)
print(ans)

Solution (Python):
n,x=int(input()),10**6+100
a,b,c=list(map(int,input().split())),[0]*(2*x),0
for i in a:
    b[i]+=1
for i in range(x):
    c+=1 if b[i]==1 else 0
    if b[i]==0:
        continue
    for j in range(1,x):
        if i*j>=x:
            break
        b[i*j]=0
print(c)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
A.sort()
t = max(A)
K = [1]*(t+1)
before = -1
for i in A:
    if K[i] == 1:
        c = 2
        while(True):
            if i*c > t:
                break
            K[i*c] = 0
            c += 1
    if i == before:
        K[i] = 0
    before = i

ans = 0
for i in A:
    ans += K[i]
print(ans)

Solution (Python):
from collections import Counter
N=int(input())
A=sorted(list(map(int,input().split())))
c=Counter(A)
if 1 in A:
    if c[1]==1:
        print(1)
    else:
        print(0)
    exit()
n=max(A)
ans=[0]*(n+1)
for k,v in c.items():
    if v==1:
        ans[k]=1
for i in c.keys():
    t=i*2
    while t<=n:
        ans[t]=0
        t+=i
print(sum(ans))

Solution (Python):
import sys

sys.setrecursionlimit(1000000)

import bisect
import math
import collections
import heapq


def prime_factors(n):
    c = collections.Counter()
    while n > 1:
        for i in range(2, n + 1):
            if n % i == 0:
                c.update([i])
                n //= i
                break
    return c

def solve(N, As):
    As.sort()
    k = As[-1]
    data = [True for _ in range(k + 1)]
    count = collections.Counter(As)
    if count[1] >= 2:
        return 0

    ans = []
    done = set()
    for a in As:
        if count[a] == 1 and data[a]:
            ans.append(a)
        if a not in done:
            for n in range(a, len(data), a):
                data[n] = False
        if a == 1:
            break
    return len(ans)









































def dummy(N, R=100):
    import random
    return [random.randint(1, R) for _ in range(N)]

def slow_solve(N, As):
    ans = 0
    for i, a in enumerate(As):
        if all(i == j or a % b != 0 for j, b in enumerate(As)):
            ans += 1
    return ans























if __name__ == "__main__":
    N = int(input())
    As = list(map(int, input().split(" ")))

    print(solve(N, As))

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
cnt = 0
d = [0]*(10**6+1)
a.sort()
for i in range(n):
    if d[a[i]]: continue
    cnt += 1
    if i != n-1 and a[i] == a[i+1]:
        cnt -= 1
    res = a[i]
    while res <= 10**6:
        d[res] = 1
        res += a[i]
print(cnt)

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

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

Solution (Python):
import math

n=int(input())
A=list(map(int,input().split()))
A.sort()
m=10**6+10
C=[0]*m
C[0]=-1
ans=0
now=0
flag=0
for a in A:
    if now!=a:
        flag=0
        now=a
    if now==a and flag:
        flag=0
        ans-=1
        continue
    if C[a]==0:
        ans+=1
        flag=1
        j=a
        while j<m:
            C[j]=1
            j+=a

print(ans)

Solution (Python):

def main():

    import collections

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

    max_A = max(A_s)

    
    CNT_A = collections.Counter(A_s).most_common()
    CNT_A.sort()

    NG_list = [True for i in range(max_A)]
    cnt = 0

    
    for i in range(len(CNT_A)):
        counter = CNT_A[i][1]
        num = CNT_A[i][0]
        

        index_num = num - 1

        if (counter > 1):
            NG_list[index_num] = False
            

        if (NG_list[index_num] == True):
            cnt += 1
            NG_list[index_num] = False

        coef = 1
        while (True):
            coef += 1
            tmp_num = coef * num
            
            if (tmp_num <= max_A):
                NG_list[tmp_num - 1] = False
            else:
                break

    print(cnt)


if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
M=max(a)
num=[0]*M
for x in a:
	num[x-1]+=1
for i in range(M):
	if num[i]>=2:
		num[i]=2
ret=num.copy()
for i in range(M):
	if num[i]:
		j=i+i+1
		while j<M:
			ret[j]=0 
			j+=i+1
	if num[i]==2:
		ret[i]=0
print(ret.count(1))

Solution (Python):


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

ma = max(A)
first = [0]*(ma+3)
seen = [False]*(ma+3)
seens = set()
for i in range(N):
    a = A[i]
    if first[a] == 0:
        seens.add(a)
        ans += 1
        for j in range(a, ma + 3, a):
            first[j] += 1
    elif first[a] == 1 and (a in seens):
        ans -= 1
        first[a] += 1
    else:
        first[a] += 1

    
    
    
    
    
    

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import Counter
def main():
    N = int(input())
    A = list(map(int, input().split()))
    cnt = Counter(A)
    A.sort()
    ans = set()
    table = {i:-1 for i in range(1, 10 ** 6 + 1)}
    for a in A:
        table[a] = 0
    for a in A:
        if table[a] == 0 and cnt[a] == 1:
            ans.add(a)
        elif table[a] == 1:
            continue
        i = 2
        target = a
        while True:
            target = a * i
            if target > A[-1]:
                break
            if table[target] == 0:
                table[target] = 1
            i += 1
    print(len(ans))
if __name__ == "__main__":
    main()

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

max_num = max(a)

if a.count(1) == 1:
    print(1)
    exit()
if a.count(1) >= 2:
    print(0)
    exit()
a.sort()
d = {}

ans = 0



for i in range(n):
    if a[i] not in d.keys():
        ans += 1
        j = 1
        
        while(a[i]*j <= max_num):
            if j == 1:
                d[a[i]*j] = 1
            else:
                
                
                d[a[i]*j] = 0
            j += 1
    else:
        if d[a[i]] == 1:
            ans -= 1
            d[a[i]] = 2

print(ans)

Solution (Python):
def main():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    answer = n
    chk = [0 for _ in range(a[-1] + 1)]
    for aa in a:
        chk[aa] += 1
    if a[0] == 1:
        answer = 0 if chk[1] - 1 else 1
    else:
        for i in range(a[-1] + 1):
            if chk[i]:
                if chk[i] - 1:
                    answer -= chk[i]
                for j in range(2 * i, a[-1] + 1, i):
                    answer -= chk[j]
                    chk[j] = 0
        answer = max(answer, 0)
    print(answer)


if __name__ == '__main__':
    main()

Solution (Python):
if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))
    a = sorted(a)

    huru = [False] * (10 ** 6 + 1)
    visited = [False] * (10 ** 6 + 1)
    for i in range(n):
        if huru[a[i]]:
            continue

        if visited[a[i]]:
            huru[a[i]] = True
        tmp = a[i] * 2
        while tmp <= 10 ** 6:
            huru[tmp] = True
            tmp += a[i]
        visited[a[i]] = True

    ans = 0
    for i in range(n):
        if not huru[a[i]]:
            ans += 1
    print(ans)

Solution (Python):
import collections
from collections import defaultdict
n= int(input())
a= list(map(int, input().split()))
d=defaultdict(int)
v=[0]*(pow(10,6)+1)
a.sort()
ans=0
for i in a:
    d[i]+=1

for i in a:
    if v[i]==0:
        if d[i]==1:
            ans+=1
        x = pow(10, 6) // i
        for j in range(1,x + 1):
            v[i*j]=1
print(ans)

Solution (Python):
n = int(input())
A = sorted(map(int, input().split()))
used = set()

U = A[-1]+1
is_prime = [1]*U
cnt = [0]*U
depri = 0
for a in A:
    cnt[a] += 1
    if cnt[a] == 2 and is_prime[a]:
        depri += 1
    if is_prime[a]:
        used.add(a)
        for q in range(2*a, U, a):
            is_prime[q] = 0
print(len(used)-depri)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
A.sort()
d = {}
n = A[-1]
def makePrimeChecker(n):
    isPrime = [True] * (n + 1)
    i = 0
    for j in A:
        if i == j:
            isPrime[i] = False
            continue
        i = j
        if isPrime[i]:
            for j in range(i * 2, n + 1, i):
                isPrime[j] = False
    return isPrime
P = makePrimeChecker(n)
i = 0
ans = 0
for j in A:
    if i == j:
        continue
    else:
        i = j
        if P[i]:
            ans += 1
print(ans)

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

if __name__ == '__main__':
    main()

Solution (Python):
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))

from collections import Counter

n = ii()
A = iil()
di = Counter(A)
A.sort()

ans = 0
l = set()
for item in A:
    if di[item] > 1:
        if item not in l:
            for i in range(1,1000000//item+1):
                l.add(item*i)
        continue
    if item not in l:
        for i in range(1,1000000//item+1):
            l.add(item*i)
        ans += 1
print(ans)

Solution (Python):

MOD=10**9+7
INT_MAX=10**20+7
def INPUT():return list(int(i) for i in input().split())
def LIST_1D_ARRAY(n):return [False for _ in range(n)]
def LIST_2D_ARRAY(m,n):return [[0 for _ in range(n)]for _ in range(m)]

n=int(input())
A=INPUT()
C=LIST_1D_ARRAY(10**6+1)
count=[0]*(10**6+1)
for i in range(n):
    C[A[i]]=True
    count[A[i]]+=1
for i in range(1,10**6+1):
    if C[i]==True:
        for j in range(2*i,10**6+1,i):
            C[j]=False
ans=0
for i in range(1,10**6+1):
    if C[i]==True and count[i]==1:
        ans+=1
print(ans)

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
As=[0]*(10**6 + 1)
for i in range(N): 
    As[A[i]]+=1
count=N
for i in range(1,10**6 + 1):
    if As[i]:
        for j in range(i*2,10**6 + 1,i):
            if As[j]:
                count-=As[j]
                As[j]=0
for i in range(1,10**6 + 1):
    if As[i]>1:
        count-=As[i]
print(count)

Solution (Python):
from collections import defaultdict

N = int(input())
arr1 = [int(i) for i in input().split()]
arr = []
Dict = defaultdict(int)
for i in range(N):
    Dict[arr1[i]] += 1
arr = list(Dict.keys())
n = int(10 ** 6)
prime = [True for i in range(n + 10)]
for p in arr:
    if prime[p]:
        start = p+p
        for j in range(start, n + 1, p):
            prime[j] = False
count = 0
for i in arr:
    if prime[i] and Dict[i] == 1:
        count += 1
print(count)

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")

INF = float("inf")


N = int(input())
A = list(map(int,input().split()))
A.sort()
if N == 1:
    print(1)
else:
    is_prime = [True]*(10**6+1)
    is_prime[0] = False
    old = -1
    for i in range(N):
        a = A[i]
        if old == a:
            is_prime[a] = False
            continue
        if not is_prime[a]:
            old = a
            continue
        else:
            old = a
            if a*2 <= 10**6:
                for j in range(a*2,10**6+1,a):
                    is_prime[j] = False
                
    ans = 0
    for i in range(N):
        a = A[i]
        if is_prime[a] == True:
            ans += 1
    print(ans)

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

d = {}
for a in A:
    d.setdefault(a, 0)
    d[a] += 1

A = sorted(set(A))
t = [True] * (10 ** 6 + 1)

for a in A:
    for i in range(a + a, 10 ** 6 + 1, a):
        t[i] = False

for a in d:
    if d[a] > 1:
        t[a] = False

result = 0
for a in A:
    if t[a]:
        result += 1
print(result)

Solution (Python):
n=int(input())
l=list(map(int,input().split()))
c=0
d={}
f=[0]*(max(l)+1)
for i in l:
	if i in d:
		d[i]+=1
	else:
		d[i]=1
x=sorted(list(set(l)))
for i in x:
	if d[i]==1 and f[i]==0:
		c+=1
	for j in range(2*i,len(f),i):
		f[j]=1 

print(c)

Solution (Python):
def d_not_divisible():
    from collections import Counter
    N = int(input())
    A = [int(i) for i in input().split()]

    a_max = max(A)
    appear = [0] * (a_max + 1)
    for a in A:
        appear[a] += 1
    count = 0
    for j in range(1, a_max + 1):
        if appear[j] == 0:
            continue
        if appear[j] == 1:
            count += 1
        for k in range(j * 2, a_max + 1, j):
            if appear[k] != 0:
                appear[k] = 0
    return count

print(d_not_divisible())

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=0
b=list()
for i in range(10**6+1):
    b.append(0)
for i in range(n):
    if b[a[i]]==0:
        j=1
        while j*a[i]<=10**6:
            b[j*a[i]]=1
            j+=1
        if (i==n-1 or a[i+1]!=a[i]):
            ans+=1
print(ans)

Solution (Python):
n = int(input())
a = [int(i) for i in input().split()]

a.sort()

MAXN = a[-1]


divisors = [False for _ in range(MAXN + 1)]
answer = 0
apast = None
for i, ai in enumerate(a):
    if ai == apast:
        is_good = False
    elif i < n - 1 and ai == a[i + 1]:
        is_good = False
        m = 1
        while m * ai <= MAXN:
            divisors[m * ai] = True
            m += 1
    else:
        is_good = not divisors[ai]

        m = 1
        while m * ai <= MAXN:
            divisors[m * ai] = True
            m += 1

    if is_good:
        answer += 1

    apast = ai


print(answer)