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):
import math
import heapq,bisect
import sys
from collections import deque,defaultdict
from fractions import Fraction
mod=10**9+7
mod1=998244353

import os
import sys
from io import BytesIO, IOBase

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


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

class SegmentTree1:
    def __init__(self, data, default=9999999, func=lambda a, b: min(a , b)):
        """initialize the segment tree with data"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()

        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __delitem__(self, idx):
        self[idx] = self._default

    def __getitem__(self, idx):
        return self.data[idx + self._size]

    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1

    def __len__(self):
        return self._len

    def query(self, start, stop):
        if start == stop:
            return self.__getitem__(start)
        stop += 1
        start += self._size
        stop += self._size

        res = self._default
        while start < stop:
            if start & 1:
                res = self._func(res, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res = self._func(res, self.data[stop])
            start >>= 1
            stop >>= 1
        return res

    def __repr__(self):
        return "SegmentTree({0})".format(self.data)


class SegmentTree:
    def __init__(self, data, default=0, func=lambda a, b: a + b):
        """initialize the segment tree with data"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()

        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __delitem__(self, idx):
        self[idx] = self._default

    def __getitem__(self, idx):
        return self.data[idx + self._size]

    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1

    def __len__(self):
        return self._len

    def query(self, start, stop):
        if start == stop:
            return self.__getitem__(start)
        stop += 1
        start += self._size
        stop += self._size

        res = self._default
        while start < stop:
            if start & 1:
                res = self._func(res, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res = self._func(res, self.data[stop])
            start >>= 1
            stop >>= 1
        return res

    def __repr__(self):
        return "SegmentTree({0})".format(self.data)

class Factorial:
    def __init__(self, MOD):
        self.MOD = MOD
        self.factorials = [1, 1]
        self.invModulos = [0, 1]
        self.invFactorial_ = [1, 1]

    def calc(self, n):
        if n <= -1:
            print("Invalid argument to calculate n!")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        if n < len(self.factorials):
            return self.factorials[n]
        nextArr = [0] * (n + 1 - len(self.factorials))
        initialI = len(self.factorials)
        prev = self.factorials[-1]
        m = self.MOD
        for i in range(initialI, n + 1):
            prev = nextArr[i - initialI] = prev * i % m
        self.factorials += nextArr
        return self.factorials[n]

    def inv(self, n):
        if n <= -1:
            print("Invalid argument to calculate n^(-1)")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        p = self.MOD
        pi = n % p
        if pi < len(self.invModulos):
            return self.invModulos[pi]
        nextArr = [0] * (n + 1 - len(self.invModulos))
        initialI = len(self.invModulos)
        for i in range(initialI, min(p, n + 1)):
            next = -self.invModulos[p % i] * (p // i) % p
            self.invModulos.append(next)
        return self.invModulos[pi]

    def invFactorial(self, n):
        if n <= -1:
            print("Invalid argument to calculate (n^(-1))!")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        if n < len(self.invFactorial_):
            return self.invFactorial_[n]
        self.inv(n)  
        nextArr = [0] * (n + 1 - len(self.invFactorial_))
        initialI = len(self.invFactorial_)
        prev = self.invFactorial_[-1]
        p = self.MOD
        for i in range(initialI, n + 1):
            prev = nextArr[i - initialI] = (prev * self.invModulos[i % p]) % p
        self.invFactorial_ += nextArr
        return self.invFactorial_[n]


class Combination:
    def __init__(self, MOD):
        self.MOD = MOD
        self.factorial = Factorial(MOD)

    def ncr(self, n, k):
        if k < 0 or n < k:
            return 0
        k = min(k, n - k)
        f = self.factorial
        return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
    if a == 1 or n == 0:
        return 1
    if n % 2 == 0:
        s = powm(a, n // 2, m)
        return s * s % m
    else:
        return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
    zipped_pairs = zip(list2, list1)

    z = [x for _, x in sorted(zipped_pairs)]

    return z

def product(l):
    por=1
    for i in range(len(l)):
        por*=l[i]
    return por

def binarySearchCount(arr, n, key):
    left = 0
    right = n - 1

    count = 0

    while (left <= right):
        mid = int((right + left) / 2)

        
        
        if (arr[mid] <= key):

            
            
            
            count = mid + 1
            left = mid + 1

        
        else:
            right = mid - 1

    return count

def countdig(n):
    c=0
    while(n>0):
        n//=10
        c+=1
    return c
def countGreater(arr, n, k):
    l = 0
    r = n - 1

    
    
    leftGreater = n

    
    while (l <= r):
        m = int(l + (r - l) / 2)

        
        
        if (arr[m] > k):
            leftGreater = m
            r = m - 1

        
        
        else:
            l = m + 1

    
    
    return (n - leftGreater)

n=int(input())
l=list(map(int,input().split()))
l.sort()
c=dict()
for i in range(n):
    if l[i] in c:
        c[l[i]]+=1
    else:
        c.update({l[i]:1})
ma=l[-1]
d=defaultdict(int)
ans=[0]*n
for i in range(n):
    if d[l[i]]==0:
        ans[i]=1
        for j in range(l[i],ma+1,l[i]):
            d[j]=-1
        if c[l[i]]>1:
            ans[i]=0

print(sum(ans))

Solution (Python):
from itertools import islice
def solve(A):
    memo = [0]*(10**6+1)

    for a in A:
        memo[a] += 1
    if memo[1] > 0:
        return 1 if memo[1] == 1 else 0

    res = 0
    for i,v in enumerate(islice(memo,2,None),start=2):
        if v > 0:
            res += 1 if v == 1 else 0
            j = i
            while j <= 10**6:
                memo[j] = 0
                j += i
    return res

if __name__ == '__main__':
    N = int(input())
    A = list(map(int,input().split()))
    print(solve(A))

Solution (Python):

import sys


def solve(N: int, A: "List[int]"):
    from collections import Counter
    M = max(A)
    C = Counter(A)
    table = [False] * (M + 1)
    for c in C:
        for j in range(c+c, M + 1, c):
            table[j] = True
    ans = 0
    for a in A:
        if table[a] or C[a] > 1:
            continue
        ans += 1
    return ans



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)]  
    print(solve(N, A))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    
    main()

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

l = [0] * 1000001

ans = 0

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

for i in range(1, 1000001):
    if l[i] > 0:
        if l[i] == 1:
            ans += 1
        for j in range(2, 1000000//i + 1):
            l[i * j] = 0

print(ans)

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

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

def solve():
    N = int(readline())
    A = list(map(int, readline().split()))

    c = Counter(A)
    A = set(A)

    f = [0] * (10 ** 6 + 10)

    for a in A:
        for b in range(a * 2, len(f), a):
            f[b] = 1
    
    count = 0
    for a in A:
        if f[a] == 0 and c[a] == 1:
            count += 1

    print(count)

solve()

Solution (Python):
import collections

_ = input()
lst = list(map(int,input().split()))

lst = sorted(lst)
elim = [False for _ in range(10**6 + 1000)]
c = collections.Counter(lst)

for x in lst:
  if elim[x]:
    continue
  for i in range(x+x,10**6+1,x):
    elim[i] = True
  if c[x] > 1:
    elim[x] = True

cnt = 0
for x in lst:
  if not elim[x]:
    cnt += 1

print(cnt)

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

n = int(input())
a = [int(x) for x in input().split()]
b = [0] * 1000001
chk = [0] * 1000001
s = set(a)

for x in a:
    chk[x] += 1

for x in s:
    for y in range(x, 1000001, x):
        b[y] += 1

cnt = 0

for x in s:
    if b[x] == 1 and chk[x] == 1:
        cnt += 1

print(cnt)

Solution (Python):


import os
import sys
from io import BytesIO, IOBase

"""
    for _ in range(int(input())):
    n,m=map(int,input().split())
    n=int(input())
    a = [int(x) for x in input().split()]
"""

def main():
    n=int(input())
    a = [int(x) for x in input().split()]
    N = 10**6
    ans=[True]*(1+N)
    ct=[False]*(1+N)
    for x in a:
        if ct[x]:
            ans[x]=False
            continue
        ct[x]=True
        for j in range(2*x,N+1,x):
            ans[j]=False
    cnt=0
    for x in a:
        cnt+=ans[x]
    print(cnt)



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


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")



if __name__ == "__main__":
    main()

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()))
num = [0 for _ in range(10**6+1)]
for x in a:
	num[x] += 1

ok = [True for _ in range(10**6+1)]
ans = 0
for i in range(1, 10**6+1):
	if num[i] == 1 and ok[i] == True:
		ans += 1
	if num[i]:
		for j in range(i, 10**6+1, i):
			ok[j] = False
print(ans)

Solution (Python):
import sys

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


MAXA = 10**6

used = [False for i in range(MAXA + 5)]
result = 0
counts = {}
for a in x:
	if a in counts:
		counts[a] += 1
	else: 
		counts[a] = 1

for x in range(MAXA + 1):
	if not used[x]:
		if x in counts:
			count = counts[x]		
			if count == 1:
				result += 1

			y = 2*x
			while y <= MAXA:
				used[y] = True
				y += x

print(result)

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

ma = 2 * 10 ** 6
tab = [False] * (ma)

mapp = {}
for i in a:
    if i in mapp:
        mapp[i] += 1
    else:
        mapp[i] = 1

ans = 0
for i in a:
    if not tab[i]:
        if mapp[i] == 1:
            ans += 1
        for j in range(i, ma, i):
            tab[j] = True
print(ans)

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

l.sort()
check = [-1]*(10**6+2)

ans = 0
for i in l:
    if check[i] == -1:
        if c[i] == 1:
            ans += 1
        for j in range(i,10**6+2,i):
            check[j] = i
print(ans)

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


def solve(n, a_list):
    count_a = Counter(a_list)
    res = 0
    
    sieve = np.ones(10 ** 6 + 1)
    for i in range(10 ** 6 + 1):
        if sieve[i]:
            if count_a[i] > 0:
                sieve[i::i] = 0
            if count_a[i] == 1:
                res += 1
    return res


def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    res = solve(n, a_list)
    print(res)


def test():
    assert solve(5, [24, 11, 8, 3, 16]) == 3
    assert solve(4, [5, 5, 5, 5]) == 0
    assert solve(10, [33, 18, 45, 28, 8, 19, 89, 86, 2, 4]) == 5


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

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

ok = [True]*1000005

a.sort()
ans=0
for i in range(n):
    if i<n-1 and a[i]!=a[i+1] and ok[a[i]]:
        ans+=1
    elif i==n-1 and ok[a[i]]:
        ans+=1
    if ok[a[i]]:
        for j in range(a[i],1000004,a[i]):
            ok[j]=False

print(ans)

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

al.sort()
table = [False]*1000001
table2 = [False]*1000001

for a in al:
    if table2[a]:
        table[a]=True
    if not table[a]:
        table2[a] = True
        for i in range(a+a,1000001,a):
            table[i]=True
    

cnt=0
for a in al:
    if not table[a]:
        cnt+=1
print(cnt)

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

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

A.sort()

L = [False]*(10**6+1)
for i,a in enumerate(A):
    if A[i-1] == a:
        L[a] = True
        continue
    if L[a]: continue
    for i in range(2,10**6+1):
        if a*i > 10**6: break
        L[a*i] = True

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

Solution (Python):

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

from collections import Counter

C = Counter(A)

K = list(C.keys())

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

for k in K:
    l = 2*k
    while l <= 10**6:
        D[l] = 1
        l+=k
count = 0
for k in K:
    if C[k]==1 and D[k]==0:
        count+=1
print(count)

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

from collections import defaultdict
dic = defaultdict(int)


for a in al:
    dic[a] += 1

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

al = sorted(al)
from math import sqrt
M = 10**6+1
p = [1]*(M+1)
p[0] = p[1] = 0
ans = 0
for x in al:
    if p[x]:
        if dic[x] == 1:
            ans += 1
        for y in range(x, M+1, x):
            p[y] = 0

print(ans)

Solution (Python):
from collections import Counter

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

c = Counter(A)
t = [True] * (10**6 + 1)

ans = 0
for k, v in c.items():
    if t[k]:
        if v == 1:
            ans += 1
        for j in range(k, 10**6+1, k):
            t[j] = False

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)
F = [False]*(10**6+100)
cnt = Counter(A)

for i in range(10**6+100):
    if i in s:
        F[i] = True

for i in range(1, 10**6+100):
    if i in s:
        for j in range(2*i, 10**6+100, i):
            F[j] = False
    
ans = 0

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

print(ans)

Solution (Python):

import sys
input = sys.stdin.readline
from collections import Counter

n = int(input())
a = [int(item) for item in input().split()]
a.sort()

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

MAX_SIZE = 10**6 + 10
is_divisible = [True] * MAX_SIZE 
ans = 0
for item in a:
    if is_divisible[item]:
        if cnt[item] == 1:
            ans += 1
        for i in range(MAX_SIZE):
            if i * item >= MAX_SIZE:
                break
            is_divisible[i * item] = False
    else:
        continue

print(ans)

Solution (Python):
def gcd(a, b):
    while b: a, b = b, a % b
    return a
def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2, 7, 61] if n < 1<<32 else [2, 3, 5, 7, 11, 13, 17] if n < 1<<48 else [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = y * y % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1
def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g): return g
            elif isPrimeMR(n // g): return n // g
            return findFactorRho(g)
def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i * i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += i % 2 + (3 if i % 3 == 1 else 1)
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

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

def divisors(N):
    pf = primeFactor(N)
    ret = [1]
    for p in pf:
        ret_prev = ret
        ret = []
        for i in range(pf[p]+1):
            for r in ret_prev:
                ret.append(r * (p ** i))
    return sorted(ret)


N = int(input())
A = [int(a) for a in input().split()]
X = [0] * 1000001
for a in A:
    X[a] += 1

ans = 0
for a in A:
    if X[a] > 1:
        continue
    for d in divisors(a)[:-1]:
        if X[d]:
            break
    else:
        ans += 1
print(ans)

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
A.sort()
dic={}
for i in range(N):
    if A[i] not in dic:
        dic[A[i]]=0
    dic[A[i]]+=1
ban=set([])
res=0
for i in range(N):
    a=A[i]
    if a not in ban:
        if dic[A[i]]==1:
            res+=1
        for j in range(1,10**6//a+1):
            ban.add(a*j)

print(res)

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

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

for a in A:
    LIST[a]+=1
ANS=0

for i in range(10**6+1):
    if LIST[i]==1:
        ANS+=1
    if LIST[i]!=0:
        for j in range(2*i,10**6+1,i):
            if LIST[j]!=0:
                LIST[j]+=1
print(ANS)

Solution (Python):

from collections import deque
N = int(input())
A = list(map(int,input().split()))
A.sort()
A = deque(A)
B = [0]*(10**6+1)
ans = 0
for _ in range(N):
    x = A.popleft()
    if B[x]==0:
        ans += 1
        B[x] = 2
        tmp = 2*x
        while tmp<=10**6:
            B[tmp] = 1
            tmp += x
    elif B[x]==2:
        B[x] = 1
        ans -= 1
print(ans)

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

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

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

for a in A:
    LIST[a]+=1
ANS=0

for i in range(10**6+1):
    if LIST[i]==1:
        ANS+=1
    if LIST[i]!=0:
        for j in range(2*i,10**6+1,i):
            if LIST[j]!=0:
                LIST[j]+=1
print(ANS)

Solution (Python):
import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())
A=sorted([int(i) for i in input().split()])
ma=max(A)
C=[True]*(ma+1)

import collections
AA=collections.Counter(A)

AS=list(set(A))
AS.sort()
for a in AS:
  if AA[a]>1:
    ct=1
  else:
    ct=2
  while a*ct<=ma:
    C[a*ct]=False
    ct+=1
ans=0
for a in AA.keys():
  if C[a]:
    ans+=AA[a]
print(ans)

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

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

@njit('(i4[::1],)', cache=True)
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()))

D = [0] * (10 ** 6 + 1)
A.sort()
A = A + [10 ** 7]
cnt = 0
for i in range(N):
  if D[A[i]] == 0:
    if A[i] != A[i + 1]:
      cnt += 1
    for j in range(A[i], 10 ** 6 + 1, A[i]):
      D[j] = 1
print(cnt)

Solution (Python):
import sys
from collections import Counter

import numpy as np

n, *aaa = map(int, sys.stdin.buffer.read().split())
cnt = Counter(aaa)
duplicated = {x for x, c in cnt.items() if c > 1}
aaa.sort()

can = np.ones(aaa[-1] + 1, np.int8)

ans = 0
for a in aaa:
    if can[a] == 0:
        continue
    if a not in duplicated:
        ans += 1
    can[a * 2::a] = 0

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
  if cnt[arr[i]]>=2:
    continue
  ans+=1
print(ans)

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

M = 10**6+1
L = [0]*M

for a in A:
    if L[a] >= 1:
        L[a] = 2
        continue
    L[a] = 1
    i = 2
    while a*i < M:
        L[a*i] = 2
        i += 1

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

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
a.sort()
b = [0 for _ in range(10**6+1)]
ans = 0
for i in range(n):
  x = a[i]
  if b[x]:
    continue
  if i != n-1:
    if a[i+1] != x:
      ans += 1
      
  else:
    ans += 1
  now = x
  while True:
    try:
      b[now] = 1
      now += x
    except:
      break

print(ans)

Solution (Python):




N=int(input())
A=[int(i) for i 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,*a=map(int,open(0).read().split())
m=max(a)+10
li=[0]*m
for x in a:
	li[x]+=1
ans=0
for i in range(1,m):
	if li[i]:
		if li[i]==1:
			ans+=1
		for j in range(i,m,i):
			li[j]=0
print(ans)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
a.sort()
ls = [1]*(10**6+1)
ans = 0
for idx,i in enumerate(a):
  if ls[i] == 0:
    continue
  if idx == n-1 or a[idx+1] != i:
    ans += 1
  for j in range(i,10**6+1,i):
    ls[j] = 0
print(ans)

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

N = int(input())
A = list(map(int, input().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)

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):
mod = 1000000007
eps = 10**-9


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

    N = int(input())
    A = list(map(int, input().split()))
    M = 10**6

    A.sort()
    C = Counter(A)
    ans = 0
    seen = [0] * (M+1)
    A = set(A)
    for a in A:
        if C[a] == 1 and seen[a] == 0:
            ans += 1
        for j in range(1, M+1):
            if a * j > M:
                break
            seen[a*j] = 1
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
a = sorted(map(int, input().split()))
b = [0] * (10 ** 6 + 1)
c = [False] * (10 ** 6 + 1)
for i in a:
    b[i] += 1
ans = 0
for i in range(1, 10 ** 6 + 1):
    if not b[i]:
        continue
    if b[i] == 1 and not c[i]:
        ans += 1
    for j in range(1, 10 ** 6 + 1):
        if i * j > 10 ** 6:
            break
        c[i * j] = True
print(ans)

Solution (Python):

from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    a = LI()
    N = 10**6
    f = [1]*(N+1)
    a.sort()
    cnt = [0]*(N+1)
    for i in a:
        cnt[i] += 1
    for i in range(N+1):
        if cnt[i] > 1:
            f[i] = 0
            x = i
            while x <= N:
                f[x] = 0
                x += i
    ans = 0
    for i in a:
        if f[i]:
            ans += 1
            x = i
            while x <= N:
                f[x] = 0
                x += i
    print(ans)
    return


if __name__ == "__main__":
    solve()

Solution (Python):
import sys

sys.setrecursionlimit(500005)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

n = ni()
a = na()

f = [0] * 1000005
for v in a:
    f[v] += 1
for i in range(1000000, 0, -1):
    if f[i] == 0:
        continue
    j = i*2
    while j <= 1000000:
        f[j] += f[i]
        j += i
ct = 0
for v in a:
    if f[v] == 1:
        ct += 1
print(ct)