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):
from sys import stdin

def main():
    n=int(input())
    As=list(map(int, stdin.readline().split()))
    As.sort()
    check=[0]*(10**6+10)
    for a in As:
        count=1
        while a*count < 10**6+2 and a*count < As[-1]+1:
            if check[a*count]<2:
                check[a*count]+=1
            count+=1
    ans=0
    for a in As:
        if check[a]==1:
            ans+=1
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin

def main():
    n=int(input())
    As=list(map(int, stdin.readline().split()))
    As.sort()
    check=[0]*(10**6+10)
    for a in As:
        count=1
        while a*count < 10**6+2 and a*count < As[-1]+1:
            if check[a*count]<2:
                check[a*count]+=1
            count+=1
    ans=0
    for a in As:
        if check[a]==1:
            ans+=1
    print(ans)


if __name__ == '__main__':
    main()

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

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

from collections import Counter

n = readint()
a = sorted(readints())

c = Counter(a)
ans = 0
b = [1]*(max(c)+1)
l = max(c)

for x in c:
    if c[x]==1 and b[x]==1:
        ans += 1
    for i in range(1,l//x+1):
        b[x*i] = 0

print(ans)

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

for i,num in enumerate(A):
    if i < N-1 and A[i+1] == num:
        dp[num] = False
    else:
        for j in range(2*num, A[-1]+1, num):
            dp[j] = False

print(len([i for i in A if dp[i]]))

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

for i,num in enumerate(A):
    if i < N-1 and A[i+1] == num:
        dp[num] = False
    else:
        for j in range(2*num, A[-1]+1, num):
            dp[j] = False

print(len([i for i in A if dp[i]]))

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 = sorted(A)

limit = 10**6 + 2
A += [limit]
dp = [True] * (limit)

ans = 0
for i in range(n):
  a = A[i]
  if dp[a] and a != A[i+1]:
    ans += 1
  
  if dp[a] == False:
    continue
  for t in range(a,limit,a):    
    dp[t] = False
    t += a

print(ans)

Solution (Python):
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

import math

MAX=10**6+1

n=ni()
a=nl()

s = [0]*(MAX)

for ai in a:
  if s[ai]!=0:
    s[ai]=2
    continue
  for i in range(ai,MAX,ai):
    s[i]+=1

cnt=0
for ai in a:
  if s[ai]==1:
    cnt+=1

print(cnt)

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

for i,num in enumerate(A):
    if i < N-1 and A[i+1] == num:
        dp[num] = False
    for j in range(2*num, A[-1]+1, num):
        dp[j] = False

print(len([i for i in A if dp[i]]))

Solution (Python):
n = int(input())
L = list(map(int,input().split()))
dp = [0]*((10**6)+1000)
for i in L:
    dp[i] +=1

one = []
for i in range(10**6+1000):
    if dp[i] == 1:
        one.append(i)

dp = [0]*((10**6)+1000)
a = list(set(L))
for i in a:
    for j in range(2*i,10**6+1000,i):
        dp[j] = 1

ans = 0
for i in one:
    if dp[i] == 0:
        ans +=1
print(ans)

Solution (Python):
from collections import Counter

N = int(input())
A = [int(x) for x in input().split()]

A.sort()
C = Counter(A)
for a in A:
    if C[a] == 0: continue
    if C[a] > 1:
        C[a] = 0
    for ab in range(2 * a, A[-1] + 1, a):
        C[ab] = 0

print(sum(C.values()))

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

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

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

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

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

    for i, a in enumerate(A):
        if dp[a]:
            continue
        dp[a::a] = [True] * len(dp[a::a])
        if i < N - 1 and A[i + 1] == a:
            continue
        r += 1
    return r


print(main())

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
A.sort()
check = [0] * 1000001
res = 0
for i in range(N):
    if check[A[i]]:
        continue
    if i == N-1 or A[i] != A[i+1]:
        res += 1
    for j in range(A[i], 1000001, A[i]):
        check[j] = 1
print(res)

Solution (Python):
from collections import Counter

n = int(input())
A = list(map(int, input().split()))
c = Counter(A)
s = list(set(A))
b = [True] * (10**6+1)
for x in s:
    t = x * 2
    while t <= 10**6:
        b[t] = False
        t += x
ans = 0
for x in A:
    if c[x] == 1 and b[x]:
        ans += 1
print(ans)

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    n = I()
    mylist = list(MI())
    max_a = max(mylist)
    exclude_set = set()
    tlist = [False] * (max_a+1)
    for a in mylist:
        if tlist[a]:
            exclude_set.add(a)
        else:
            tlist[a] = True
    ans = 0
    
    for i in range(1, max_a//2 + 1):
        if not tlist[i]:
            continue
        else:
            for j in range(2*i, max_a+1, i):
                tlist[j]=False
    for i in range(len(tlist)):
        if tlist[i] and not i in exclude_set:
            ans += 1
    print(ans)
                
    

if __name__ == '__main__':
    main()

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

    A.sort()

    l=[True for _ in range(A[-1]+1)]
    
    cnt=0
    for n in range(N-1):
        if l[A[n]]==True:
            if A[n]==A[n+1]:
                l[A[n]]=False
            else:
                l[A[n]]=False
                cnt+=1
            i=1
            while i*A[n]<=A[-1]:
                l[A[n]*i]=False
                i+=1
    if l[A[N-1]]==True:
        cnt+=1
        l[A[N-1]]=False
    return cnt

if __name__=="__main__":
    print(main())

Solution (Python):
import sys

def input():
    return sys.stdin.readline().strip()

def main():

    N = int(input())
    A = sorted(list(map(int,input().split())))
    A_max = A[-1] + 1
    dp = [0] * A_max

    for i in A:
        dp[i] += 1
        if dp[i] == 1:
            for j in range(i*2,A_max,i):
                dp[j] = 2
    print(dp.count(1))

if __name__ == "__main__":
    main()

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

x = max(a)
dp = [0] * (x+1)
for ai in a:
    i = 1
    while i * ai <= x:
      dp[i * ai] += 1
      i += 1

ans = 0
for ai in a:
    if dp[ai] <= 1:
        ans += 1

print(ans)

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

x = max(a)
dp = [0] * (x+1)
for ai in a:
    i = 1
    if dp[ai] <= 2:
        while i * ai <= x:
            dp[i * ai] += 1
            i += 1

ans = 0
for ai in a:
    if dp[ai] <= 1:
        ans += 1

print(ans)

Solution (Python):

n = int(input())
a = list(map(int, input().split()))
m = max(a)
count = [0 for _ in range(m + 1)]
ans = 0

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


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

print(ans)

Solution (Python):
import sys
from collections import Counter

MAX_A = 10**6 + 5

N = int(sys.stdin.readline())
A = [int(x) for x in sys.stdin.readline().split()]


dp = [True] * MAX_A
Ac = Counter(A)

for k, v in Ac.items():
    if v > 1:
        dp[k] = False
    for n in range(2*k, MAX_A, k):
        dp[n] = False

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

print(ans)

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

x = max(a)
dp = [0] * (x+1)
for ai in a:
    i = 1
    if dp[ai] <= 2:
        while i * ai <= x:
            dp[i * ai] += 1
            i += 1

ans = 0
for ai in a:
    if dp[ai] <= 1:
        ans += 1

print(ans)

Solution (Python):
"""
考え方のポイント
・自分以外では割り切れないような数の個数を求める
　→ 数列の各項に対して〇（割り切れない）×がついていって、〇の個数を数える
・[2, 2]みたいな入力は、他の数で割り切れるようになるので、同じ数が入っていると絶対に×になる。

まずは入力が全部異なる前提で進める。
範囲内の整数からなる全て配列dを用意する。
→ 入力の数列を約数としてもつ数にチェックをしていく（Anに2が含まれていれば、2の倍数全てにチェック（+1)する）
→ チェック後にd[i]をみたとき、d[i]の約数がan中に何個存在するかが示されていることになる。（2∈Aiならd[5](=6)の値は必ず1以上になってる)
"""
N = int(input())
An = [int(i) for i in input().split()]
An.sort()
max_val = 10**6+1
d = [0] * max_val




for i in An:
    d[i] += 1
    
    
    if(d[i] == 1):
        
        
        for val in range(i*2, max_val, i):
            d[val] = 2

print(d.count(1))

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

A.sort()
dp = [True for _ in range(A[-1]+1)]

for i in range(n-1):
    if A[i] == A[i+1]:
        dp[A[i]] = False

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

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

for i in A:
    if cnt[i] != 0: 
        cnt[i] = 2 
        continue
    j = i
    while j < M:
        cnt[j] += 1
        j += i
ans = 0
for i in A:
    if cnt[i] == 1:
        ans += 1
print(ans)

Solution (Python):
def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10

    N = II()
    A = LMIIS()
    ans = 0
    count = defaultdict(int)
    for a in A:
        count[a] += 1
    A = list(set(A))
    A.sort()

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

    sup = max(A)+1
    Not_Divisible = [True] * sup
    Not_Divisible[0] = False


    for a in A:
        if Not_Divisible[a]:
            for i in range(a*2,sup,a):
                Not_Divisible[i] = False

    ans = 0
    for a in A:
        if Not_Divisible[a] and count[a] == 1:
            ans += 1

    print(ans)
            


    
main()

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
m = max(a)
y = [0] * (m + 1)
for i in a:
    x = i
    while x <= m:
        y[x] += 1
        x += i
ans = 0
for j in a:
    if y[j] == 1:
        ans += 1

print(ans)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
m = max(a)
y = [0] * (m + 1)
for i in a:
    x = i
    while x <= m:
        y[x] += 1
        x += i
ans = 0
for j in a:
    if y[j] == 1:
        ans += 1

print(ans)

Solution (Python):
n = int(input())
a = sorted(list(map(int,input().split())))
a_max = a[-1]
dp = [0]*(a_max+1)

for i in a:
    dp[i] += 1
    if dp[i] == 1:
        for j in range(i*2,a_max+1,i):
            dp[j] = 2
print(dp.count(1))

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

max_A = A[-1] + 1
ans = [0] * max_A

for i in A:
    ans[i] += 1
    if ans[i] == 1:
        for j in range(i*2, max_A, i):
            ans[j] = 2

print(ans.count(1))

Solution (Python):

from collections import Counter
def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = sorted(A)
    a = Counter(A)
    l = [0] * (10**6+1)
    v = [0] * (10**6+1)
    for i in B:
        if v[i] == 1 or l[i] == 1:
            continue
        else:
            v[i] = 1
        t = 2*i
        while t < 10**6 + 1:
            l[t] = 1
            t += i
    r = 0
    for i in A:
        if l[i] == 0 and a[i] == 1:
            r += 1
    return r
print(main())

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

x = max(a)
dp = [0] * (x+1)
for ai in a:
    i = 1
    while i * ai <= x:
        dp[i * ai] += 1
        i += 1

ans = 0
for ai in a:
    if dp[ai] <= 1:
        ans += 1

print(ans)

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

A.sort()
chk_list = [0]*(A[-1]+1)

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

for i in A:
    if chk_list[i] == 2:
        continue

    if chk_list[i] == 1:
        chk_list[i] = 2
        continue

    chk_list[i] = 1
    for j in range(i*2, A[-1]+1, i):
        chk_list[j] = 2

print(chk_list.count(1))

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

ans = 0
n = int(input())
A = list(map(int,input().split()))
B = [0] * (10**6+3)
ans = 0
A.sort()
for i in range(n):
    if (i == 0 or A[i] != A[i-1]) and (i == n-1 or A[i] != A[i+1]) and B[A[i]] == 0:
        ans += 1
    if (i == 0 or A[i] != A[i-1]):
        m = A[i]
        while m < len(B):
            B[m] = 1
            m += A[i]
print(ans)

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

x = max(a)
dp = [0] * x
for ai in a:
    i = 1
    while i * ai <= x:
        dp[i * ai - 1] += 1
        i += 1

ans = 0
for ai in a:
    if dp[ai-1] <= 1:
        ans += 1

print(ans)

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

ans = 0

check = [True] * (10 ** 6 + 1)
for i in range(N):
    a = A[i]
    if not check[a]:
        continue
    if (i >= 1 and A[i] != A[i - 1]) or i == 0:
        tmp = a
        while tmp <= 10 ** 6:
            check[tmp] = False
            tmp += a
    else:
        continue
    if i + 1 < N and A[i] == A[i + 1]:
        continue
    
    ans += 1

print (ans)

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

Solution (Python):
import sys, os, math, bisect, itertools, collections, heapq, queue
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict



sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)


MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = sorted(il())

    cnt = collections.Counter(A)
    multiple = set()
    ret = 0
    maximum = max(A)
    for a in A:
        
        if a in multiple:
            continue

        
        
        
        if cnt[a] == 1:
            ret += 1

        i = 1
        
        while a * i <= maximum:
            multiple.add(a*i)
            i += 1
    print(ret)


if __name__ == '__main__':
    main()

Solution (Python):

n = int(input())
a = list(map(int, input().split()))
m = max(a)
count = [0 for _ in range(m + 1)]
ans = 0

for i in a:
    if count[i] != 0:
        count[i] = 1
        continue
    for j in range(2 * i, m + 1, i):
        count[j] = 1
    count[i] = 2

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

print(ans)

Solution (Python):
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

import collections
N = int(input())
A = list(map(int, input().split()))
cA = collections.Counter(A)

LIM = 10 ** 6 + 1


A.sort()
dp = [1] * LIM

for i in set(A):
    s = i * 2
    while s < LIM:
        dp[s] = 0
        s += i

ans = 0

for a in A:
    
    if dp[a] and cA[a] == 1:
        
        ans += 1
print(ans)

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














M = 10**6  + 5
cnt = [0 for _ in range(M)]
for x in A:
    if cnt[x] != 0:
        cnt[x] = 2
        continue
    i = x
    while i < M:
        cnt[i] += 1
        i += x
ans = 0
for x in A:
    if cnt[x] == 1:
        ans += 1
print(ans)

Solution (Python):
def resolve():
    '''
    code here
    '''
    import collections
    N = int(input())
    A_list = [int(item) for item in input().split()]

    A_list.sort()


    dp = [0 for item in range(A_list[-1]+1)]
    for item in A_list:

        temp = item
        while temp <= A_list[-1]:
            dp[temp] += 1
            temp += item

    cnt = 0
    for item in A_list:
        if dp[item] == 1:
            cnt += 1
    print(cnt)

if __name__ == "__main__":
    resolve()

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
a.sort()
amax = a[-1]
flags = [True] * amax

prev = -1

cnt = 0
for idx in range(n):
    i = a[idx]
    if prev == i: continue
    if flags[i-1]: 
        cnt += 1
        if idx < n-1:
            if i == a[idx+1]:
                cnt -= 1
    ax = i + i
    while ax <= amax:
        flags[ax-1] = False
        ax += i
    prev = i
print(cnt)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
a.sort()
dp=[True]*a[-1]
def hantei(i):
    ans = True
    if i!=n-1:
        if a[i]==a[i+1]: ans = False
    if i!=0:
        if a[i]==a[i-1]: ans=False
    return ans
for val in set(a):
    for i in range(2*val,a[-1]+1,val): dp[i-1]=False
ans=0
for i in range(n):
    if dp[a[i]-1] and hantei(i)==1: ans+=1
print(ans)

Solution (Python):
from collections import Counter
U = 10 ** 6 + 1

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

C = Counter(A)
dp = [0] * U

ans = 0
for k in sorted(C.keys()):
    if dp[k]:
        continue
    if C[k] == 1:
        ans += 1
    for i in range(k, U, k):
        dp[i] = 1

print(ans)

Solution (Python):
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n = ii()
a = li()

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

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

single = []
for i in a:
    if cnt[i] == 1:
        single.append(i)

st = [0] * (10**6+1)
unique = list(set(a))

for i in unique:
    if st[i] >= 1:
        continue
    j = i*2
    while j <= 10**6:
        st[j] = 1
        j += i

ans = 0
for i in single:
    if st[i] == 0:
        ans += 1

print(ans)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
a.sort()
from collections import Counter
c=Counter(a)
f=[1]*(10**6+1)
ans=0
for ai in a:  
  if c[ai]==1 and f[ai]==1:ans+=1
  if f[ai]==1:
    for i in range(ai,10**6+1,ai):
      f[i]=0
print(ans)

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

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

    if N == 1:
        return 1

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

    temp = 1

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

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

    return ans


print(main())

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

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

def slove():
    n = int(input())
    A = sorted(list(map(int,input().split())))
    a_max = A[-1]+1
    B = [0] * a_max
    for value in A:
        B[value] += 1
        for i in range(value*2,a_max,value):
            B[i] += 2
    
    print(B.count(1))

if __name__ == "__main__":
    slove()

"""
import sys
input = sys.stdin.readline

def slove():
    n = int(input())
    A = list(map(int,input().split()))
    A = sorted(A)
    ans = 0
    flag = False
    while len(A) != 0:
        ans += 1
        tmp = A.pop(0)
        
        k = 0
        for i in range(len(A)):
            if A[i-k] % tmp == 0:
                if A[i-k] == tmp:
                    flag = True
                A.remove(A[i-k])
                k += 1
        if flag:
            ans -= 1
            flag = False
        
    print(ans)


if __name__ == "__main__":
    slove()
"""

Solution (Python):
from collections import Counter

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


counter = Counter(A)


A_max = max(A)
dp = {a: False for a in A}

for a in A:
    
    if counter[a] > 0:
        t = 2
        while a * t <= A_max:
            dp[a * t] = True
            t += 1

ans = 0
for a in A:
    if counter[a] == 1 and dp[a] is False:
        ans += 1

print(ans)

Solution (Python):
def main():
  N=input()
  A=sorted(map(int,input().split()))
  M=A[-1]+1
  B=[True]*M
  c=0
  x=0
  for i in A:
    if B[i]:
      if i!=c:
        for j in range(i*2,M,i):
          B[j]=False
        x+=1
        c=i
      else:
        B[i]=False
        x-=1
  print(x)
main()

Solution (Python):
import sys
import heapq
def input(): return sys.stdin.readline().strip()


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

    """
    エラトステネスの篩は脳裏に浮かんだが、
    計算量がO(NloglogN)になる理屈を分かってなかったのを丁度突かれてしまった。
    1,2,3,...に対してそれぞれの倍数が1~Nにどれだけ含まれるかのチェックは
        N + N//2 + N//3 + ... = N (1 + 1/2 + 1/3 + ...) = NlogN
    になるのがミソ。
    さらに1~Nのリストに倍数チェックをつける際に、ある数xの倍数をすべて見るとして
    xのところに既にチェックがあればその先のチェックもすでに終わっているので計算量はさらに減らせる。 
    """

    sieve = [0] * (10**6 + 1)
    for a in A:
        if sieve[a] == 2: continue 
        if sieve[a] == 1:
            sieve[a] += 1
            continue
        if sieve[a] == 0:
            num = a
            while num <= 10**6:
                sieve[num] += 1
                num += a
    ans = 0
    for a in A:
        if sieve[a] == 1: ans += 1
    print(ans)
    

if __name__ == "__main__":
    main()

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

Solution (Python):
N = int(input())
Alist = list(map(int,input().split(" ")))
Alist.sort()
Amax = Alist[-1]
dp = [1]*(Amax+1)
count = 0
for i in range(len(Alist)-1):
    p = Alist[i]
    if dp[p] == 1:
        for j in range(Amax//p+1):
            dp[p*j] = 0
        if Alist[i] != Alist[i+1]:
            count+=1
if dp[Amax] == 1:
    count += 1
print(count)

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

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
a_max = max(a)
lst = [0] * (a_max + 1)
cnt = 0
for i in a:
    if lst[i] > 1:  
        continue
    for j in range(a_max // i + 1):  
        lst[i * j] += 1
    
for i in a:
    if lst[i] == 1:
        cnt += 1
print(cnt)

Solution (Python):
import numpy as np

n = int(input())
a = list(map(int, input().split()))
a_max = max(a)
lst = [0] * (a_max + 1)
cnt = 0



for i in a:
    if lst[i] > 1:  
        continue
    for j in range(a_max // i + 1):  
        lst[i * j] += 1
    
for i in a:
    if lst[i] == 1:
        cnt += 1
print(cnt)

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

if c[1]==1:
    print(1)
elif c[1] > 1:
    print(0)
else:
    mx = 10**6+10
    ok = [True]*mx
    ans = 0
    for a in A:
        if ok[a]:
            if c[a] == 1:
                ans += 1
            for i in range(mx):
                if i*a >= mx:
                    break
                ok[i*a] = False
        else:
            continue
    print(ans)

Solution (Python):
from collections import Counter

N,*A = map(int, open(0).read().split())
As = sorted(A)
Ac = Counter(A)
m = max(A)
dp = [True] * (m+1)
ans = 0
for x in As:
    if dp[x] == True:
        for i in range(1,m//x+1):
            dp[x*i] = False
        if Ac[x] == 1:
            ans += 1
    else:
        continue
print(ans)

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

AM=max(A)+1
B=[0]*AM

for i in A:
  
  
  for j in range(i,AM,i):
    B[j]+=1
x=0
for i in A:
  if B[i]==1:
    x+=1
    
print(x)

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

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

for i in c.keys():
    j = i*2
    while j<len(dp):
        dp[j] = 0
        j += i
        
ans = 0
for i in c.keys():
    if c[i] == 1:
        if dp[i] == 1:
            ans += 1
print(ans)

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

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

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

Solution (Python):
def main():
    _ = int(input())
    A = list(map(int, input().split()))

    A.sort()
    a_max = A[-1]
    dp = [0] * (a_max + 1)

    for a in A:
        if dp[a] != 0:
            dp[a] = 2
            continue

        i = a
        while i < a_max + 1:
            dp[i] += 1
            i += a

    r = 0
    for a in A:
        if dp[a] == 1:
            r += 1

    print(r)


if __name__ == '__main__':
    main()

Solution (Python):



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

    A.sort()

    
    
    
    
    

    a_max = A[-1]
    dp = [0] * (a_max + 1)
    
    

    for a in A:
        if dp[a] != 0:
            dp[a] = 2
            continue

        i = a
        while i < a_max + 1:
            dp[i] += 1
            i += a

    r = 0
    for a in A:
        if dp[a] == 1:
            r += 1

    print(r)

    
    
    
    
    

    
    
    
    

    


if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict

def main():
    MOD = 10**9+7
    n = int(input())
    A = list(map(int,input().split()))

    A.sort()
    T = A[-1]+1

    dp = [True] * T

    d = defaultdict(int)

    for a in A:
        d[a] += 1
        if dp[a]:
            for j in range(2*a,T,a):
                dp[j] = False

    ans = 0
    
    for a in A:
        if d[a] == 1 and dp[a] == True:
            ans += 1

    print(ans)

main()

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

Solution (Python):
def main():
  N=input()
  A=sorted(map(int,input().split()))
  M=A[-1]+1
  B=[0]*M
  for i in A:
    B[i]+=1
    if B[i]==1:
      for j in range(i*2,M,i):
        B[j]=2
  print(B.count(1))
main()

Solution (Python):
def main():
  N=input()
  A=sorted(map(int,input().split()))
  M=A[-1]+1
  B=[True]*M
  c=0
  x=0
  for i in A:
    if B[i]:
      if i!=c:
        for j in range(i*2,M,i):
          B[j]=False
        x+=1
        c=i
      else:
        B[i]=False
        x-=1
  print(x)
main()

Solution (Python):
T = 10 ** 6 + 20
n = int(input())
a = [int(i) for i in input().split()]
table = [True for _ in range(T)]
a.sort()
ans = 0
for i in range(n):
    if table[a[i]]:
        for j in range(a[i], T, a[i]):
            table[j] = False
        if i + 1 < n:
            if a[i + 1] != a[i]:
                ans += 1
        elif i + 1 == n:
            ans += 1
print(ans)

Solution (Python):
n = int(input())
a = [int(i) for i in input().split()]
table = [True for _ in range(2 * (10 ** 6))]
a.sort()
ans = 0
for i in range(n):
    if table[a[i]]:
        for j in range(a[i], 2 * (10 ** 6), a[i]):
            table[j] = False
        if i + 1 < n:
            if a[i + 1] != a[i]:
                ans += 1
        elif i + 1 == n:
            ans += 1
print(ans)

Solution (Python):

N = int(input())
A = list(map(int,input().split()))
A.sort()
cnt = [0]*(10**6+1)
for i in A:
    if cnt[i]<1:
        multiple = 2
        while i*multiple <= 10**6:
            cnt[multiple*i]+=1
            multiple+=1
    cnt[i]+=1
ans = 0
for i in A:
    if cnt[i]==1:
        ans+=1
print(ans)

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

Dv = [0]*(A[-1]+1)
Ct = [0]*(A[-1]+1)

for a in A:
  Dv[a] += 1
  Ct[a] += 1
  
for a in A:
  if Dv[a] >= 2:
    Dv[a] = 1
    Ct[a] = 0

for i in range(1,A[-1]+1):
  if Dv[i] == 1:
    for j in range(2,A[-1]+1): 
      if j * i > A[-1]:
        break
      Dv[j*i] = 0
      Ct[j*i] = 0

Ct[0] = 0
ans = sum(Ct)

print(ans)