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 collections import deque
import collections
import math
"""


n = 10**5
A = [int(i)+1 for i in range(10**5,0,-1)]
A.sort()
ans = 0
ans_list = []
kaburi = {}
for i in A:
    Flag = True
    for j in ans_list:
        if i==j:
            kaburi[i]=True
            Flag = False
            break
        if i%j==0:
            Flag = False
            break
    if Flag:
        ans_list.append(i)
        ans += 1
print(ans-len(kaburi))
"""


n = int(input())
A = [int(i) for i in input().split()]
Max = max(A)
cnt_dict = collections.Counter(A)

Dict = {a:True for a in A}
for a in A:
    times = 2
    while a*times<=Max:
        Dict[a*times]=False
        times +=1
ans = 0
for a in A:
    if cnt_dict[a]==1 and Dict[a]:
        ans +=1
print(ans)

Solution (Python):

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




A.sort()
Amax = max(A)

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):
from collections import Counter
max_=10**6+1
ans=0

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

b=[True]*(max_+1)
data.sort()
c=Counter(data)

for d in data:
    if b[d]:
        for j in range(d,max_,d):
            b[j]=False
        if c[d]==1:
            ans+=1
print(ans)

Solution (Python):

from sys import stdin

def main():
    from collections import defaultdict
    input = stdin.readline

    n = int(input())
    a = sorted(list(map(int, input().split())))
    p = defaultdict(int)
    for x in a:
        p[x] += 1
    q = a[-1] + 1
    f = [True] * (q)
    for k, v in p.items():
        if v > 1:
            f[k] = False
        for i in range(k + k, q, k):
            f[i] = False
    print(sum(1 for x in a if f[x]))
main()

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 sys
import collections
input = lambda: sys.stdin.readline().rstrip()

def main():
    n = int(input())
    a = sorted([int(i) for i in input().split()])
    cnt_list = collections.Counter(a)
    search_list = [0] * (a[-1]+1)
    ans = 0
    for num, cnt in cnt_list.items():
        search_list[num] = cnt
    for i in a:
        if search_list[i] == 1:
            ans += 1
        for j in range(i, a[-1]+1, i):
            search_list[j] = 0
    print(ans)
    
if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
A=list(map(int,input().split()))
A.sort()
M=10**6+1
cnt=[0]*M
for i in A:
    if cnt[i]!=0:
        cnt[i]=2
        continue
    for j in range(i,M,i):
        cnt[j]+=1
ans=0
for i in A:
    if cnt[i]==1:
        ans+=1
print(ans)

Solution (Python):

import sys

def solve(N: int, A: "List[int]"):
    max_a = max(A)
    arr = [0] * (max_a + 1)
    for a in A:
        arr[a] += 1

    counter = 0
    for x in range(1,max_a+1):
        if arr[x] == 1:
            counter += 1
        if arr[x]:
            for j in range(x*2,max_a+1,x):
                arr[j] = 0
    print(counter)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    A = [int(next(tokens)) for _ in range(N)]  
    solve(N, A)

if __name__ == '__main__':
    main()

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

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

    ans = 0
    from collections import Counter
    cnt = Counter(a)
    lim = max(a) + 1
    tmp = [0] * (lim)
    
    
    a.sort()

    for aa in a:
        if tmp[aa] == 0:
            for j in range(aa,lim,aa):

                tmp[j] = 1

            if cnt[aa] == 1:
                
                ans += 1




    print(ans)

if __name__=='__main__':
    main()

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

    ans = 0
    from collections import Counter
    cnt = Counter(a)
    lim = max(a) + 1
    tmp = [0] * (lim)
    
    
    a.sort()

    for aa in a:
        if tmp[aa] == 0:
            for j in range(lim):
                if aa * j > lim-1:
                    break
                tmp[aa*j] = 1

            if cnt[aa] == 1:
                
                ans += 1




    print(ans)

if __name__=='__main__':
    main()

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 a in A:
    if P[a]==0:
        for i in range(MX+1):
            x = a*i
            if x > MX:
                break
            P[x] = 1
        if cnt[a]==1:
            ans+=1
print (ans)

Solution (Python):
M = 10 ** 6 + 5
N = int(input())
A = list(map(int, input().split()))

cnt = [0] * M
for i in A:
    if(cnt[i] >= 2):
        continue
    for j in range(i, M, i):
        cnt[j] += 1
ans = 0
for i in A:
    if(cnt[i] == 1):
        ans += 1
print(ans)

Solution (Python):
def solve(n, a):
    ub = max(a) + 1
    a = sorted(a)
    matched = [False] * ub
    for x in a:
        matched[x] = True
    for x in a:
        if matched[x]:
            for y in range(2*x, ub, x):
                matched[y] = False
    for i in range(n-1):
        if a[i] == a[i+1]:
            matched[a[i]] = False
    return sum(matched)

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

Solution (Python):
N = 5
ARR = [24, 11, 8, 3, 16]


N = 4
ARR = [5, 5, 5, 5]


N = 10
ARR = [33, 18, 45, 28, 8, 19, 89, 86, 2, 4]

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

def calculate(n, arr):

    prr = [0 for i in range(2000005)]

    for i in range(n):
        start = arr[i]
        
        if prr[start] > 0:
            prr[start] = 2
            continue

        for j in range(start, 2000005, start):
            prr[j] = prr[j] + 1


    result = 0
    for i in range(n):
        start = arr[i]
        if prr[start] == 1:
            result += 1


    print(result)

calculate(N, ARR)

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

counts = [0 for i in range(Amax+1)]

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

count = 0
for i in range(1, Amax+1):
    if counts[i] == 1:
        count += 1
    if counts[i]:
        for j in range(i*2, Amax+1, i):
            counts[j] = 0
print(count)

Solution (Python):
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
prime = [True] * (10 ** 6 + 10)
 
b = sorted(set(a))
 
for i in b:
    num = i * 2
    while True:
        if num >= 10 ** 6 + 10:
            break
        prime[num] = False
        num += i
 
ans = 0
for s in a:
    if prime[s] == True and c[s] == 1:
        ans += 1
 
print(ans)

Solution (Python):
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
prime = [True] * (10 ** 6 + 10)
 
b = sorted(set(a))
 
for i in b:
    num = i * 2
    while True:
        if num >= 10 ** 6 + 1:
            break
        prime[num] = False
        num += i
 
ans = 0
for s in a:
    if prime[s] == True and c[s] == 1:
        ans += 1
 
print(ans)

Solution (Python):

import sys
import math
sys.setrecursionlimit(10**8)


def eratosthenes_sieve(n):
    table = [0] * (n + 1)
    prime_list = []

    for i in range(2, n + 1):
        if table[i] == 0:
            prime_list.append(i)
            for j in range(i + i, n + 1, i):
                table[j] = 1

    return prime_list


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

    ans = 0
    m = max(A)
    zeta = [0]*(m+1)
    for a in A:
        zeta[a] += 1

    
    primes = eratosthenes_sieve(m)
    
    for p in primes:
        for i in range(1, m//p+1):
            zeta[p*i] += zeta[i]

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

    
    
    

    return


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
ans = 0
A = list(map(int,input().rstrip().split(" ")))
A.sort()
A2 = [True for i in range(A[-1] + 1)]
for i in range(len(A)):
    k = A[i] * 2
    if A2[A[i]]:
        if i != 0 and A[i-1] == A[i]:
            A2[A[i]] = False
        while(k < len(A2)):
            A2[k] = False
            k += A[i]
for i in A:
    if A2[i]:
        ans += 1
print(ans)

Solution (Python):
N = 1000001
a = [0]* N
input()
for x in input().split():
  a[int(x)] += 1
for i in range(1, N):
  if a[i]:
    for j in range(i + i, N, i):
      a[j] = 0
print(a.count(1))

Solution (Python):



from math import *
from copy import *					
from heapq import *					
from string import *				
from random import *				
from bisect import *				
from sys import stdin				
from sys import maxsize				
from operator import *				
from itertools import *				
from decimal import Decimal 		
from collections import Counter		
from collections import defaultdict 

'''
5
24 11 8 3 16
'''

def solve(l):
	n = len(l)
	l.sort()
	maxx,ans = max(l),0
	cancel,p = [0]*(maxx+1),[0]*(maxx+1)
	for i in l:
		p[i] += 1
	for i in l:
		for j in range(2*i,maxx+1,i):
			cancel[j] = 1
	for i in l:
		if(p[i] == 1 and not cancel[i]):
			ans += 1
	return ans

N = int(stdin.readline())
l = list(map(int, stdin.readline().rstrip().split()))
ans = solve(l)
print(ans)

Solution (Python):
N = 1000001
a = [0]* N
input()
for x in input().split():
  a[int(x)] += 1
for i in range(1, N):
  if a[i]:
    for j in range(i + i, N, i):
      a[j] = 0
print(a.count(1))

Solution (Python):
N = 1000001
a = [0]* 1000001
input()
for x in input().split():
  a[int(x)] += 1
for i in range(1, N):
  if a[i]:
    for j in range(i + i, N, i):
      a[j] = 0
print(a.count(1))

Solution (Python):
a = [0]* 1000001
m = 0
input()
for x in map(int, input().split()):
  m = max(m, x)
  a[x] += 1
m += 1
for i in range(1, m):
  if a[i]:
    for j in range(i + i, m, i):
      a[j] = 0
print(a[:m].count(1))

Solution (Python):
a = [0]* 1000001
m = 0
input()
for x in map(int, input().split()):
  m = max(m, x)
  a[x] += 1
m += 1
for i in range(1, m):
  if a[i]:
    for j in range(i + i, m, i):
      a[j] = 0
print(a.count(1))

Solution (Python):
a = [0]* 1000001
m = 0
input()
for x in map(int, input().split()):
  m = max(m, x)
  a[x] += 1
m += 1
for i in range(1, m):
  if a[i]:
    for j in range(i + i, m, i):
      a[j] = 0
print(a.count(1))

Solution (Python):
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy

if __name__ == "__main__":
    n = int(input())
    a = sorted(list(map(int,input().split())))
    M = 1000005
    m = max(a)
    dp = [0]*(m+1)
    for i in range(n):
        if dp[a[i]] != 0:
            dp[a[i]] = 2
            continue
        for j in range(a[i],m+1,a[i]):
            dp[j]+=1
    cnt = 0
    for i in range(n):
        if dp[a[i]] == 1:
            cnt+=1
    print(cnt)

Solution (Python):
n  = int(input())
li = list(map(int,input().split()))
ok = set()
ng = set()
mul = set()

ans = 0

for i in li:
    if i not in ok:
        ok.add(i)
    else:
        ng.add(i)

M = max(ok)

for i in ok:
    for j in range(2,M+1):
        if i*j > 10**6:
            break
        else:
            mul.add(i*j)

for i in ok:
    if i not in mul:
        if i not in ng:
            ans+=1

print(ans)

Solution (Python):
n  = int(input())
li = list(map(int,input().split()))
ok = set()
ng = set()
mul = set()

ans = 0

for i in li:
    if i not in ok:
        ok.add(i)
    else:
        ng.add(i)

for i in ok:
    for j in range(2,10**6):
        if i*j > 10**6:
            break
        else:
            mul.add(i*j)

for i in ok:
    if i not in mul:
        if i not in ng:
            ans+=1

print(ans)

Solution (Python):
N = 1000001
a = [0]* N
input()
for x in input().split():
  a[int(x)] += 1
for i in range(1, N):
  if a[i]:
    for j in range(i + i, N, i):
      a[j] = 0
print(a.count(1))

Solution (Python):
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy

if __name__ == "__main__":
    n = int(input())
    a = sorted(list(map(int,input().split())))
    M = 1000005
    dp = [0]*(M)
    for i in range(n):
        if dp[a[i]] != 0:
            dp[a[i]] = 2
            continue
        for j in range(a[i],M,a[i]):
            dp[j]+=1
    cnt = 0
    for i in range(n):
        if dp[a[i]] == 1:
            cnt+=1
    print(cnt)

Solution (Python):
N = 1000001
a = [0]* N
input()
for x in input().split():
  a[int(x)] += 1
for i in range(1, N):
  if a[i]:
    for j in range(i + i, N, i):
      a[j] = 0
print(a.count(1))

Solution (Python):
N = 1000001
a = [0]* N
_, s = open(0)
for x in s.split():
  a[int(x)] += 1
for i in range(1, N):
  if a[i]:
    for j in range(i + i, N, i):
      a[j] = 0
print(a.count(1))

Solution (Python):
N = 1000001
a = [0]* N
_, s = open(0)
for x in s.split():
  a[int(x)] += 1
for i in range(1, N):
  for j in range(i + i, N, i):
    if a[i]:
      a[j] = 0
print(a.count(1))

Solution (Python):
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
import math

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())
rlf = lambda: map(float, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def main():
	n = int(rl())
	A = list(rli())
	indices = defaultdict(lambda: [])
	Amax = NINF
	if 1 in indices:
		print(1 if len(indices[1]) == 1 else 0)
		return
	A.sort()	
	for i, num in enumerate(A):
		indices[num].append(i)
		Amax = max(Amax, num)
	set_false = set()
	dp = [1 for _ in range(n)]
	for i, num in enumerate(A):
		if i in set_false: continue
		if len(indices[num]) > 1:
			dp[i] = 0
		curr = num
		while curr <= Amax:
			for j in indices[curr]:
				if i == j: continue
				dp[j] = 0
				set_false.add(j)
			curr += num
	print(sum(dp))
	stdout.close()

if __name__ == "__main__":
	main()

Solution (Python):
from collections import Counter
n = int(input())
a = [int(v) for v in input().split()]
 
M = max(a)
d = [1 for i in range(M+1)]
for v in sorted(a):
    for j in range(2*v, M+1, v):
        d[j] = 0
ans = 0
c = Counter(a)
for i in a:
    if c[i]==1:
      ans += d[i]
print(ans)

Solution (Python):
N = int(input())
arr = list(map(int, input().split()))
arr.sort()
ma = max(arr)
check = [True]*(ma+1)
cnt = [0]*(ma+1)
for i in arr:
    cnt[i] += 1
ans = 0
for i in arr:
    if not check[i]:
        continue
    for k in range(i,ma+1,i):
        check[k] = False
    if cnt[i] <= 1:
        ans += 1
print(ans)

Solution (Python):
from sys import stdin,stdout
from collections import Counter
n=int(stdin.readline())
a=sorted(map(int,stdin.readline().split()))
d=Counter(a)
m1=max(a);ans=0
vis=[0]*(m1+1)
for v in a:
    if not vis[v]:
        if d[v]==1:ans+=1
        for mul in range(v,m1+1,v):
            vis[mul]=1
stdout.write(str(ans))

Solution (Python):
c=[0]*8**7
for a in[*open(0)][1].split():c[int(a)]+=1
i=r=0
for t in c:
 if t:c[::i]=[0]*-(-8**7//i)
 i+=1;r+=t==1
print(r)

Solution (Python):
c=[0]*8**7
for a in[*open(0)][1].split():c[int(a)]+=1
i=r=0
for t in c:
 if t:c[::i]=[0]*-(-8**7//i)
 i+=1;r+=t==1
print(r)

Solution (Python):
c=[0]*8**7
for a in[*open(0)][1].split():c[int(a)]+=1
i=r=0
for t in c:
 r+=t==1
 if t:c[::i]=[0]*-(-8**7//i)
 i+=1
print(r)

Solution (Python):
m=8**7
c=[0]*m
for a in[*open(0)][1].split():c[int(a)]+=1
i=r=0
while~i+m:
 i+=1;r+=c[i]==1
 if c[i]:c[::i]=[0]*-(-m//i)
print(r)

Solution (Python):
m=8**7
c=[0]*m
for a in[*open(0)][1].split():c[int(a)]+=1
i=r=0
while~i+m:
 i+=1;r+=c[i]==1
 if c[i]:c[::i]=[0]*-(-m//i)
print(r)

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

Solution (Python):
from collections import Counter
import math

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

a.sort()

is_prime = [True]*(10**6 + 1)

is_prime[0] = False

maxA = max(a)

for i in set(a):
    for j in range(2 * i, maxA+1, i):
        is_prime[j] = False

result = 0
c = Counter(a)

for e in set(a):
        if is_prime[e] and c[e] == 1:
    
             result += 1

print(result)

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

m=1000000
c=[0]*(m+1)

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

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

Solution (Python):
_,*l=map(int,open(0).read().split())
a=[0]*6**8
for i in l:
  if a[i]<1:
    for j in range(i*2,6**8,i): a[j]=2
  a[i]+=1
print(a.count(1))

Solution (Python):
M=10**6+1
_,*l=map(int,open(0).read().split())
a=[0]*M
for i in l:
  if a[i]<1:
    for j in range(i*2,M,i): a[j]=2
  a[i]+=1
print(a.count(1))

Solution (Python):
M=10**6+1
_,*l=map(int,open(0).read().split())
a=[0]*M
for i in l:
  if a[i]<2:
    for j in range(i,M,i): a[j]+=2
    a[i]-=1
print(a.count(1))

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]

from itertools import count
from collections import Counter

def test():
    n = int(input())
    a = sorted([int(i) for i in input().split()])
    mxn = a[-1]
    c = Counter(a)
    a = sorted(list(set(a)))
    r = dict()
    for i in a:
        for j in count(1):
            if i * j > mxn: break
            r[i * j] = r.get(i * j, 0) + 1
    print(len([k for k in a if r[k] == 1 and c[k] == 1]))


test()

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

dic = {}
dup = set()
for a in A:
    if a in dic:
        dic[a] += 1
        dup.add(a)
    else:
        dic[a] = 1

A_max = max(A)
A_set = set(dic.keys())

cnt = 0
for a in A:
    if a not in A_set:
        continue

    cnt1 = 2
    x = a * cnt1
    while x <= A_max:
        if x in A_set:
            A_set.remove(x)

        cnt1 += 1
        x = a * cnt1

A_set = A_set - dup

print(len(A_set))

Solution (Python):
M=10**6+1
_,*l=map(int,open(0).read().split())
a=[0]*M
for i in l:
  a[i]+=1
  if a[i]==1:
    for j in range(2*i,M,i): a[j]=2
print(a.count(1))

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

dic = {}
dup = set()
for a in A:
    if a in dic:
        dic[a] += 1
        dup.add(a)
    else:
        dic[a] = 1

A_max = max(A)
A.sort()
A_set = set(dic.keys())

cnt = 0
for a in A:
    if a not in A_set:
        continue

    cnt1 = 2
    x = a * cnt1

    while x <= A_max:
        if x in A_set:
            A_set.remove(x)

        cnt1 += 1
        x = a * cnt1


A_set = A_set - dup

print(len(A_set))

Solution (Python):
M=10**6+1
_,*l=map(int,open(0).read().split())
a=[0]*M
for i in sorted(l):
  if a[i]: a[i]=2; continue
  for j in range(i,M,i): a[j]+=1
print(sum(a[i]==1 for i in l))

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 i in range(elem*2,(10**6)+1,elem):
        cnt[i]+=1

ans=0
for elem in unique:
    if cnt[elem]==0:
        ans+=1

print(ans)

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

D = [0]*(10**6+1)
for i in A:
    
    D[i] += 1

U = []
for i in range(10**6+1):
    
    if D[i] == 1:
        U.append(i)

A = list(set(A))

T = [0]*(10**6+1)
for i in A:
    
    for j in range(2*i, 10**6+1, i):
        T[j] = 1


ans = 0
for i in U:
    if T[i] == 0:
        ans += 1

print(ans)

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):
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 a in A:
    if P[a]==0:
        for i in range(MX+1):
            x = a*i
            if x > MX:
                break
            P[x] = 1
        if cnt[a]==1:
            ans+=1
print (ans)

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

dp = [0] * (mx+1)
for i in a:
    if dp[i] == 1:
        continue
    j = 2
    while i * j <= mx:
        dp[i*j] = 1
        j += 1

cnt = 0
for i in set(a):
    if dp[i] == 0 and c[i] == 1:
        cnt += 1

print(cnt)

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

m = max(A)
l = [1 for i in range(m+1)]
for v in sorted(A):
    for j in range(2*v, m+1, v):
        l[j] = 0

ans = 0
c = Counter(A)
for a in A:
    if c[a] > 1:continue
    ans += l[a]
print(ans)

Solution (Python):
from collections import Counter

N, *A = map(int, open(0).read().split())

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

dp = Counter()
for a in A:
    dp[a] += 1
    if dp[a] == 1:
        dp.update({k : 2 for k in range(2 * a, lim, a)})

print(len([0 for k, v in dp.items() if v == 1]))

Solution (Python):

2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

	

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 a in A:
    if P[a]==0:
        for i in range(MX+1):
            x = a*i
            if x > MX:
                break
            P[x] = 1
        if cnt[a]==1:
            ans+=1
print (ans)

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

    A_dict = {}
    for a in A:
        if a in A_dict.keys():
            A_dict[a] += 1
        else:
            A_dict[a] = 1

    A_list = sorted(A_dict.keys())
    limit = A_list[-1]

    sieve = {i: True for i in A_dict.keys()}

    for a in A_list:
        if not sieve[a]:
            continue
        for i in range(2*a, limit+1, a):
            if i in sieve:
                sieve[i] = False

    print(sum([1 for i in sieve.keys() if sieve[i] and (A_dict[i]==1)]))
main()

Solution (Python):
N, *A = map(int, open(0).read().split())

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

dp = [0] * lim
for a in A:
    dp[a] += 1
    if dp[a] == 1:
        for j in range(2 * a, lim, a):
            dp[j] += 2

print(dp.count(1))

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

M = 10**6+5

count = [0]*M

for x in range(n):
    if count[a[x]] != 0:
        count[a[x]] = 2
        continue

    for i in range(a[x], M, a[x]):
        count[i] += 1

ans = 0
for x in range(n):
    if count[a[x]] == 1:
        ans += 1

print(ans)

Solution (Python):
N = int(input())
A = sorted(int(a) for a in input().split())


max_A = A[-1]
search_list = [True for _ in range(max_A)]

count = 0
for i, a in enumerate(A):
    if not search_list[a - 1]:
        continue
    for j in range(a, max_A + 1, a):
        search_list[j - 1] = False
    if i < N - 1 and A[i + 1] == a:
        continue
    count += 1

print(count)

Solution (Python):
from collections import Counter

N, *A = map(int, open(0).read().split())

C = Counter(A)
B = sorted(C.items(), key=lambda x: x[0])

lim = B[-1][0] + 1

memo = set()
ans = 0
for k, v in B:
    if k in memo:
        continue
    memo |= set(range(k, lim, k))
    ans += (v == 1)

print(ans)

Solution (Python):
from collections import Counter

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


prime = [1] * 1000010

for i in set(a):
    
    for j in range(i + i, 1000001, i):
        prime[j] = 0

c = Counter(a)
ans = 0
for i in a:
    if prime[i] and c[i] == 1:
        ans += 1
print(ans)

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

count = 0
for i, a in enumerate(A):
    if not b[a]:
        continue
    for j in range(a, M+1, a):
        b[j] = False
    if i < N-1 and A[i+1] == a:
        continue
    count += 1

print(count)

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

l=[0]*(1000005)
for i in range(n):
    if l[a[i]]==1:
        l[a[i]]+=1

    if l[a[i]]==0:
        for j in range(1000000//a[i]+1):
            l[a[i]*j]+=1
    
cnt=0
for i in range(n):
    if l[a[i]]==1:
        cnt+=1
print(cnt)

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

b = sorted(set(a))

for i in b:
    num = i * 2
    while True:
        if num >= 10 ** 6 + 1:
            break
        prime[num] = False
        num += i

ans = 0
for s in a:
    if prime[s] == True and c[s] == 1:
        ans += 1

print(ans)

Solution (Python):
from collections import Counter

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

is_p=[1]*(10**6+1)
for i in set(a):
  if is_p[i]:
    for j in range(i+i,10**6+1,i):
      is_p[j]=0

c=Counter(a)

cnt=0
for i in a:
  if is_p[i] and c[i]==1:
    cnt+=1

print(cnt)

Solution (Python):
from collections import Counter

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

is_p=[1]*(10**6+1)
for i in set(a):
  if is_p[i]:
    for j in range(i+i,10**6+1,i):
      is_p[j]=0

c=Counter(a)

cnt=0
for i in a:
  if is_p[i] and c[i]==1:
    cnt+=1

print(cnt)

Solution (Python):


from collections import Counter
n = int(input())
a = list(map(int, input().split()))


c = Counter(a)


p = [True] * (10 ** 6 + 1)


s = list(set(a))


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

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

count = 0
cnt = [0] * m
for i in range(n):
  if cnt[a[i]] == 0:
    for j in range(a[i], m, a[i]):
      cnt[j] += 1
  else:
    cnt[a[i]] = 2
for i in range(n):
  if cnt[a[i]] == 1:
    count += 1
print(count)

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

a_sorted = sorted(a)
divisible_list = [0] * (max(a)+1)

for i in range(len(a)):
    
    if divisible_list[a[i]] > 2:
        continue
    for j in range(0, len(divisible_list), a[i]):
        divisible_list[j] += 1

ans = 0
for i in range(len(a)):
    if divisible_list[a[i]] == 1:
        ans+=1
print(ans)

Solution (Python):
import numpy as np


N = int(input())
A = list(map(int, input().split())) + [10**7]

A.sort()
e = np.zeros(10**6 + 1)
ans = 0
for i in range(N):
    if e[A[i]] == 0:
        e[::A[i]] = 1 
        
        if A[i] != A[i+1]:
            ans += 1
print(ans)

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

a_sorted = sorted(a)
divisible_list = [0] * (max(a)+1)

for i in range(len(a)):
    for j in range(0, len(divisible_list), a[i]):
        divisible_list[j] += 1

ans = 0
for i in range(len(a)):
    if divisible_list[a[i]] == 1:
        ans+=1
print(ans)

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

print(dp.count(1))

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

count = 0
for i, a in enumerate(A):
  if not b[a]:
    continue
  for j in range(a, M+1, a):
    b[j] = False
  if i < N-1 and A[i+1] == a:
    continue
  count += 1

print(count)

Solution (Python):

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

count = 0
cnt = [0] * m
for i in range(n):
  if cnt[a[i]] == 0:
    for j in range(a[i], m, a[i]):
      cnt[j] += 1
  else:
    cnt[a[i]] = 2
for i in range(n):
  if cnt[a[i]] == 1:
    count += 1
print(count)

Solution (Python):



import numpy

def main():
  n = int(input())
  la = sorted(list(map(int, input().split())))
  a_max = max(la)
  dp = numpy.ones(a_max + 1)
  counts = numpy.zeros(a_max + 1)
  for a in la:
    counts[a] += 1
    if counts[a] < 2:
      dp[2*a::a] = 0
  print(len([a for a in la if dp[a]==1 and counts[a] == 1]))

if __name__=='__main__':
  main()

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

ma = max(A)
Er = [0 for _ in range(ma + 5)]

for i in range(N):
    temp = A[i]
    if Er[temp] != 2:
        a = 0
        while(1):
            a += 1
            tt = a * temp
            if tt >= ma + 5:
                break
            Er[tt] += 1
        
ans = 0
for i in range(N):
    temp = A[i]
    if Er[temp] == 1:  ans += 1
        
print(ans)

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

ma = max(A)
Er = [0 for _ in range(ma + 5)]
is_c = [0 for _ in range(ma + 5)]

for i in range(N):
    temp = A[i]
    if Er[temp] != 2:
        a = 0
        while(1):
            a += 1
            tt = a * temp
            if tt >= ma + 5:
                break
            Er[tt] += 1
        
ans = 0
for i in range(N):
    temp = A[i]
    is_c[temp] += 1
    if is_c[temp] == 2:
        continue  
    if Er[temp] == 1:  ans += 1
        
print(ans)

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

dq = [0] * (nums[-1] + 1)

for num in nums:
    dq[num] += 1
    if dq[num] == 1:
        for i in range(num*2, nums[-1]+1, num):
            dq[i] += 2

print(dq.count(1))

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

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

for i in range(N):
    tmp = A[i]
    if dp[tmp] != 0:
        dp[tmp] = 2
        continue
    else:
        for j in range(tmp, maxi, tmp):
            dp[j] += 1

ans = 0
for i in range(N):
    tmp = A[i]
    if dp[tmp] == 1:
        ans += 1

print(ans)