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 getN():
    return int(input())


def getNM():
    return map(int, input().split())


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


from collections import defaultdict, deque, Counter
from sys import exit
import math
import copy
from bisect import bisect_left, bisect_right
from heapq import *
import sys


INF = 10 ** 17
MOD = 1000000007

from fractions import *


def inverse(f):
    
    return 1 / f


def combmod(n, k, mod=MOD):
    ret = 1
    for i in range(n - k + 1, n + 1):
        ret *= i
        ret %= mod

    for i in range(1, k + 1):
        ret *= pow(i, mod - 2, mod)
        ret %= mod

    return ret

MOD = 10 ** 9 + 7
def wari(n):
    res = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            res.append(i)
            res.append(n // i)

    return res
def gcd(a, b):
    while b: a, b = b, a % b
    return a
def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1
def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g): return g
            elif isPrimeMR(n // g): return n // g
            return findFactorRho(g)
def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i*i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += 1 + i % 2
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1: ret[n] = 1
    if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
    return ret

def yaku(n):
    fac = primeFactor(n)
    
    res = [1]
    for k, v in fac.items():
        new = []
        for i in range(v+1):
            for r in res:
                new.append(r * (k**i))
        res = new
    return res
def solve():
    n = getN()
    nums = getList()
    cnt = Counter(nums)
    ans = 0
    for num in nums:
        flag = True
        
        for r in yaku(num):
            if r in cnt.keys() and (r != num or cnt[r] > 1):
                flag = False
                
                break
        if flag:
            ans += 1

    print(ans)
def main():
    n = getN()
    for _ in range(n):
        solve()


if __name__ == "__main__":
    solve()

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
a.sort()

cnt = [0]*(10**6 + 1)
lst = [True]*(10**6+1)
for i in a:
    cnt[i] += 1

ans = 0
for i in a:
    if cnt[i] == 1 and lst[i]:
        ans += 1
        j = 1
        while i*j <= 10**6:
            lst[i*j] = False
            j += 1
    elif lst[i]:
        j = 1
        while i*j <= 10**6:
            lst[i*j] = False
            j += 1

print(ans)

Solution (Python):
N = int(input())
A = [int(i) for i in input().split()]

A.sort()

check = [0]*A[-1]

ans = 0
for i in range(N):
    elem = A[i]
    if check[elem-1]==0:
        if i < N-1:
            if elem != A[i+1]:
                ans += 1 
        if i==N-1:
            ans += 1
    
    now = elem
    while now <= A[-1]:
        check[now-1] = 1
        now += elem
        
print(ans)

Solution (Python):

def main():
    from collections import Counter as ct
    n = int(input())
    s = list(map(int, input().split()))
    a = ct(s)
    a2 = sorted([i for i, j in a.items() if j == 1])
    a3 = sorted([i for i, j in a.items() if j > 1])
    s = set(s)

    ans = 0
    for i in a3:
        if i in s:
            k = i
            while k <= 10**6:
                if k in s:
                    s.remove(k)
                k += i
    for i in a2:
        if i in s:
            ans += 1
            k = i
            while k <= 10**6:
                if k in s:
                    s.remove(k)
                k += i
    print(ans)


main()

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





def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))



def main():
	n=II()
	A=LI()
	A.sort()
	A.append(10**7)
	li=[0]*(10**6+10)

	ans=0
	f=0
	for k in range(n):
		i=A[k]
		if i==A[k+1]:
			f=1
			continue
		if li[i]==0:
			if f==0:
				ans+=1
			j=1
			while i*j<10**6+5:
				li[i*j]=1
				j+=1
		f=0

	print(ans)
















if __name__ == "__main__":
	main()

Solution (Python):
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

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

L = 1000010
ps = [False] * L

cs = [0] * L
for i in range(N):
    cs[A[i]] += 1

cnt = 0
for i in range(N):
    if cs[A[i]] > 1:
        if not ps[A[i]]:
            j = A[i]
            while j < L:
                ps[j] = True
                j += A[i]
        continue
    if not ps[A[i]]:
        ps[A[i]] = True
        cnt += 1
        j = A[i] * 2
        while j < L:
            ps[j] = True
            j += A[i]

print(cnt)

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): 
	return list(map(int,input().split()))
def m(): 
	return map(int,input().split())
def onem(): 
	return int(input())
def s(x): 
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): 
	return " ".join(map(str,x))
def max2(x): 
	return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""

n = onem()

a = l()

a.sort()

aa = s(a)

ans = 0
dp = [0 for i in range(10**6+1)]
for i in range(len(aa)):
	f = 0
	if aa[i][1] != 1:
		f = 1
	elif dp[aa[i][0]] != 0:
		f = 1
	for _ in range(aa[i][0],10**6+1,aa[i][0]):
		dp[_] = 1
	if not f:
		ans += 1



print(ans)

Solution (Python):
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
"""
普通にやると、O(N^2)かかる
エラトステネスの篩でできないか？
まず、長さ10^6+1のflag配列を用意する。初期値は全部1。
Aに含まれる値以外は0にする。
で、エラトステネスの篩と同じことをする。
"""
A = Counter(A)
flags = [1]*(1000001)
for i in range(1000001):
    if i not in A:
        flags[i] = 0
ans = 0
for i in range(1000001):
    if flags[i] == 1:
        ans += 1
        for j in range(i*2,1000001,i):
            flags[j] = 0

for i in range(1000001):
    if flags[i] == 1:
        if A[i] > 1:
            ans -= 1

print(ans)

Solution (Python):
from sys import stdin, setrecursionlimit
input = stdin.buffer.readline
setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi, radians, sin, cos

MOD = 10 ** 9 + 7
INF = 10 ** 18

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

cnt = [0] * (10 ** 6 + 1)
for a in A:
    cnt[a] += 1

if cnt[1] >= 2:
    print(0)
    exit()

if cnt[1] == 1:
    print(1)
    exit()

answer = 0
for i in range(2, 10 ** 6 + 1):
    if cnt[i] == 1:
        answer += 1
    if cnt[i] == 0:
        continue
    k = 2
    while i * k <= 10 ** 6:
        cnt[i * k] = 0
        k += 1

print(answer)

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

A.sort()
A.append(-1)

dat={i:False for i in range(10**6+10)}

ans=0
for i in range(len(A)-1):
    if dat[A[i]]:
        pass
    else:
        if A[i]!=A[i+1]:
            ans+=1
        for i in range(A[i],10**6+10,A[i]):
            dat[i]=True

print(ans)

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

Solution (Python):
import math
n = int(input())
lis = list(map(int,input().split()))
ans = 0
num = [1 for i in range(10 ** 6 + 5)]
lis.sort()
for i in range(n):
  
    key = 1
    gone = 1
    if i > 0:
        if lis[i] == lis[i-1]:
            key = 0
            gone = 0
    if i < n-1:
        if lis[i] == lis[i+1]:
            key = 0
    ans += num[lis[i]] * key
    num[lis[i]] = 0
    cnt = lis[i]
    t = 1
    if gone:
        while cnt*t <= 10 ** 6:
            num[cnt*t] = 0
            t += 1
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
    N = int(input())
    number = [0] * 1000005
    A = list(map(int,input().split()))
    for a in A:
        number[a] += 1
    
    for n in range(1000005):
        if number[n] == 0:
            continue
        for k in range(n + n,1000005,n):
            if number[k] > 0:
                number[k] = -1
    ans = 0
    for a in A:
        if number[a] == 1:
            ans += 1
    print(ans)
if __name__ == '__main__':
    main()

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

lim = pow(10, 6)+3
ans = 0
judge = [False]*(lim)
index = 0
for i in range(n):
  if judge[a[i]] == True:
    continue
  if i != n-1 and a[i] == a[i+1]:
    pass
  else:
    ans += 1
  for j in range(a[i], lim, a[i]):
    judge[j] = True
print(ans)

Solution (Python):



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

    primes = set(A)
    for ind,i in enumerate(A):
        primes.difference_update(range(i*2, n+1, i))
        if ind>=1:
            if A[ind]==A[ind-1]:
                primes -= {i}
    print(len(primes))



if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter
import math
def eratos(A):
    isprime = [True for i in range(10**6+1)]
    
    
    for i in set(A):
        if isprime[i]:
            j = i + i
        while j <= 10**6:
            isprime[j] = False
            j = j + i
    return isprime        

N = int(input())
A = list(map(int, input().split()))
countA = Counter(A)
is_prime = eratos(A)
ans = 0
for ai in A:
    
    if is_prime[ai] and countA[ai] < 2:
        ans += 1
print(ans)

Solution (Python):
N = int(input())
A = [int(i) for i in input().split()]

x = [0] * (10 ** 6 + 10)
y = [0] * (10 ** 6 + 10)
for a in A :
  x[a] = 1
  y[a] += 1
  
for i in range(10 ** 6 + 1) :
  if x[i] == 0 : continue
  j = i * 2
  while j <= 10 ** 6 :
    x[j] = 0
    j += i

ret = 0
for i in range(10 ** 6 + 1) :
  if x[i] == 1 and y[i] == 1 :
    ret += 1
    
print(ret)

Solution (Python):
from collections import Counter

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

A.sort()

ans = 0
tmp = [True for i in range(A[-1] + 1)]

for i in range(N - 1):
    if tmp[A[i]]:
        if A[i + 1] != A[i]:
            ans += 1
        for j in range(A[i], A[-1] + 1, A[i]):
            tmp[j] = False
if tmp[A[-1]]:
    ans += 1
print(ans)

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))



N = I()
A = LI()

d = defaultdict(int)
for i in range(N):
    d[A[i]] += 1

b = [False]*(10**6+1)
for k in d.keys():
    if d[k]:
        b[k] = True

for i in range(10**6+1):
    if b[i]:
        for j in range(2*i,10**6+1,i):
            b[j] = False

for k in d.keys():
    if d[k] != 1:
        b[k] = False

count = 0
for i in range(10**6+1):
    if b[i]:
        count += 1

print(count)

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 sys
input=sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
d=[True]*(10**6+1)
a.sort()
ans=0
D={}
for i in a:
    if not i in D:
        D[i]=1
    else:
        D[i]+=1
for i in a:
    if not d[i]:
        continue
    if D[i]!=1:
        k=1
        while i*k<=10**6:
            d[i*k]=False
            k+=1
        continue
    ans+=1
    k = 1
    while i * k <=10 ** 6:
        d[i * k] = False
        k += 1
print(ans)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

ans = 0
lim = max(A)+1
ok = [True]*lim
checked = [False]*lim

for a in sorted(A):
    if (not checked[a]) and ok[a]:
        checked[a] = True
        for j in range(a*2, lim, a):
            ok[j] = False

cnt = Counter(A)
for a in A:
    if cnt[a] == 1 and ok[a]:
        ans += 1
print(ans)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
lis = set()
A.sort()
ans = 0
for i in range(N):
    if not A[i] in lis:
        if i == N-1:
            ans += 1
        else:
            if A[i] == A[i+1]:
                cnt = 1
                while A[i] * cnt <= int(1e6):
                    lis.add(A[i] * cnt)
                    cnt += 1
            else:
                ans += 1
                cnt = 1
                while A[i] * cnt <= int(1e6):
                    lis.add(A[i] * cnt)
                    cnt += 1
print(ans)

Solution (Python):
class Ruiseki_lr:
    """左右からの畳み込みをそれぞれ計算する"""
    def __init__(self, array, op, e):
        self.op = op
        self.e = e

        n = len(array)
        self.left = [e] * (n + 1)
        self.right = [e] * (n + 1)
        for i in range(n):
            self.left[i + 1] = self.op(self.left[i], array[i])
        for i in reversed(range(n)):
            self.right[i] = self.op(self.right[i + 1], array[i])

    def get_left(self, p):
        """区間[0, p)の畳み込み結果を返す"""
        return self.left[p]

    def get_right(self, p):
        """区間[p, n)の畳み込み結果を返す"""
        return self.right[p]

    def fold(self, p):
        """p番目を除いた区間[0, n)の畳み込み結果を返す"""
        return self.op(self.left[p], self.right[p + 1])


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

memo = {}
for i in range(n):
    if a[i] not in memo:
        memo[a[i]] = []
    memo[a[i]].append(i)

ans = [True] * n
used = set([])
for i in range(n):
    if a[i] in used:
        continue
    used.add(a[i])
    num = a[i]
    if len(memo[num]) >= 2:
        for j in memo[num]:
            ans[j] = False
    num += a[i]
    while num <= 10 ** 6:
        if num in memo:
            for j in memo[num]:
                ans[j] = False
        num += a[i]
res = 0
for i in ans:
    if i:
        res += 1
print(res)

Solution (Python):
d = [0] * (10**6 + 1)
n = int(input())
for a in map(int, input().split()):
    d[a] += 1
ans = 0
for i in range(1, 10**6 + 1):
    if d[i] == 1:
        ans += 1
    if d[i] > 0:
        for j in range(i, 10**6 + 1, i):
            d[j] = 0
print(ans)

Solution (Python):
from collections import Counter
n = int(input())
a = list(map(int,input().split()))
a.sort()
b = Counter(a)
ma = a[-1]

check = [True] * (ma+1)

ans = 0
for i in range(n):
    if check[a[i]]:
        if b[a[i]] == 1:
            ans += 1
            
        for j in range(a[i],ma+1,a[i]):
            check[j] = False
            
print(ans)

Solution (Python):
from sys import stdin

t = int(input())
nums = list(map(int, stdin.readline().split()))
nums.sort()


n = nums[-1]

is_prime = [1]*(n+1)
small = nums[0]

d = dict()
for elem in nums:
    if elem not in d:
        d[elem] = 0
    else:
        is_prime[elem] = 0



for num in nums:
    
    

    
    

    for mult in range(2*num, n+1, num):
        is_prime[mult] = 0


print(sum([is_prime[i] for i in nums]))

Solution (Python):
def solve():
    MAX = 1000001
    N = int(input())
    arr = list(map(int, input().split(" ")))
    arr.sort()
    is_ans = [True]*MAX
    ans = 0

    dup = set()
    for a in arr :
        if a in dup and is_ans[a] :
            j = a
            while j < MAX :
                is_ans[j] = False
                j += a

        dup.add(a)

    for a in arr :
        if is_ans[a]:
            ans += 1
            j = a
            while j < MAX :
                is_ans[j] = False
                j += a

    return ans

print(solve())

Solution (Python):
N=int(input())
A=sorted(map(int,input().split()))
dp=[1]*10**6
for a in A:
    if dp[a-1]==1:
        dp[a-1]=2
        for i in range(a*2,10**6+1,a):
            dp[i-1]=0
    elif dp[a-1]==2:
        dp[a-1]=0
print(sum([1 for a in A if dp[a-1]]))

Solution (Python):
import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7

N = INT()
A = LIST()
MAX = max(A)

S = set(A)
ok = [1] * (MAX+1)
for a in S:
    for x in range(a+a, MAX+1, a):
        ok[x] = 0

C = Counter(A)
for k, v in C.items():
    if v >= 2:
        ok[k] = 0

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

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

x = [False]*(10**6+1)

a.sort()
for i in range(1, n):
    if a[i] == a[i-1]:
        if x[a[i]]:
            continue
        else:
            x[a[i]] = True
            for r in range(a[i], 10 ** 6 + 1, a[i]):
                x[r] = True
ans = 0
for v in a:
    if x[v]:
        continue
    ans += 1
    for i in range(v, 10**6+1, v):
        x[i] = True

print(ans)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
S = set(A)
M = max(A)
A.sort()

pre_a = 0
for a in A:
    if a == pre_a:
        S.discard(a)
    if a in S:
        j = a * 2
        while j <= M:
            S.discard(j)
            j += a
    pre_a = a

print(len(S))

Solution (Python):
import sys
import numpy as np
from collections import Counter

sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

VALID = np.ones((10 ** 6) + 10, dtype=np.bool)

A.sort()
C = Counter(A)

multi = []
for k, v in C.items():
    if v > 1:
        multi.append(k)

for x in multi:
    VALID[x::x] = False


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

print(ans)

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

a.sort()
kouho = set(i for i in range(1, 10**6+1))
ans = 0
for i in range(n):
    ai = a[i]
    tasu = True
    if i < n-1:
        if ai == a[i+1]:
            tasu = False
    if ai not in kouho:
        continue
    while ai <= 10**6:
        if ai in kouho:
            kouho.remove(ai)
        ai += a[i]
    if tasu:
        ans += 1
print(ans)

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

a=list(map(int,input().split()))
a.sort()
checked=[0]*(a[-1]+1)
cnt=0



for j,aa in enumerate(a):
    if checked[aa]==0:
        i=1
        if j+1<len(a) and aa==a[j+1]:
            cnt+=0
        else:
            cnt+=1
        
        

        
        while aa*i<a[-1]+1:
            checked[aa*i]=1
            i+=1


print(cnt)

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

res = 0

from collections import defaultdict
D = defaultdict(int)

for i in range(N):
    D[A[i]] += 1

P = [0 for _ in range(10**6 + 1)]

for i in range(N):
    if P[A[i]]:
        continue
    if D[A[i]] == 1:
        res += 1
    for j in range(A[i], 10**6 + 1, A[i]):
        P[j] = 1

print(res)

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
A.sort()
M = 10**6+1
is_prime = [True] * (M)
is_prime[0] = False

freq = dict()
for a in A:
    if a not in freq:
        freq[a] = 1
    else:
        freq[a] += 1
if 1 in freq and freq[1]>1:
    print(0)
    exit()
for i in A:
    if not is_prime[i]:
        continue
    for cur in range(i*2, M, i):
        is_prime[cur] = False
ans = 0
for a in A:
    if is_prime[a] and freq[a]==1:
        ans += 1
print(ans)

Solution (Python):
n = int(input())
a = [int(i) for i in input().split()]
ma = max(a)
d = [0 for i in range(ma+1)]
c = 0
for i in a:
    if d[i] == 2 or d[i] == 1:
        d[i] = 1
        continue
    for j in range(2*i, ma+1, i):
        d[j] = 1
    d[i] = 2
for i in a:
    if d[i] != 1:
        
        c += 1
print(c)

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
mx = max(a)
table = [0] * (mx + 1)
for x in a: table[x] += 1

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    
    return divisors

res = set(a)

for i in range(1, mx + 1):
  if table[i] == 0: continue
  for j in range(i, mx + 1, i):
    if i == j:
      if table[j] > 1:
        res.discard(j)
      continue
    if table[j]: res.discard(j)
print(len(res))

Solution (Python):
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
from functools import lru_cache
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N = int(input())
    A = read_list()
    A.sort()

    F = [True] * (A[-1] + 1)
    for i in range(N - 1):
        if A[i] == A[i + 1]:
            F[A[i]] = False

    res = 0
    for a in A:
        if F[a]:
            res += 1
        for b in range(a, len(F), a):
            F[b] = False

    print(res)


if __name__ == "__main__":
    main()

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

Solution (Python):
N = int(input())
A = sorted(list(map(int, input().split())))
M = 1000001
D = [False]*M
ans = 0
for i, a in enumerate(A):
    if D[a]: continue
    if i==N-1 or A[i+1]>a : ans += 1
    b = a
    while b<M:
        D[b] = True
        b += a

print(ans)

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

freq = Counter(A)
if freq[1] == 1:
    print(1)
elif freq[1] >= 2:
    print(0)
else:
    bad = set()
    for k, v in freq.items():
        if v >= 2:
            bad.add(k)

    mx = max(A)

    for x in freq.keys():
        for times in range(2, 10 ** 6 + 1):
            if x * times > mx:
                break
            if x * times in freq:
                bad.add(x * times)

    count = 0
    for x in A:
        if x not in bad:
            count += 1
    print(count)

Solution (Python):
import numpy as np

N = int(input())
A = sorted(map(int, input().split()))
MAX_A = 10 ** 6
checked = np.zeros(MAX_A + 1, dtype=bool)

for i, a in enumerate(A):
    if not checked[a]:
        if i >= 1 and A[i - 1] == A[i]:
            checked[a] = True
        k = 2
        while a * k <= MAX_A:
            checked[a * k] = True
            k += 1

cnt = 0
for a in A:
    if not checked[a]:
        cnt += 1

print(cnt)

Solution (Python):
import numpy as np
n = int(input())
A = list(map(int,input().split()))
A.sort()
Amax = A[-1]

A = np.array(A)

judge = np.zeros(Amax+1,int)
judge[A]=1

for i in range(n):
    if not judge[A[i]]: continue
    if i<n-1 and A[i]==A[i+1]:
        judge[A[i]] = 0
    judge[np.arange(2,Amax//A[i]+1) * A[i]] = 0

print(judge.sum())