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 sys, io, os, re
import bisect
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor
from copy import copy, deepcopy
from collections import deque
from fractions import gcd
from functools import reduce
from itertools import groupby

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n): return [0] * n
def array2(n, m): return [[0] * m for x in range(n)]
def array3(n, m, l): return [[[0] * l for y in xrange(m)] for x in xrange(n)]

N = n1()
A = nn()

A.sort()


max_num = A[-1]
t = array1(max_num+1)
ans = 0

for i, n in enumerate(A):
    if t[n] == 0:
        if i < len(A) - 1 and A[i] == A[i+1]:
            pass
        else:
            ans += 1

    j = n
    while j <= max_num:
        t[j] = 1
        
        j += n
    
print(ans)

Solution (Python):
from collections import Counter
def main():
    M = 10 ** 6
    _ = int(input())
    A = list(map(int,input().split()))
    erato = [True] * (M+10)
    m = sorted(Counter(A).items())
    ans = 0
    for t in m:
        if t[1] == 1 and erato[t[0]]:
            ans += 1
        for i in range(t[0],M+1,t[0]):
            erato[i] = False
            
    print(ans)


if __name__ == '__main__':
    main()

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

sortList = sorted(AList)
Amax = max(sortList)
dp = [0] * (Amax+1)

for n in sortList:
  dp[n] += 1
  if dp[n] == 1:
    for j in range(n*2, Amax+1, n):
      dp[j] += 2
print(dp.count(1))

Solution (Python):
def abc170_d():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    Amax = A[-1]
    check = [False] * (Amax + 1)
    ans = 0
    for i in range(N):
        if check[A[i]]: continue
        if not(i < N-1 and A[i] == A[i+1]): ans += 1
        k = 1
        while k*A[i] <= Amax:
            check[k*A[i]] = True
            k += 1
    print(ans)

abc170_d()

Solution (Python):
import sys
sys.setrecursionlimit(10 **5)




readline = sys.stdin.readline



def proc():
    _ = int(readline().rstrip())
    a = list(map(int, readline().rstrip().split()))

    mx = max(a) +1
    cnt = [0] * mx
    for i in a:
        if cnt[i]!=0:
            if cnt[i] == 2:
                continue
        
        for j in range(i, mx, i):
            cnt[j]+=1
    
    return sum(cnt[i] for i in a if cnt[i]==1)


print(proc())

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


mx = max(A)
x = [0] * (mx + 1) 
for i in A:
    x[i] += 1
for i in range(1, mx + 1):
    if x[i] != 0:
        for j in range(2 * i, mx + 1, i):
            x[j] = 0
    if x[i] > 1:
        x[i] = 0
print(sum(x))

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
A.sort()
MAX = max(A)+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):
import numpy as np
from collections import Counter

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

max=list[-1]
dp=[0]*(max+1)
dp=np.array(dp,int)

for num in list:
    dp[num]=1

for num in list:
    if dp[num]==1:
        dp[2*num::num]=0

count=Counter(list)

for num,cnt in count.items():
    if cnt>1:
        dp[num]=0

print(dp.sum())

Solution (Python):


def submit():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    max_a = max(a)
    sieve = [0] * (max_a + 1)

    for e in a:
        sieve[e] += 1

    if sieve[1] == 1:
        print(1) 
        return
    
    if sieve[1] > 1:
        print(0) 
        return

    
    for e in range(1, max_a + 1):
        if sieve[e] == 0:
            continue

        coef = 2
        while e * coef <= max_a:
            sieve[e * coef] = 0
            coef += 1
        
    
    ans = 0
    for e in sieve:
        if e == 1:
            ans += 1

    print(ans)


submit()

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

a.sort()

M = 1000005
cnt = [0] * M

for i in range(n):
    if cnt[a[i]] != 0:
        cnt[a[i]] = 2
        continue
    for j in range(a[i], M, a[i]):
        cnt[j] += 1

ans = 0

for i in range(n):
    if cnt[a[i]] == 1:
        ans += 1

print(ans)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
a.sort()
amax = a[-1]
isok = [True]*(amax+1)
ans = 0
if n == 1:
    print(1)
    exit()
for i in range(n):
    x = a[i]
    if isok[x]:
        if i == 0 and a[i] != a[i+1]:
            ans += 1
        elif i == n-1 and a[i] != a[i-1]:
            ans += 1
        elif a[i] != a[i+1] and a[i] != a[i-1]:
            ans += 1
        orix = x
        while x<=amax:
            isok[x]=False
            x+=orix
print(ans)

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

INF = 10**6

A.sort()
check = [False] + [True]*(INF)

setA = list(set(A))
length = len(setA)
for i in range(length):
    x = setA[i]
    for j in range(2, int(INF/x)+1):
        check[x*j] = False

prev = 0
count = 0
flag = False 
for i in range(N):
    x = A[i]
    if check[x]:
        if x != prev:
            count += 1
            flag = True
        elif flag:
            count -= 1
            flag = False
        prev = x
print(count)

Solution (Python):

import sys
import math
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import itertools
from decimal import *

input = sys.stdin.readline

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007




def main():
	N = inputInt()
	A = inputList()

	A.sort()
	zyuufuku = {}
	for i,val in enumerate(A):
		if i == 0:
			continue
		if val == A[i-1]:
			if val in zyuufuku:
				pass
			else:
				zyuufuku[val] = 1

	refd = [0 for i in range(1000000 + 1)]
	for i,val in enumerate(A):
		if val in zyuufuku:
			if zyuufuku[val] > 2:
				continue
			else:
				zyuufuku[val] += 1
		for j in range(val,1000000 + 1,val):
			refd[j] += 1

	ans = 0
	for i,val in enumerate(A):
		if val in zyuufuku:
			continue
		if refd[val] < 2:
			ans += 1

	print(ans)



if __name__ == "__main__":
	main()

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
M = max(a)+1
t=[True]*M
a.sort()
s=set(a)
pre = 0
for i in a:
    if t[i] == 0:
        continue
    if pre == i:
        t[i] = False
    for j in range(2*i,M,i):
        t[j] = False
    pre = i
ans = 0
for k in a:
    if t[k] == True:
        ans += 1

print(ans)

Solution (Python):
def func(n, a):
    mx = max(a)
    x = [0] * (mx + 1) 
    for i in a:
        x[i] += 1
    for i in range(1, mx + 1):
        if x[i] != 0:
            for j in range(2 * i, mx + 1, i):
                x[j] = 0
        if x[i] > 1:
            x[i] = 0
    print(sum(x)) 

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

Solution (Python):









import os
import sys




def main():
    _ = int(input())
    a_s = list(map(int, input().split()))
    m = max(a_s)+1
    cnt = [0 for _ in range(m)]

    for a in a_s:
        if cnt[a] != 0:
            cnt[a] = 2
            continue
        for n in range(a, m, a):
            cnt[n] += 1

    print(sum(cnt[a] for a in a_s if cnt[a]==1))


if __name__ == "__main__":
    main()

Solution (Python):
n=int(input())
l=list(map(int,input().split()))
ml=max(l)
m=[0]*(ml+1)
for i in l:
    m[i]+=1
for i in range(ml+1):
    if m[i]>=1:
        for j in range(2*i,ml+1,i):
            if m[j]>0:
                m[j]=0
                
for i in range(ml+1):
    if m[i]>=2:
        m[i]=0
print(sum(m))

Solution (Python):
N = int(input())
As = list(map(int, input().split()))
M = max(As)+1
cnt = [0 for _ in range(M)]

for A in As:
  if cnt[A] != 0:
    cnt[A] = 2
    continue
  for n in range(A, M, A): cnt[n] += 1

ans = 0
for A in As:
  if cnt[A] == 1:
    ans += 1

print(ans)

Solution (Python):
from collections import defaultdict
n=int(input())
A=sorted((map(int,input().split())))
maxA=max(A)
L=[0]*(maxA+1)
AD=defaultdict(int)
for a in A:
	L[a]=1
	AD[a]+=1
for a in A:
	if AD[a]>=2:
		L[a]=0
	for i in range(2*a,maxA+1,a):
		L[i]=0
print(sum(L))

Solution (Python):
N = int(input())
A_list = list(map(int, input().split()))
M = max(A_list)+1
cnt = [0 for _ in range(M)]

for i in A_list:
    if cnt[i] != 0:
        cnt[i] = 2
        continue
    for j in range(i, M, i): cnt[j] += 1

ans = 0
for k in A_list:
    if cnt[k] == 1: ans += 1
print(ans)

Solution (Python):

import glob
import os

bn = os.path.basename(__file__).split('.')[0]
dn = os.path.dirname(__file__).split('/')


REL_PATH = dn[len(dn)-2] + '\\' + dn[len(dn)-1] + '\\' + bn


TOP_PATH = 'C:\\AtCoder'

class Common:

    problem = []
    index = 0

    def __init__(self, rel_path):
        self.rel_path = rel_path

    def initialize(self, path):
        file = open(path)
        self.problem = file.readlines()
        self.index = 0
        return

    def input_data(self):
        try:
            IS_TEST
            self.index += 1
            return self.problem[self.index-1]

        except NameError:
            return input()

    def resolve(self):
        pass

    def exec_resolve(self):
        try:
            IS_TEST
            for path in glob.glob(TOP_PATH + '\\' + self.rel_path + '/*.txt'):
                print("Test: " + path)
                self.initialize(path)
                self.resolve()
                print("\n\n")
        except NameError:
            self.resolve()


class Solver(Common):

    def resolve(self):

        N = int(self.input_data())
        A = list(map(int, self.input_data().split()))
        A_sorted = sorted(A)

        check_list = [-1]*1000001

        for a in A:
            for i in range(a, 1000001, a):
                if i == a:
                    if check_list[i] == -1:
                        check_list[i] = 0
                    elif check_list[i] == 0:
                        check_list[i] = 1
                    else:
                        break
                    continue

                check_list[i] = 1


        result = 0
        for i in A_sorted:
            if check_list[i] < 1:
                result += 1

        print(str(result))

solver = Solver(REL_PATH)
solver.exec_resolve()

Solution (Python):

n=int(input())
a=sorted(map(int,input().split()))
m=max(a)+1
t=[0]*m
cnt=0
for i in a:
    if t[i]==0:
        cnt+=1
    elif t[i]==1:
        cnt-=1
    if t[i]<2:
        t[i]+=1
        for j in range(i*2,m,i):
            t[j]=2
print(cnt)

Solution (Python):
N = int(input())
A_list = list(map(int, input().split()))
M = max(A_list)+1
cnt = [0 for _ in range(M)]

for i in A_list:
    if cnt[i] != 0:
        cnt[i] = 2
        continue
    for j in range(i, M, i): cnt[j] += 1

ans = 0
for k in A_list:
    if cnt[k] == 1: ans += 1
print(ans)

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

m = max(a)+1
dp = [1]*m
for i in a:
  if dp[i-1] == 1:
    dp[i-1] = 2 
    for j in range(i*2, m, i):
      dp[j-1] = 0
  elif dp[i-1] == 2: 
    dp[i-1] = 0

print(sum([1 for i in a if dp[i-1]]))

Solution (Python):
n = int(input())
arr = [int(x) for x in input().split()]
d = {}
for x in arr:
  d[x] = d.get(x,0)+1

mxN = 10**6 + 1
rp = [True]*mxN

if 1 in d:
  if d[1] > 1:
    print(0)
    exit()
  else:
    print(1)
    exit()
for i in range(2,len(rp)):
  if i not in d or not rp[i]:continue
  for j in range(i+i,mxN,i):
    if j in d: rp[j] = False





for k,v in d.items():
  if v > 1:rp[k] = False

ans = sum([(1 if rp[x] else 0) for x in arr])
print(ans)

Solution (Python):

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

listA = [0] * (10**6+10)
ans = 0
for i in A:
    if listA[i] != 0:
            listA[i] = 2
            continue
    for j in range(i,10**6+10,i):
        listA[j] += 1

for i in A:
    if listA[i] == 1:
        ans += 1

print(ans)

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

n=int(input())
L=list(map(int,input().split()))
L.sort()
hb = L[-1]
dp = [-1 for i in range(hb+1)] 
for i in L:
    if dp[i]!=0:
        if dp[i]==1:
            dp[i]=0
            continue
        dp[i]=1
        for j in range(2*i,hb+1,i):
            dp[j]=0
ans=0
for i in L:
    if dp[i]==1:
        ans+=1
print(ans)

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

n=int(input())
L=list(map(int,input().split()))
L.sort()
hb = L[-1]
dp = [-1 for i in range(hb+1)] 
for i in L:
    if dp[i]!=0:
        if dp[i]==1:
            dp[i]=0
            continue
        dp[i]=1
        for j in range(2*i,hb+1,i):
            dp[j]=0
ans=0
for i in L:
    if dp[i]==1:
        ans+=1
print(ans)

Solution (Python):
n = int(input())
ints = list(map(int, input().split()))
m = max(ints)
x = [0] * m
cnt = 0

for i in ints:
    if x[i-1] >= 2:
        continue
    for j in range(m // i):

        x[i * (j + 1) - 1] += 1

for i in ints:
    if x[i - 1] == 1:
        cnt += 1

print(cnt)

Solution (Python):
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
from math import cos,sin,tan,sqrt
import cmath as cma
import copy as cp
import sys
import re
sys.setrecursionlimit(10**7)
EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf
MOD = 10**9 + 7

def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def adj(n): return [[] for _ in range(n)]

n = iinput()
a = iarr()
amax = max(a)


dp = [1 for i in range(amax+1)]
for num in a:
    for i in range(2, amax//num + 1):
        tmp = num * i
        if dp[tmp]: dp[tmp] = 0


cnt = col.Counter(a)


ans = 0
for key,val in cnt.items():
    if dp[key] and val==1: ans += 1

print(ans)

Solution (Python):
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
a.sort()
check = [True] * (a[-1] + 1)
cnt = Counter(a)

for i in range(n):
    if check[a[i]] == False:continue
    for j in range(a[i], a[-1] + 1, a[i]):
        if j == a[i]:continue
        check[j] = False

ans = 0
for i in range(n):
    if check[a[i]] and cnt[a[i]] == 1:ans += 1

print(ans)

Solution (Python):



import os
import sys
from itertools import repeat







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

    A.sort()
    max = A[N - 1]
    check = list(repeat(0, max + 1))

    for i in A:
        if check[i] != 0:
            check[i] += 1
            continue
        for j in range(i, max + 1, i):
            if check[j] == 0: check[j] += 1

    ans = 0
    for i in A:
        if check[i] == 1: ans += 1

    
    
    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
from math import cos,sin,tan,sqrt
import cmath as cma
import copy as cp
import sys
import re
sys.setrecursionlimit(10**7)
EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf
MOD = 10**9 + 7

def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def adj(n): return [[] for _ in range(n)]

n = iinput()
a = iarr()
amax = max(a)


cnt = [0 for i in range(amax+1)]
for num in a:
    for i in range(1,amax//num + 1):
        tmp = num * i
        cnt[tmp] += 1

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

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
key=max(A)+1 
B=[0]*key 
for a in A:
    for b in range(a,key,a):
        B[b]+=1 
ans=0
for a in A:
    if B[a]==1: 
        ans+=1
print(ans)

Solution (Python):
import sys

def Not_Divisible(n,p):
    maxp = max(p)
    dp = [True for _ in range(maxp+1)]
    count =[0 for _ in range(maxp+1)]
    for a in p:
        count[a]+=1
        t =2
        while a*t <= maxp:
            if dp[a*t] == True :
                dp[a*t] = False
            t+=1
    k=0
    for d in p:
        if count[d] == 1 and dp[d] == True:
            k+=1
    return k


def main():
    input = sys.stdin.readline
    
    inp1 = input().rstrip().split()
    n = int(inp1[0])

    inp2 = input().rstrip().split()
    p = tuple(map(int,inp2))
    print(Not_Divisible(n,p))


if __name__ == '__main__':
    main()

Solution (Python):
import sys

def Not_Divisible(n,p):
    maxp = max(p)
    dp = [[True,0] for _ in range(maxp+1)]
    for a in p:
        dp[a][1]+=1
        t =2
        while a*t <= maxp:
            if dp[a*t][0] == True :
                dp[a*t][0] = False
            t+=1
    k=0
    for d in p:
        if dp[d][1] == 1 and dp[d][0] == True:
            k+=1
    return k


def main():
    input = sys.stdin.readline
    
    inp1 = input().rstrip().split()
    n = int(inp1[0])

    inp2 = input().rstrip().split()
    p = tuple(map(int,inp2))
    print(Not_Divisible(n,p))


if __name__ == '__main__':
    main()

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

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

Solution (Python):
N = int(input())
A_list = list(map(int, input().split()))
M = 10**6+1
cnt = [0 for _ in range(M)]

for i in A_list:
    if cnt[i] != 0:
        cnt[i] = 2
        continue
    for j in range(i, M, i): cnt[j] += 1

ans = 0
for k in A_list:
    if cnt[k] == 1: ans += 1
print(ans)

Solution (Python):
import sys

n = int(input())
list_input = list(map(int, sys.stdin.readline().split()))

list_input.sort()


list_div = [0]*(max(list_input))

for i in list_input:
    
    a = list_div[i-1]
    
    list_div[i-1::i] = map(lambda x: x+1, list_div[i-1::i])
    if a == 1:
        pass
    else:
        
        pass

ans = 0
for i in list_input:
    if list_div[i-1] == 1:
        ans += 1

print(ans)

Solution (Python):
N = int(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
    dp[a] = 1
    for i in range(2*a, maxA+1, a):
      dp[i] = 0
ans = 0
for a in A:
  if dp[a] == 1:
    ans += 1
print(ans)

Solution (Python):
from collections import Counter


def main():
    N = int(input())
    A = list(map(int, input().split()))
    MAX = max(A)
    dp = [True] * (MAX+1)
    A.sort()
    cnt = Counter(A)
    ans = 0
    for a in A:
        if dp[a]:
            if cnt[a] == 1:
                ans += 1
            x = a
            while x <= MAX:
                dp[x] = False
                x += a
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
a.sort()
Amax = a[-1]
dp = [0]*Amax
ans = 0
for i in a:
    for j in range(i,Amax+1,i):
        dp[j-1] += 1
for i in a:
    if dp[i-1] == 1:
        ans += 1
print(ans)

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
key=max(A)+1
B=[0]*key
for a in A:
  for b in range(a,key,a):
    B[b]+=1
ans=0
for a in A:
  if B[a]==1:
    ans+=1
print(ans)

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

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
ex=[0]*1000001
for a in A:ex[a]+=1
cnt=0
for i in range(1,1000001):
    if ex[i]>0:
        for j in range(i+i,1000001,i):ex[j]=0
        if ex[i]==1:
            cnt+=1
print(cnt)

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

maxa = max(a)
l = [0] * (maxa+1)


for i in a:

    c = 1
    while True:
        if i*c >= maxa+1:
            break
        l[i*c - 1] += 1
        c += 1







ans = 0

for i in set(a):
    if l[i-1] == 1:
        ans += 1

print(ans)

Solution (Python):
n = int(input())
A = list(map(int,input().split()))
 
maxA = max(A)
ans = 0
flag = [0]*(maxA+1)
 

for a in A:
    for ax in range(a,maxA+1,a):
        flag[ax] +=1
 

for a in set(A):
    if flag[a] == 1:
        ans += 1
print(ans)

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

maxA = max(A)
ans = 0
flag = [0]*(maxA+1)


for a in A:
    for ax in range(a,maxA+1,a):
        flag[ax] +=1


for a in set(A):
    if flag[a] == 1:
        ans += 1
print(ans)

Solution (Python):
import numpy as np

N = int(input())
MAXX = 10**6 + 5
num = np.array(input().split(), np.int32)[:]
mark = np.zeros(MAXX, np.int32)

num = np.sort(num)
for n in num:
    if mark[n] < 2:
        mark[n::n] += 1

count = 0
for n in num:
    if mark[n] == 1:
        count += 1

print(count)

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

for x in s:
    t=x*2
    while t<=10**6:
        p[t]=False
        t+=x
ans=0
for x in a:
    if c[x]==1 and p[x]==True:
        ans+=1
print(ans)

Solution (Python):
from collections import Counter

def undivisible(A):
    m = max(A)
    dp = [True] * (m+1)
    A.sort()
    for a in A:
        if dp[a]:
            k = a * 2
            while k <= m:
                dp[k] = False
                k += a
    cnt = Counter(A)
    ans = 0
    for a in A:
        if dp[a] and cnt[a] == 1:
            ans += 1
    return ans

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

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

max_a = max(a)
dp = [0] * (max_a + 1)

for i in a:
    for j in range(i, max_a + 1, i):
        dp[j] += 1

out = 0
for i in a:
    if dp[i] == 1:
        out += 1

print(out)

Solution (Python):
import numpy as np
s = int(input())
l = list(map(int, input().split()))
a = np.zeros(max(l)+1,dtype=int)
n = 0
for i in l:
    a[:: i] += 1

for i in l:
    if a[i] == 1:
        n += 1
print(n)

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

a.sort()
dp = [True for i in range(a[-1]+1)]
count=0

for i in range(n):
    if dp[a[i]]:
        count+=1
        for j in range(1,n-i):
            if a[i]!=a[i+j]:
                break
            elif j==1:
                count-=1
            dp[a[i+j]]=False
        for j in range(a[i], a[-1]+1, a[i]):
            dp[j]=False
        
        
        
        
        


print(count)

Solution (Python):
import os
import heapq
import sys
import math
import operator
from collections import defaultdict
from io import BytesIO, IOBase


"""def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)"""

"""def pw(a,b):
    result=1
    while(b>0):
        if(b%2==1): result*=a
        a*=a
        b//=2
    return result"""



def inpt():
    return [int(k) for k in input().split()]


def main():
    divisor=[False]*(1000010)
    n=int(input())
    d=defaultdict(int)
    ar=inpt()
    for i in ar:
        d[i]+=1

    ar.sort()
    for i in range(n):
        if(not divisor[ar[i]]):
            temp=2*ar[i]
            while(temp<=ar[n-1]):
                divisor[temp]=True
                temp+=ar[i]
    ct=0
    for i in ar:
        if(divisor[i]==False and d[i]==1):
            ct+=1
    print(ct)













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


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np

n = int(input())
a = [int(x) for x in input().split()]

m = np.zeros(max(a)+1, dtype=int)
cnt = 0

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

Solution (Python):
n=int(input())
a=list(map(int, input().split()))
ans=0
cnt=[0]*((10**6)+1)
b=[]
for i in a:
    cnt[i]+=1
for i in range((10**6)+1):
    if cnt[i] ==1:
        b.append(i)

cnt=[0]*((10**6)+1)
for s in list(set(a)):
    for i in range(s*2,(10**6)+1,s):
        cnt[i]=1
for s in b:
    if cnt[s]==0:
        ans+=1
print(ans)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
ln = max(a) + 1
l = [0]*ln
ans = 0

for i in a:
    for j in range(i, ln, i):
        l[j] += 1

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

print(ans)

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


n = int(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 dic.keys():
  i = 2
  
  while True:
    if k * i <= upper:
      multiples.add(k * i)
      i += 1
    else:
      break

ans = 0

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

print(ans)

Solution (Python):
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
A.sort()
cnt = Counter(A)
divs = set()
for i in range(N):
  if A[i] in divs: 
    continue
  if cnt[A[i]]>=2:
    divs.add(A[i]) 
  for j in range(2, 10**6//A[i]+1):
    divs.add(A[i]*j) 
ans = 0
for i in range(N):
  if A[i] in divs:
    continue
  ans += 1
print(ans)

Solution (Python):
import numpy as np

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

non_divisible = np.ones(a[-1]+1, dtype=np.int8)
non_divisible[0] = 0
for i in range(n):
    if i != 0 and a[i] == a[i-1]:
        non_divisible[a[i]] = 0
    elif non_divisible[a[i]]:
        non_divisible[a[i]*2::a[i]] = 0

res = 0
for aa in a:
    if non_divisible[aa]:
        res += 1

print(res)

Solution (Python):
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
A.sort()
cnt = Counter(A)
divs = set()
for i in range(N):
  if A[i] in divs:
    continue
  if cnt[A[i]]>=2:
    divs.add(A[i])
  for j in range(2, 10**6//A[i]+1):
    divs.add(A[i]*j)
ans = 0
for i in range(N):
  if A[i] in divs:
    continue
  ans += 1
print(ans)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
ln = max(a) + 1
l = [0]*ln
ans = 0

for i in a:
    for j in range(i, ln, i):
        l[j] += 1

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

print(ans)

Solution (Python):
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
a.sort()
c = Counter(a)
m = max(a) + 1
dp = [False]*m
ans = 0
for ai in a:
    if dp[ai]:
        continue
    if c[ai] == 1:
        ans += 1
    for i in range(ai, m, ai):
        dp[i] = True
print(ans)

Solution (Python):
from sys import stdin

if True:

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

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

    a.sort()

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

    for i in range(n):

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

        if dp[a[i]]:

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

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

    print(ans)

Solution (Python):
from sys import stdin

if True:

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

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

    a.sort()

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

    for i in range(n):

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

        if dp[a[i]]:

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

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

    print(ans)