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):
"""
    Satwik_Tiwari ;) .
    16 june , 2020  - Tuesday
"""



from __future__ import division, print_function

from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase


import bisect
from heapq import *
from math import *
from collections import deque
from collections import Counter as counter  
from itertools import combinations as comb 
from itertools import permutations as permutate
from bisect import bisect_left as bl


from bisect import bisect_right as br
from bisect import bisect





BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)






mod = 1000000007
def inp(): return sys.stdin.readline().rstrip("\r\n") 
def out(var): sys.stdout.write(str(var))  
def lis(): return list(map(int, inp().split()))
def stringlis(): return list(map(str, inp().split()))
def sep(): return map(int, inp().split())
def strsep(): return map(str, inp().split())
def graph(vertex): return [[] for i in range(0,vertex+1)]
def zerolist(n): return [0]*n
def nextline(): out("\n")  
def testcase(t):
    for p in range(t):
        solve()
def printlist(a) :
    for p in range(0,len(a)):
        out(str(a[p]) + ' ')
def lcm(a,b): return (a*b)//gcd(a,b)
def power(a,b):
    ans = 1
    while(b>0):
        if(b%2==1):
            ans*=a
        a*=a
        b//=2
    return ans
def ncr(n,r): return factorial(n)//(factorial(r)*factorial(max(n-r,1)))
def isPrime(n) : 
    if (n <= 1) : return False
    if (n <= 3) : return True
    if (n % 2 == 0 or n % 3 == 0) : return False
    i = 5
    while(i * i <= n) :
        if (n % i == 0 or n % (i + 2) == 0) :
            return False
        i = i + 6
    return True




def solve():
    n = int(inp())
    a = lis()
    
    
    
    m = max(a)
    cnt = [0]*(m+1)

    for i in range(0,n):
        num = a[i]
        for j in range(num,m+1,num):
            cnt[j] +=1
        
    ans= 0
    for i in range(n):
        if(cnt[a[i]] == 1):
            
            ans +=1
    print(ans)





testcase(1)

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


num_max = 10 ** 6 + 5  
exist_counts = [0] * num_max
for num in nums:
  
  if exist_counts[num]:
    exist_counts[num] = 2
    continue
  
  idx = num
  while idx < num_max:
    exist_counts[idx] += 1
    idx += num


count = 0
for num in nums:
  if exist_counts[num] == 1:
    count += 1
print(count)

Solution (Python):
N=int(input())
A=sorted(list(map(int,input().split())))
dp=[True for i in range(A[-1])]
ans=0
i=0
j=-1
while i<N:
  if i+1<N:
    while A[i]==A[i+1]:
      i+=1
      if i+1==N:
        break
  if dp[A[i]-1] and i-j==1:
    ans+=1
  for k in range(2*A[i],A[-1]+1,A[i]):
    dp[k-1]=False
  j=i
  i+=1
print(ans)

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

Solution (Python):
def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    MAX = A[-1]
    dp = [1] * (MAX + 5)
    ANS = 0
    for i in range(N):
        if dp[A[i]] == 0:
            continue
        for j in range(MAX+1):
            if A[i]*j > MAX:
                break
            dp[A[i]*j] = 0
        dp[A[i]] = 0
        if i < N-1 and A[i] == A[i+1]:
            continue
        ANS += 1
    print(ANS)

if __name__ == '__main__':
    main()

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

values = list(map(int, input().split()))

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

for a in values:
    i = 1
    if dp[a] > 0:
        dp[a] = dp[a] + 1
        continue
    while i * a < maxV:
        i_a = i * a
        dp[i_a] = dp[i_a] + 1
        i += 1

count = 0
for a in values:
    if dp[a] == 1:
        count+=1

print(count)

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

values = list(map(int, input().split()))

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

for a in values:
    i = 1
    if dp[a] > 0:
        dp[a] = dp[a] + 1
        continue
    while i * a < maxV:
        i_a = i * a
        dp[i_a] = dp[i_a] + 1
        i += 1

count = 0
for a in values:
    if dp[a] == 1:
        count+=1

print(count)

Solution (Python):
from collections import Counter
N = int(input())
A = list(map(int, input().split())) 
ans = set(A)
for k, v in Counter(A).items():
    if v != 1:
        ans.discard(k)
    temp = {k*i for i in range(2,10**6//k + 1)}
    ans -= ans&temp
print(len(ans))

Solution (Python):

import sys


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




def solve(A):
  
  
    count = np.zeros(10**6 + 10, np.int32)
    for x in A:
        if count[x] > 1:
            continue
        count[::x] += 1
    ret = 0
    for x in A:
        ret += count[x] == 1
    return ret

def solve2(A):
  count = [0 for _ in range(10**6 + 10)]
  for x in A:
    if count[x] > 1:
      continue
    for a in range(0,len(count),x):
      count[a] += 1
  ret = 0
  for x in A:
    ret += (1 if count[x] == 1 else 0)
  
  return ret
  


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

print(solve2(sorted(A)))

Solution (Python):

import sys


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




def solve(A):
  
  
    count = np.zeros(10**6 + 10, np.int32)
    for x in A:
        if count[x] > 1:
            continue
        count[::x] += 1
    ret = 0
    for x in A:
        ret += count[x] == 1
    return ret

def solve2(A):
  count = [0 for _ in range(10**6 + 10)]
  for x in A:
    if count[x] > 1:
      continue
    for a in range(0,len(count),x):
      count[a] += 1
  ret = 0
  for x in A:
    ret += (1 if count[x] == 1 else 0)
  
  return ret
  


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

print(solve2(A))

Solution (Python):
import sys
import numpy as np

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

def solve(A):
    count = np.zeros(10**6 + 10, np.int32)
    for x in A:
        if count[x] > 1:
            continue
        count[::x] += 1
    ret = 0
    for x in A:
        ret += count[x] == 1
    return ret

A = np.array(read().split(), np.int32)[1:]
 
print(solve(A))

Solution (Python):


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

max_a = max(a)
c = {a_tmp: 0 for a_tmp in a}
for a_tmp in a:
    c[a_tmp] += 1

d = {a_tmp: 0 for a_tmp in a}
for a_tmp in a:
    if c[a_tmp] > 0:
        t = 2
        while a_tmp*t <= max_a:
            d[a_tmp*t] = 1
            t += 1
ans = 0
for a_tmp in a:
    if c[a_tmp] == 1 and d[a_tmp] == 0:
        ans += 1

print(ans)

Solution (Python):
import sys
from itertools import groupby

readline = sys.stdin.buffer.readline
readline()
b = list(map(int, readline().split()))

b.sort()


x = len(b)
c = [(k, len(tuple(L))) for k, L in groupby(b)]

m = c[-1][0]

s = [True] * (m + 1)


a = 0
for i, le in c:
  if s[i]:
    if le <= 1:
      a += 1
    for v in range(i, m + 1, i):
      s[v] = False

print(a)

Solution (Python):
import numpy as np
import sys
input = sys.stdin.buffer.readline

N = int(input())
A = list(map(int, (input().split())))
A.sort()
cnt = np.zeros(10**6+10, dtype=np.int32)
for x in A:
    if cnt[x] != 0:
        cnt[x] = 2
        continue
    cnt[x::x] += 1
ans = 0
for x in A:
    if cnt[x] == 1:
        ans += 1
print(ans)

Solution (Python):
A=int(input())
S=list(map(int,input().split()))
tmp=set()
aft=set()
for i in S:
   if i in aft:
      tmp.add(i)
   else:
      aft.add(i)
n=max(S)+1
DP=[1]*n
for i in aft:
   if i in tmp:
      DP[i]=0
   for j in range(2*i,n,i):
      DP[j]=0
ans=0
for i in S:
   ans+=DP[i]
print(ans)

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

A.sort()
mx = A[n-1]
dp = [0]*(mx+1)
for a in A:
    for j in range(a,mx+1,a):
        dp[j]+=1
        
sum = 0
for i in A:
    if dp[i]==1:
        sum+=1
print(sum)

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

a.sort()
a_set = set(a)
for i in range(n-1):
    if a[i] == a[i + 1]:
        if a[i] in a_set:
            a_set.remove(a[i])

ma = max(a)

dp = [True for _ in range(ma + 1)]
ans = 0
y = -1
for x in a:
    if x == y:
        continue
    y = x

    if x in a_set:
        ans += 1 if dp[x] else 0

    while y <= ma:
        dp[y] = False
        y += x

print(ans)

Solution (Python):
from collections import Counter

_ = int(input())
A = list(map(int, input().split()))
a_max = 10 ** 6

c = Counter(A)
b = list(set(A))
b.sort()

dp = [True] * (a_max + 1)
ans = 0
for a in b:
    if dp[a]:
        if c[a] == 1:
            ans += 1
        for i in range(2 * a, a_max + 1, a):
            dp[i] = False

print(ans)

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
A.sort()
max_a=A[-1]
dp=[True]*(max_a+1)
ans=0
for i in range(N):
  a=A[i]
  
  if dp[a]==True: 
    if i==N-1:
      ans+=1
    elif a!=A[i+1]:
      ans+=1
    
    k=a
    while k<=max_a:
      dp[k]=False    
      k+=a
print(ans)

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

div = [0] * 1000005

N = int(input())

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

for num in A:
    if div[num] == 0:
        for i in range(num, 1000004, num):
            div[i] += 1
    elif div[num] != 0:
        div[num] += 1        

ans = 0

for num in A:
    if div[num] == 1:
        ans += 1

print(ans)

Solution (Python):
N = int(input())
nums = [i for i in map(int, input().split())]
nums = sorted(nums)
max = nums[-1]
dp = [1]*(max+1)
ans = 0

for i in range(len(nums)-1):
    p = nums[i]
    if dp[p] ==1:
        for q in range(max//p+1):
            dp[p*q]=0
        if nums[i] != nums[i+1]:
            ans+=1
if dp[max]==1:
    ans+=1
print(ans)

Solution (Python):



from fractions import gcd
from itertools import combinations,permutations 

from collections import deque,defaultdict











import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
N = I()
A = readInts()
import collections
dic = collections.Counter(A)
A = set(A)
is_prime = [True] * (10**6+1)
for a in A:
    if is_prime[a]:
        for v in range(a*2,10**6+1,a):
            is_prime[v] = False
cnt = 0
for a in A:
    if is_prime[a]:
        cnt += 1
for k,v in dic.items():
    if v >= 2 and is_prime[k]:
        cnt -= 1
print(cnt)

Solution (Python):
from collections import*
n = int(input())
c = Counter(map(int, input().split()))
s = set()
for i in c:
    c[i] -= 1
    for j in range(i, 10**6+1, i):
        if c[j]:
            s.add(j)
    c[i] += 1
r = 0
for i in c:
    r += c[i] * (i not in s)
print(r)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

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

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

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




    
resolve()

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

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

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


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


cnt = col.Counter(a)


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

print(ans)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
MAX = max(A)
dp = [True for _ in range(MAX+1)]

for a in set(A):
    for k in range(2*a,MAX+1,a):
        dp[k] = False
B = sorted(A)
for i in range(len(B)-1):
    if B[i] == B[i+1]:
        dp[B[i]] = False

print(sum(dp[a] for a in set(A)))

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

sortList = sorted(AList)
Amax = max(sortList)

dp = [0]*(Amax+1)

for n in sortList:
  dp[n] += 1
  if dp [n] == 1:
    for i in range(n*2, Amax+1, n):
      dp[i] += 2

print(dp.count(1))

Solution (Python):


import sys

def resolve():
    it = map(int,sys.stdin.read().split())
    N = next(it)
    A = [next(it) for i in range(N)]
    
    if N == 1:
        print(1)
        return
    ax = max(A) + 1
    dp = [0] * ax
    for ai in A:
        da = dp[ai]
        if da > 1:
            continue
        dp[ai] += 1
        if da == 0:
            for aj in range(2*ai, ax, ai):
                dp[aj] = 2
    ans = 0
    for ai in A:
        if dp[ai] == 1:
            ans += 1
    print(ans)
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(4100000)

import math

import logging

logging.basicConfig(level=logging.DEBUG)

logger = logging.getLogger(__name__)

import numpy as np


def resolve():
    
    N = [int(x) for x in sys.stdin.readline().split()][0]  
    
    a_list = [int(x) for x in sys.stdin.readline().split()]  

    
    
    
    

    logger.debug('{}'.format([]))

    MAX = 10**6
    count_list = np.array([0 for _ in range(MAX + 1)])
    for a in a_list:
        count_list[a] += 1

    for i in range(1, MAX + 1):
        if count_list[i]:
            count_list[i * 2::i] = 0
            if count_list[i] >= 2:
                count_list[i] = 0

    print(count_list.sum())


if __name__ == "__main__":
    resolve()





import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """5
24 11 8 3 16"""
        output = """3"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """4
5 5 5 5"""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """10
33 18 45 28 8 19 89 86 2 4"""
        output = """5"""
        self.assertIO(input, output)

    def test_入力例_4(self):
        input = """2
1000000 1000000"""
        output = """0"""
        self.assertIO(input, output)

Solution (Python):
n=int(input())
l=list(map(int,input().split()))
l.sort()
max=l[n-1]
dp=[0]*(max+1)
for i in l:
  if dp[i]!=0:
    dp[i]+=1
    continue
  for j in range(i,max+1,i):
    dp[j]+=1
sum=0
for i in l:
  if dp[i]==1:
    sum+=1
print(sum)

Solution (Python):


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


max_a = max(a_nums)
fact_list = [0] * (max_a + 1)
ans = 0


for a in a_nums:
    tmp = max_a // a
    for i in range(tmp):
        fact_list[a*(i+1)] += 1


for a in a_nums:
    if fact_list[a]==1:
        ans += 1


print(ans)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    from collections import Counter
    N = int(input())
    A = sorted(list(map(int, input().split())))
    C = Counter(A)
    dp = [False] * 1100000
    ans = 0
    for a, cnt in C.items():
        if dp[a]:
            continue
        for i in range(2*a, 1100000, a):
            dp[i] = True
        if cnt == 1:
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
from collections import Counter as co
l=co(list(map(int,input().split())))
ans=len(l)
ng=set()
for k in l:
    if l[k]>=2:ng.add(k)
    for i in range(2*k,10**6+1,k):
        if i in l:
            ng.add(i)
print(ans-len(ng))

Solution (Python):
n=int(input())
from collections import Counter as co
l=co(map(int,input().split()))
ans=set()
for k in l:
    if l[k]>=2:ans.add(k)
    for j in range(2*k,10**6+1,k):
        if j in l:
            ans.add(j)
        
        
print(len(l)-len(ans))

Solution (Python):
from copy import deepcopy
import math
import string
import collections
from collections import Counter
from collections import deque
from decimal import Decimal
import sys
import fractions
from operator import itemgetter
import itertools
import copy


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


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor



dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]

n = int(input())
a = readints()
tmp = [False]*(10**6+100)
a_so = sorted(a)

cnt = 0
for i in range(len(a_so)):
    if tmp[a_so[i]]:
        continue
    if (i+1 >= len(a_so)) or (a_so[i] != a_so[i+1]):
        cnt += 1
    for j in range(1, len(tmp)):
        if a_so[i]*j >= len(tmp):
            break
        tmp[a_so[i]*j] = True
print(cnt)

Solution (Python):
def find(A):
    nums=[0]*(10**6+1)
    bad = [0]*(10**6+1)
    count = 0
    for x in A:
        nums[x] += 1
    for i in range(1,10**6+1):
        if nums[i]==0:
            continue
        for j in range(2,10**6+1):
            temp = i*j
            if temp<10**6+1:
                bad[temp] = 1
            else:
                break
    
    ans = 0
    for x in A:
        if bad[x] == 0 and nums[x] == 1:
            ans +=1
    return ans

input()
A = list(map(int,input().strip().split()))
print(find(A))

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

from collections import Counter
C = Counter(A)


M = max(A)
X = [0]*(M+1)
for i in A:
    j = i*2
    while j <= M:
        X[j] = 1
        j += i


ans = 0
for a in A:
    if C[a] == 1 and X[a] != 1:
        ans += 1
print(ans)

Solution (Python):
import numpy as np

n = int(input())
a = list(map(int, input().split()))
MAX = 10 ** 6

arr = np.zeros(MAX + 1, np.int64)
for e in a:
    arr[e] += 1

for i in range(MAX + 1):
    if arr[i]:
        arr[2*i::i] = 0

    arr[i] = arr[i] == 1

ans = arr.sum()
print(ans)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
a.sort()
f=[1]*(10**6+10)
from collections import Counter
c=Counter(a)
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+10,ai):
      f[i]=0
print(ans)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
A = sorted(A)
N = len(A)
amax = A[-1]
P = [0 for _ in range(amax+1)]
for i in range(N):
    P[A[i]] = 1
for i in range(N):
    a = A[i]
    for j in range(a*2,amax+1,a):
        P[j] = 0
C = {}
for i in range(N):
    a = A[i]
    if a not in C:
        C[a] = 0
    C[a] += 1
for i in range(N):
    a = A[i]
    if P[a]==1 and C[a]>1:
        P[a] = 0
print(sum(P))

Solution (Python):


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
lis=LI()
c=Counter(lis)
lis=list(set(lis))
m=10**6+1
dp=[0 for i in range(m)]

for i in range(len(lis)):
    x=lis[i]
    
    for j in range(2,((m-1)//x)+1):
        dp[x*j]=1
        


ans=0

for y in lis:
    if c[y]<=1:
        ans+=1-dp[y]
print(ans)

Solution (Python):
import sys
from collections import Counter

N = int(input())
A = list(map(int, sys.stdin.readline().rsplit()))
A.sort()
B = [0] * (A[-1] + 1)
C = Counter(A)

res = 0
for a in A:
    if B[a] == 0 and C[a] == 1:
        res += 1
    for i in range(a, A[-1] + 1, a):
        B[i] += 1

print(res)

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

Solution (Python):
def main():

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

    from collections import Counter
    C = Counter(A)
    

    M = max(A)

    X = [0]*(M+1)
    for i in A:
        j = i*2
        while j <= M:
            X[j] = 1
            j += i
    

    ans = 0
    for a in A:
        if C[a] == 1 and X[a] != 1:
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

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

Solution (Python):
from collections import Counter

N = int(input())
*A, = map(int, input().split())
A.sort()
C = Counter(A)
MAX = 1010101
B = [0]*MAX

ans = 0
for a, cnt in C.items():
    if B[a]:
        continue
    for i in range(2*a, MAX, a):
        B[i] = 1
    if cnt == 1:
        ans += 1

print(ans)

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

N = int(input())
A = list(map(int, input().split()))
s = set(A)
flag = [False]*(10**6+100)

for i in range(10**6+100):
    if i in s:
        flag[i] = True
        
for i in range(10**6+100):
    if i in s:
        for j in range(2*i, 10**6+100, i):
            flag[j] = False

cnt = Counter(A)
ans = 0

for i in range(10**6+100):
    if flag[i] and cnt[i]==1:
        ans += 1

print(ans)

Solution (Python):
N = int(input())
A = sorted(list(map(int, input().split())))
m = A[-1]+1
dp = [0]*(m*2)
ans = 0

for a in A:
    for i in range(0, m//a+1):
        dp[a*i] += 1
for a in A:
    if dp[a] == 1:
        ans += 1

print(ans)

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

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

for i in a:
    if dp[i] == 0:
        for j in range(1,10**6+1):
            if i * j > 10**6:
                break
            dp[i*j] += 1
    elif dp[i] == 1:
        dp[i] += 1

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


print(ans)

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

max_number = max(A) + 1
ng = [False] * max_number
counter = 0
prev = 0
for ai in A:
    if ai == prev:
        counter -= 1
        prev = 0
    if not ng[ai]:
        counter += 1
        prev = ai
    for i in range(ai, max_number, ai):
        ng[i] = True
print(counter)

Solution (Python):
import sys

def ii(): return int(sys.stdin.readline())
def li(): return list(map(int, sys.stdin.readline().split()))

if __name__ == "__main__":
    n = ii()
    a = li()
    a = sorted(a)
    a_max = a[-1]
    sive = [True] * (a_max + 1)

    def sived(x):
        for non_ans in range(x, a_max+1, x):
            sive[non_ans] = False
    ans = 0
    for i in range(len(a)-1):
        if sive[a[i]]:
            sived(a[i])
            if a[i] != a[i+1]:
                ans += 1
    if sive[a_max]:
        ans += 1
    print(ans)

Solution (Python):
import sys
from collections import Counter

def ii(): return int(sys.stdin.readline())
def li(): return list(map(int, sys.stdin.readline().split()))

if __name__ == "__main__":
    n = ii()
    a = li()
    a = sorted(a)
    a_max = a[-1]
    sive = [True] * (a_max + 1)

    def sived(x):
        for non_ans in range(x, a_max+1, x):
            sive[non_ans] = False
    ans = 0
    for i in range(len(a)-1):
        if sive[a[i]]:
            sived(a[i])
            if a[i] != a[i+1]:
                ans += 1
    if sive[a_max]:
        ans += 1
    print(ans)

Solution (Python):
from collections import deque
import math

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

    A.sort(reverse=True)

    Amax=max(A)

    dp=[0]*Amax

    tmp=-1
    res=0
    for i in range(len(A)):
        a=A.pop()
        if a==tmp:
            continue
        if dp[a-1]==0:
            if len(A)>0:
                if A[len(A)-1]!=a:
                    res+=1
            else:
                res+=1
            m=2
            while (a*m)<=Amax:
                dp[a*m-1]=1
                m+=1
        tmp=a

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

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

check = [0]*(a_max+1)

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

print(check.count(1))

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

M=max(A)
check=[0]*(M+1)

for i in range(N):
    a=A[i]
    if check[a]>1:
        continue
    while a<=M:
        check[a]+=1
        a+=A[i]
ans=0
for i in range(N):
    if check[A[i]]==1:
        ans+=1

print(ans)

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

M=max(A)
check=[0]*(M+1)
for i in range(N):
    a=A[i]
    while a<=M:
        check[a]+=1
        a+=A[i]
ans=0
for i in range(N):
    if check[A[i]]==1:
        ans+=1

print(ans)

Solution (Python):
n = int(input())
A = sorted(list(map(int, input().split())))
M = 10**6 + 1
L = [0]*M
for a in A:
    L[a] += 1
    if L[a] == 1:
        
        for i in range(2*a, M, a):
            L[i] += 2

print(L.count(1))

Solution (Python):

import numpy as np
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect


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


def z():
    return int(input())


def S():
    return input()


def C(line):
    return [input() for _ in range(line)]


N = z()
A = zz()
A = sorted(A)

kasanari = []
count = [0]*(10**6+1)
for a in A:
    count[a] += 1
    if (count[a] > 1):
        kasanari.append(a)
ref = list(set(A) - set(kasanari))

erasut = np.ones(A[-1]+1, dtype=np.int64)
for a in set(A):
    if(a*2 < A[-1]+1):
        erasut[a*2::a] = 0
erasut = erasut[ref]

print(sum(erasut))

Solution (Python):
import sys

from collections import defaultdict

I=sys.stdin.readline

n=int(I())
arr=sorted(list(map(int,I().split())))
d=defaultdict(int)

for i in arr:
	d[i]+=1

ans=0
visited=[0]*(arr[-1]+1)
for i in arr:
	if d[i]==1 and visited[i]==0:
		ans+=1

	for j in range(i,arr[-1]+1,i):
		visited[j]=1

print(ans)