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

N = int(input())
a = list(map(int, input().split()))
a.sort()
MAX = a[-1]
l = [0]*(MAX+1)
for i in range(N):
    l[a[i]] += 1
    
answer = 0
for i in range(N):
    if l[a[i]] == 1:
        answer += 1
    for g in range(a[i], MAX+1, a[i]):
        l[g] = 10
print(answer)

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

ans = 0
for i in range(n):
    if l[a[i]] == 1:
        ans += 1
    for g in range(a[i], MAX+1, a[i]):
        l[g] = 10

print(ans)

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

a.sort()
Max = a[-1]
memo = [1] * (Max+1)
count = 0


for i in range(n-1):
    t = a[i]
    if memo[t] == 1:
        if a[i] != a[i+1]:
            count += 1
        for j in [t*k for k in range(1, Max//t+1)]:
            memo[j] = 0

if memo[a[n-1]] == 1:
    count += 1

print(count)

""" 
a.sort(reverse=True)

count = 0

for i in range(n-1):
    if a[i] != a[i+1] and a[i] != a[i-1]:
        for j in range(n-1, i, -1):
            if a[i] % a[j] == 0:
                break
            if j == i+1:
                count += 1


if a[n-2] != a[n-1]:
    count += 1

if n != 1:
    print(count)
elif n == 1:
    print(1)
"""

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

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

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

for i in range(1, len(dp)):
    if dp[i]:
        for j in range(i+i, len(dp), i):
            dp[j] = 0
print(dp.count(1))

Solution (Python):
import sys
from collections import Counter
N = int(input())
As = list(map(int,input().split()))
ct = Counter(As)
As =sorted(As)
max_dp = As[-1] +1
dp = [True] * max_dp
for key,count in ct.items():
	if count > 1:
		dp[key] = False
		i = 2
		while key*i < max_dp:
			dp[key*i] = False
			i+=1
for A in As:
	if dp[A] == True:
		i = 2
		while A*i < max_dp:
			dp[A*i] = False
			i+=1

ans = 0

for A in As:
	
	if dp[A]:
		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()))
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):
import collections
 
n=int(input())
arr=list(map(int,input().split()))
arr=sorted(arr)
s=set()
cnt=collections.Counter(arr)
 
for i in range(n):
 if arr[i] in s:
   continue
 if cnt[arr[i]]>=2:
   s.add(arr[i])
 for j in range(2,10**6//arr[i]+1):
   s.add(arr[i]*j)
ans=0
for i in range(n):
 if arr[i] in s:
   continue
 ans+=1
 
print(ans)

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


N = int(input())
A = list(map(int, input().split()))
M = 10**6 + 5
cnt = [0] * M

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

ans = 0

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

print(ans)

Solution (Python):
import sys
from collections import defaultdict, deque, Counter










stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18

def main():
    N = int(stdin.readline().rstrip())
    
    A = list(map(int, stdin.readline().rstrip().split()))
    A.sort()
    C = Counter(A)
    cannot = set()
    L= max(A)
    ans = 0
    for a in A:
        if a in cannot: continue
        if C[a] == 1:
            ans += 1
        ind = 1
        while a*ind <= L:
            cannot.add(a*ind)
            ind += 1

    print(ans)

main()

Solution (Python):
import sys
import numpy as np


def solve(sequence):

    sequence.sort()

    max_v = sequence[-1]

    dp = [True] * (max_v + 1)

    previous = -1
    for v in sequence:
        if v == previous:
            dp[v] = False
            continue

        previous = v

        if not dp[v]:
            continue

        for iv in range(2 * v, max_v+1, v):
            dp[iv] = False

    count = 0
    for v in sequence:
        if dp[v]:
            count += 1

    return count













def main():
    _ = input()
    sequence = np.array(input().split(), np.int64)
    print(solve(sequence))


if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
An = list(map(int, input().split()))
An.sort()
max_n = max(An)
dp = [0] * (max_n + 1)
for i in range(N):
    if dp[An[i]] != 0:
        dp[An[i]] = 2
        continue
    for j in range(1, max_n//An[i] + 1):
        dp[An[i]*j] += 1
ans = 0
for a in An:
    if dp[a] == 1:
        ans += 1
print(ans)

Solution (Python):

















def solve():
    N = int(input())
    sequence = list(map(int, input().split()))

    sequence.sort()

    max_v = sequence[-1]

    dp = [True] * (max_v + 1)

    previous = -1
    for v in sequence:
        if v == previous:
            dp[v] = False
            continue

        previous = v

        if not dp[v]:
            continue

        for iv in range(2 * v, max_v+1, v):
            dp[iv] = False

    count = 0
    for v in sequence:
        if dp[v]:
            count += 1

    return count


def main():
    print(solve())


if __name__ == "__main__":
    main()

Solution (Python):
import sys
n = int(sys.stdin.readline().rstrip("\n"))
a = [int(s) for s in sys.stdin.readline().rstrip("\n").split()]
a_max = max(a)
c = {num: 0 for num in a}
for num in a:
    c[num] += 1
d = {num: 0 for num in a}
for num in a:
    t = 2
    while num * t <= a_max:
        d[num*t] = 1
        t += 1
ans = 0
for num in a:
    if c[num] == 1 and d[num] == 0:
        ans += 1
print(ans)

Solution (Python):
n = int(input())
a = [int(i) for i in input().split()]
max_a = max(a)
cnt_d = [0] * (max_a + 1)

for ai in a:
    for multi in range(ai, max_a + 1, ai):
        cnt_d[multi] += 1

print(sum(cnt_d[ai] == 1 for ai in a))

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

N = int(input())
A = list(map(int, input().split()))
C = Counter(A)
a = sorted(C.keys())
dp = [1]*(a[-1]+1)
for x in a:
    if C[x] > 1:
        dp[x] = 0
    y = x+x
    while y <= a[-1]:
        dp[y] = 0
        y += x
ans = 0
for x in a:
    ans += dp[x]
print(ans)

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

c = Counter(As)


is_ans = [True] * (10**6 + 1)
s = list(set(As))
for x in s:
  t = x * 2
  while t <= 10**6:
    is_ans[t] = False
    t += x

cnt = 0
for x in s:
  if c[x] == 1 and is_ans[x] == True:
    cnt += 1

print(cnt)

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

a_max = max(a_lst)
index_lst = [0]*(a_max + 1)

for ai in a_lst:
    for multi in range(ai, a_max+1, ai):
        index_lst[multi] += 1

ans = 0
for ai in a_lst:
    if index_lst[ai] == 1:
        ans += 1
print(ans)

Solution (Python):
from numba import njit, int32
import numpy as np


@njit(int32(int32[:], int32[:], int32[:]))
def main(A, B, C):
    ans = 0

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

    for a in C:
        v = 2*a
        while v <= 10**6:
            B[v] += 1
            v += a

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

    return ans


if __name__ == '__main__':
    N = int(input())
    A = [int(i) for i in input().split()]
    B = [0]*(10**6+1)
    ans = main(np.array(A, dtype=np.int32),
               np.array(B, dtype=np.int32),
               np.array([a for a in set(A)], dtype=np.int32))
    print(ans)

Solution (Python):
from numba import njit, int32
import numpy as np


@njit(int32(int32[:], int32[:]))
def main(A, B):
    ans = 0

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

    for a in set(A):
        v = 2*a
        while v <= 10**6:
            B[v] += 1
            v += a

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

    return ans


if __name__ == '__main__':
    N = int(input())
    A = [int(i) for i in input().split()]
    B = [0]*(10**6+1)
    ans = main(np.array(A, dtype=np.int32), np.array(B, dtype=np.int32))
    print(ans)

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

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

for ai in A:
    for multi in range(ai, a_max+1, ai):
        B[multi] += 1

ans = 0
for ai in A:
    if B[ai] == 1:
        ans += 1

print(ans)

Solution (Python):
from numba import njit
import numpy as np


@njit
def main(A, B):
    for a in A:
        B[a] += 1

    for a in set(A):
        v = 2*a
        while v <= 10**6:
            B[v] += 1
            v += a

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

    print(ans)


if __name__ == '__main__':
    N = int(input())
    A = [int(i) for i in input().split()]
    B = [0]*(10**6+1)
    main(np.array(A), np.array(B))

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

a_max = max(a)
cnt = [0] * (max(a) + 1)
ans = 0

for ai in a:
    for multi in range(ai, a_max + 1, ai):
        cnt[multi] += 1

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

print(ans)

Solution (Python):
import sys
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
INF = 1000000000000

n = I()
a = LI()

a.sort()
m = a[n-1]
flg = [False]*(m+1)

count = 0
for x in range(n):
    v = a[x]
    if(not flg[v]):
        i = v
        while(i <= m):
            flg[i] = True
            i += v
        if(x == n-1 or v != a[x+1]):
            count += 1

print(count)

Solution (Python):
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    B = [0]*(10**6+1)
    for a in A:
        B[a] += 1

    for a in set(A):
        v = 2*a
        while v <= 10**6:
            B[v] += 1
            v += a

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

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    B = [0]*(10**6+1)
    for a in A:
        B[a] += 1

    for a in set(A):
        v = 2*a
        while v <= 10**6:
            B[v] += 1
            v += a

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

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
checker = [1 for _i in range(10**6+1)]
a.sort()
a.append(-1)
result = 0
for i in range(n):
    if a[i] == a[i-1]:
        continue
    if a[i] == a[i+1]:
        checker[a[i]] = 0
    result += checker[a[i]]
    checker[a[i]] = 0
    x = 2
    while a[i]*x <= 10**6:
        checker[a[i]*x] = 0
        x += 1
print(result)

Solution (Python):


N = int(input())

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

M = max(A)

L1 = [False] * (M+1)
L2 = [0] * (M+1)

for i in A:
    if L2[i] == 1:
        L1[i] = True
    
    d = i * 2
    L2[i] = 1
    
    while d <= M:
        L1[d] = True
        d += i

count = 0

for i in A:
    if not L1[i]:
        count += 1

print("{}".format(count))

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
A.sort()
counter = 0
Amax = A[-1]
A.append(0)
dp = [True for i in range(Amax)]

for i in range(len(A)-1):
    p = A[i]
    if dp[p-1]:
        for j in range(Amax//p):
            if dp[p*(j+1)-1]:
                dp[p*(j+1)-1] = False
        if p != A[i+1]:
            counter += 1
    else:
        continue

print(counter)

Solution (Python):
from collections import Counter

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

M = 10**6

table = [1] * (M + 1)

B = Counter(a)
Key = list(B.keys())

count = 0
for x in Key:
    if B[x] == 1 and table[x] == 1:
        count += 1

    for i in range(M):
        if i * x > M:
            break
        else:
            table[i * x] = 0

print(count)

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

n = int(input())

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

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

uni = []
a = list(set(a))

for i in a:
    if c[i] == 1:
        uni.append(i)

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

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

cnt = 0
for i in uni:
    if b[i] == 0:
        cnt += 1

print(cnt)

Solution (Python):
n = int(input())

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

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

uni = []
a = list(set(a))

for i in a:
    if c[i] == 1:
        uni.append(i)

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

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

cnt = 0
for i in uni:
    if b[i] == 0:
        cnt += 1

print(cnt)

Solution (Python):
n = int(input())

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

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

uni = []
a = list(set(a))

for i in a:
    if c[i] == 1:
        uni.append(i)

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

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

cnt = 0
for i in uni:
    if b[i] == 0:
        cnt += 1

print(cnt)

Solution (Python):
from collections import Counter
n = int(input())
A = sorted(list(map(int, input().split())))
A_c = Counter(A)
A_max = A[-1]

dp = [True] * (A_max + 1)
counter = 0
for i in range(len(A) - 1):
    p = A[i]
    if dp[p] == False:
        continue
    else:
        for q in range(A_max // p + 1):
            dp[p * q] = False
        if p != A[i+1]:
            counter += 1
if dp[A_max] == True:
    counter += 1
print(counter)

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

b = [0] * (max(a) + 1)

for i in range(n):
    b[a[i]] += 1

ans = 0
for i in range(1, len(b)):
    if b[i] > 0:
        if b[i] == 1:
            ans += 1
        
        for j in range(len(b)):
            if i * j >= len(b):
                break
            b[i * j] = 0

print(ans)

Solution (Python):
n = int(input())
a = [int(i) for i in input().split()]
max_a = max(a)
cnt_d = [0] * (max_a + 1)

for ai in a:
    for multi in range(ai, max_a + 1, ai):
        cnt_d[multi] += 1

print(sum(cnt_d[ai] == 1 for ai in a))

Solution (Python):
from collections import Counter
import bisect
n = int(input()) 
a = list(map(int, input().split())) 
cnt = Counter(a) 
a.sort()
ans = 0
mx = 10 ** 6
p = [0] * (mx + 1)
for i in a:
    if p[i] == 0:
        for j in range(mx + 1):
            x = i * j
            if x > mx:
                break
            p[x] = 1 
        if cnt[i] == 1:
            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:
    if d[a] != 1:
        t[a] = False
    for i in range(a + a, 10 ** 6 + 1, a):
        t[i] = False
print(sum(1 for a in A if t[a]))

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

    ma = max(A)
    N = [0] * (10 ** 6 + 1)
    for a in A:
        for i in range(a, ma + 1, a):
            N[i] += 1

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

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
a = sorted([int(i) for i in input().split()])
max_a = max(a)
cnt_d = [0] * (max_a + 1)

for ai in a:
    for multi in range(ai, max_a + 1, ai):
        cnt_d[multi] += 1

print(sum(cnt_d[ai] == 1 for ai in a))

Solution (Python):
n = int(input())
a = sorted([int(i) for i in input().split()])
max_a = max(a)
cnt_d = [0] * (max_a + 1)

for ai in a:
    for multi in range(ai, max_a + 1, ai):
        cnt_d[multi] += 1

cnt_nd = 0
for ai in a:
    if cnt_d[ai] == 1:
        cnt_nd += 1
print(cnt_nd)

Solution (Python):
from collections import Counter

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

prime = [0 for i in range(ma)]

for a in A:
    for j in range(a, ma+1, a):
        prime[j-1] += 1

cnt = 0
for i in A:
    if(prime[i-1] == 1):
        cnt += 1
       
print(cnt)

Solution (Python):
N = int(input())
arr = sorted(list(map(int, input().split())))
count_arr = [0]*arr[-1]

ans = 0
for i in arr:
    for j in range(1,(arr[-1]//i)+1):
        count_arr[(i*j)-1] += 1
for i in arr:
    if count_arr[i-1] == 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 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):
n=int(input())
p=sorted(list(map(int,input().split())))
s=set()
m = 10**6+1
a=[True for _ in range(m)]
prev = 0
for x in p:
    if prev == x:
        s.discard(x)
        continue
    if a[x]:
        s.add(x)
    i = 2
    y = i*x
    while y<m:
        a[y] = False
        i+=1
        y = i*x
    prev=x

print(len(s))

Solution (Python):
n = int(input())
l = [int(x) for x in input().split()]
D = set() 
S = set() 
for x in l:
    if x in S:
        D.add(x)
    else:
        S.add(x)

M = max(S)
limit = M+1
mp = [0]*(limit)

cnt = 0
S = sorted(S)
for x in S:
    for y in range(x,limit,x):
        mp[y] += 1
    if(x in D):
        continue
    if(mp[x]==1):
        cnt += 1
        
print(cnt)

Solution (Python):
n = int(input())
l = [int(x) for x in input().split()]
D = set() 
S = set() 
for x in l:
    if x in S:
        D.add(x)
    else:
        S.add(x)

limit = 10**6+1
mp = [0]*(limit)

cnt = 0
S = sorted(S)
for x in S:
    for y in range(x,limit,x):
        mp[y] += 1
    if(x in D):
        continue
    if(mp[x]==1):
        cnt += 1
        
print(cnt)

Solution (Python):
n = int(input())
l = [int(x) for x in input().split()]
l.sort()
set_l = set(l)
set_l = sorted(set_l)
limit = 10**6+1
mp = [0]*(limit)
pre = None
for i in range(n):
    num = l[i]
    if(pre==num):
        mp[num] += 1
    pre = num

for x in set_l:
    for y in range(x,limit,x):
        mp[y] += 1
        

cnt = 0
for num in set_l:
    if(mp[num]==1):
        cnt += 1
print(cnt)

Solution (Python):
N = int(input())
A = [int(x) for x in input().split()]
D = set() 
S = set() 
for i in range(N):
    if A[i] in S:
        D.add(A[i])
    else:
        S.add(A[i])

M = max(S)

X = [1 for i in range(M+1)] 

for a in S:
    if a in D:
        X[a]=0 
    for i in range(2*a,M+1,a):
        X[i]=0 
        
ans = 0
for i in range(N):
    if X[A[i]]==1: 
        ans += 1
print(ans)

Solution (Python):
n = int(input())
nums = [int(e) for e in input().split()]
import numpy as np

ans= np.zeros(max(nums)+1)

for i in nums:
    if ans[i] >1:
        continue
    else:
        ans[i::i] +=1

cnt = 0
for i in nums:
    if ans[i] ==1:
        cnt +=1

print(cnt)

Solution (Python):
import numpy as np
import sys
def input(): return sys.stdin.readline().strip()

n = int(input())
As = list(map(int, input().split()))
ans = n
val = 10 ** 6
table = np.array([0] * (val + 1))
for a in As:
    if table[a] > 1:
        continue
    table[::a] += 1
for a in As:
    ans -= (table[a] > 1)
print(ans)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
a.sort()
a.append(0)
b = {}
c = 0
for i in range(n):
    if a[i] not in b:
        for j in range(1, 10**6//a[i]+1):
            b[a[i]*j] = 1
        if a[i] != a[i+1]:
            c += 1
print(c)

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

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):
'''
方針
    1 ～ 10^6(Aの最大値) までの全ての数について、割り切れる数をカウント
    カウント == 1 ならば、他の数では割り切れないので、そのような数の個数が答え

工夫
    そのままの実装では、最悪ケース : 1 1 1 1 ... で、TLEする
    対策として、
        1. Aを昇順ソートする
        2. A[i]がA[i-1]と同じならば、2倍以上の倍数についてはスキップ
    とする
'''

import numpy as np

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    d = np.zeros(A[-1]+1, dtype=np.uint64)  
    for i in range(N):
        a = A[i]
        a1 = A[i-1]
        if a != a1:     
            d[a::a] += 1    
        else:           
            d[a] += 1       
    print(np.count_nonzero(d[A] == 1))  

main()

Solution (Python):
_,*a = map(int, open(0).read().split())
a.sort()
m = -~a[-1]
c = [0]*m
for i in a:
    c[i] += 1
    if c[i] > 1:
        continue
    for j in range(i * 2, m, i):
        c[j] = 2
print(sum(c[i]==1for i in a))

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp



class UnionFindEx:
    def __init__(self, size):
        
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    
        self.roots[r2] = r1
        return True

def get_primes(n):
    ps = [2]
    for i in range(3, n, 2):
        for p in ps:
            if i%p == 0:
                break
        else:
            ps.append(i)
    return ps


Yes = 'Yes'
No = 'No'


import numpy as np
def main():
    N=ii()
    A=lmis()
    A.sort()
    d = np.zeros(A[-1]+1, dtype=np.uint8)
    for i in range(N):
        a = A[i]
        pa = A[i-1]
        if a != pa:
            d[a::a] += 1
        else:
            d[a] += 1
    print(sum(d[a]==1 for a in A))

main()

Solution (Python):



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





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

for i in A:
    if dp[i]!=0:
        dp[i]+=1
        continue
    for j in range(1*i,max+1,i):
        dp[j]+=1
        
ans=[]
for a_idx,a in enumerate(A):
    if dp[a] == 1:
        ans.append(a)
        
print(len(ans))

Solution (Python):
import collections

n=int(input())
arr=list(map(int,input().split()))
arr=sorted(arr)
s=set()
cnt=collections.Counter(arr)

for i in range(n):
 if arr[i] in s:
   continue
 if cnt[arr[i]]>=2:
   s.add(arr[i])
 for j in range(2,10**6//arr[i]+1):
   s.add(arr[i]*j)
ans=0
for i in range(n):
 if arr[i] in s:
   continue
 ans+=1

print(ans)

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

for i in range(n):
  c[a[i]] -= 1
  for j in range(a[i],(kmax+1),a[i]):
    c[j] += 2

ans=c.count(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())
lst = list(map(int, input().split()))
lst.sort()
k = lst[-1]+1
dp = [0 for i in range(k)]
ans = 0
for i in lst:
    if dp[i] == 0:
        ans += 1
        dp[i] = 2
        for j in range(i*2, k, i):
            dp[j] = 1
    elif dp[i] == 2:
        dp[i] = 1
        ans -= 1
print(ans)

Solution (Python):
N = int(input())

A = [i for i in 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())
List = list(map(int, input().split()))
res = 0
List.sort()
K = List[N-1]+1
Flag = [1]*K
for i in range(N):
  if Flag[List[i]] ==1:
    res +=1
    for j in range(List[i],K,List[i]):
      Flag[j] = 0
    if i != N-1 and List[i] == List[i+1]:
      res += -1
print(res)

Solution (Python):
from sys import stdin

import numpy as np

U = 10 ** 6 + 10


def main():
    readline = stdin.readline
    N = int(readline())
    a = list(map(int, readline().split()))
    ret = 0
    exist_counts = [0] * U
    for x in a:
        if exist_counts[x]:
            exist_counts[x] = 2
            continue
        idx = x
        while idx < U:
            exist_counts[idx] += 1
            idx += x
    for x in a:
        ret += exist_counts[x] == 1
    print(ret)
main()

Solution (Python):
from collections import Counter


n = int(input())
a = list(map(int, input().split()))
c = Counter(a) 
c = sorted(c.items(), key=lambda x:x[0]) 
ans = 0
isOK = [True] * (10**6+1)

for k, v in c:
    if not isOK[k]:
        continue

    if v > 1:
        for i in range(k, len(isOK), k):
            isOK[i] = False
        continue

    ans += 1
    for i in range(2*k, len(isOK), k):
        isOK[i] = False

print(ans)

Solution (Python):
N = int(input())
Alist = [int(x) for x in input().split()]
M = max(Alist)
A0 = ['NotUse']
Abool = A0 + [0 for x in range(M)]
Alist.sort()
ans = 0

for i in Alist:
    for j in range(i,M+1,i):
        if Abool[j] >= 2:
            None
        else:
            Abool[j] += 1
    
for i in Alist:
    if Abool[i] == 1:
        ans += 1
print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

from collections import Counter
cnt = Counter(a)

if a[0]==1:
    if cnt[1]==1:
        print(1)
    else:
        print(0)
    exit()

limit = a[-1]
is_prime = [0] * (limit + 1)

for aa in a:
    is_prime[aa]=1

for i in range(2, limit + 1):

    if is_prime[i]==0:
        continue
    for j in range(i * 2, limit + 1, i):
        is_prime[j] = 0

ans=0

for i in range(1,limit+1):
    if is_prime[i] and cnt[i] < 2:
        ans+=1

print(ans)

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

ans = [0]*(l[n-1]+1)
p=0

while(p<n):
     
    for i in range(l[p],l[n-1]+1,l[p]):
        ans[i]+=1
    p+=1
   
    

c=0

for i in l:
    if(ans[i]==1):
        c+=1
print(c)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
a.sort()
if a[0] == 1:
    if n > 1:
        if a[1] == 1:
            print(0)
            exit()
    print(1)
    exit()

p = [False for i in range(a[-1]+1)]
kaburi = set()
for i in range(n):
    if p[a[i]]:
        kaburi.add(a[i])
    p[a[i]] = True

for i in range(2,a[-1]+1):
    if not p[i]:
        continue
    for j in range(i*2,a[-1]+1,i):
        p[j] = False
ans = 0
for i in range(a[-1]+1):
    if p[i] and not i in kaburi:
        ans += 1
print(ans)

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

a.sort()
amax=a[-1]
boo = [0]*(amax+1)
from collections import Counter
c=Counter(a)

for aa in a:
    if boo[aa]==0:
        if c[aa]>=2:
            for i in range(aa,amax+1,aa):
                boo[i]=1
        else:
            for i in range(aa*2,amax+1,aa):
                boo[i]=1

print( n-sum(boo[aa] for aa in a))