Problem:
 Score : 400 points    Problem Statement Given is a number sequence A of length N .  Find the number of integers i  \left(1 \leq i \leq N\right) with the following property:   For every integer j  \left(1 \leq j \leq N\right) such that i \neq j , A_j does not divide A_i .       Constraints  All values in input are integers.  1 \leq N \leq 2 \times 10^5  1 \leq A_i \leq 10^6         Input Input is given from Standard Input in the following format:  N  A_1  A_2  \cdots  A_N       Output Print the answer.        Sample Input 1 5
24 11 8 3 16      Sample Output 1 3  The integers with the property are 2 , 3 , and 4 .       Sample Input 2 4
5 5 5 5      Sample Output 2 0  Note that there can be multiple equal numbers.       Sample Input 3 10
33 18 45 28 8 19 89 86 2 4      Sample Output 3 5

Solution (Python):
n, *a = map(int, open(0).read().split())           
a.sort()                                           
s = set()                                          
checked = set()                                    
dup = set()                                        
count = 0                                          
for x in a:                                        
    if x in s:                                     
        if x in checked:                           
            dup.add(x)                             
        continue                                   
    count += 1                                     
    checked.add(x)                                 
    for i in range(1, 10**6 // x + 1):             
        s.add(x * i)                               
                                                   
print(count - len(dup))

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
max_a = max(a)
b = [0] * (max_a + 1)
a.sort()

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

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def make_divisors(n):
    divisors = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)
    return divisors


def solve():
    _ = int(rl())
    A = list(map(int, rl().split()))
    
    a_set = set()
    memo = set()
    for ai in A:
        if ai in a_set:
            memo.add(ai)
            if ai == 1:
                print(0)
                return
        else:
            a_set.add(ai)
    if 1 in a_set:
        print(1)
        return
    
    counter = [0] * (10 ** 6 + 1)
    for ai in A:
        for m in range(ai, 10 ** 6 + 1, ai):
            counter[m] += 1
    
    ans = 0
    for ai in A:
        if counter[ai] == 1:
            ans += 1
    print(ans)


if __name__ == '__main__':
    solve()

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

import numpy as np
from collections import Counter
from numba import njit




N = int(input())
A = np.array(readline().split(), np.int32)

count = np.zeros((A.max() + 1))
for a in A:
    if count[a] > 1:
        continue
    count[::a] += 1

ret = 0
for a in A:
    ret += count[a] == 1

print(ret)

Solution (Python):


import sys
from math import gcd
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N, *A = map(int, read().split())
A = sorted(A)
M = pow(10, 6) + 1
divs = [False] * M
cnt = 0
for i, a in enumerate(A):
    if divs[a]:
        continue

    if i == N - 1 or a != A[i + 1]:
        cnt += 1

    acc = a
    while acc < M:
        divs[acc] = True
        acc += a
print(cnt)

Solution (Python):
n,x=int(input()),10**6+100
a,b,c=list(map(int,input().split())),[0]*(2*x),0
for i in a:
    b[i]+=1
for i in range(x):
    c+=1 if b[i]==1 else 0
    if b[i]==0:
        continue
    for j in range(1,x):
        if i*j>=x:
            break
        b[i*j]=0
print(c)

Solution (Python):
INF=10**6+1
n,*l=map(int,open(0).read().split())
from collections import *
c=Counter(l)
l=sorted(c.keys())
a=[]
b=[0]*INF
for i in l: b[i]=1  
for i in l:
  if b[i]:
    if c[i]<2: a+=[i]
    for j in range(2*i,INF,i): b[j]=0
print(len(a))

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

A.sort()
max_num = A[-1]
counter = Counter(A)
s = set()
cnt = 0
for a in A:
    if a in s:
        continue
    if counter[a] == 1:
        cnt += 1
    idx = 1
    while a * idx <= max_num:
        s.add(a * idx)
        idx += 1
print(cnt)

Solution (Python):
def main():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline
    from collections import Counter

    N = int(input())
    A = list(map(int, input().split()))
    counter_A = Counter(A)
    flag = [True] * 1000001

    count = 0
    for i in sorted(counter_A.keys()):
        if counter_A[i] == 1 and flag[i]:
            count += 1
        multiple = i
        while multiple < 1000001:
            flag[multiple] = False
            multiple += i

    print(count)


main()

Solution (Python):

from collections import Counter
from itertools import accumulate

def main():
    N = int(input())
    A = sorted(map(int, input().split()))
    
    B = [0] * (A[N-1]+1)
    for i in range(N):
        j = A[i]
        while j <= A[N-1]:
            B[j] += 1
            j += A[i]
    
    ans = 0
    for i in range(N):
        if B[A[i]] == 1:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

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

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

A.sort()
b = [0]*(10**6+1)

for a in A:
  b[a] += 1
  if b[a] == 1:
    for i in range(2*a,10**6+1,a):
      b[i]+=100
print(b.count(1))

Solution (Python):
import sys
input = sys.stdin.readline
from collections import Counter, defaultdict
def main():
    N = int( input())
    A = list( map( int, input().split()))
    CA = Counter(A)
    d = defaultdict( lambda : False)
    T = [False]*(10**6+1)
    A.sort()
    Z = [False]*(10**6+1)
    ans = 0
    for a in A:
        if CA[a] == 1 and not T[a]:
            ans += 1
        if not Z[a]:
            Z[a] = True
            for i in range(1, 10**6+1):
                if i*a > 10**6:
                    break
                T[i*a] = True
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
a.sort()
MAX = 10 ** 6 + 1
flg_lst = [False] * MAX
res = 0
for i in range(n):
    if flg_lst[a[i]]:
        continue
    if i + 1 == n or a[i+1] != a[i]:
        res += 1
    for j in range(a[i], MAX, a[i]):
        flg_lst[j] = True
print(res)

Solution (Python):
n = int(input())
li = list(map(int, input().split()))
li.sort()
inf = (10**6)+1
isprime = [False]*(inf+1)
for i in li:
    isprime[i] = True
temp = 0
for i in li:
    if i == temp:
        isprime[i] = False
    if not isprime[i]:
        continue
    for k in range(i*2, inf+1, i):
        isprime[k] = False
    temp = i
prime_list = []
for i in range(len(li)):
      if i+1<len(li):
            if li[i] == li[i+1]:
                isprime[li[i]] = False
for i in range(1, inf+1):
    if isprime[i]:
        prime_list.append(i)
print(len(prime_list))

Solution (Python):
n = int(input())
A = list(map(int,input().split()))
A.sort()
B = [0]*(A[-1]+1)
ans = 0
for i,a in enumerate(A):
    if B[a]:
        continue
    else:
        if i+1 == n or A[i+1] != a:
            ans += 1
        x = a
        while x <= A[-1]:
            B[x] = 1
            x += a
print(ans)

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

    count = 0
    for ix, a in enumerate(A):
        if sieve[a] == 0:
            if ix == len(A) - 1 or a != A[ix+1]:
                count += 1
        else:
            continue
        intermediate_a = a
        while intermediate_a < sieve_len:
            sieve[intermediate_a] += 1
            intermediate_a += a
    print(count)



if __name__ == '__main__':
    main()

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

table = [0 for i in range(10**6 + 1)]
ans = 0
a.sort()
a.append(10**7)
for i in range(n):
    el = a[i]
    if table[el] != 0:
        continue
    else:
        if el != a[i + 1]:
            ans += 1
    idx = el
    while idx <= 10**6:
        table[idx] += 1
        idx += el

print(ans)

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N, *A = map(int, read().split())
    A.sort()

    M = 10 ** 6
    B = [True] * (M + 1)
    B[0] = False
    ans = 0
    for i in range(N):
        if not B[A[i]]:
            continue
        if i < N - 1 and A[i + 1] == A[i]:
            B[A[i]] = False
        else:
            ans += 1
        for n in range(2 * A[i], M + 1, A[i]):
            B[n] = False

    print(ans)
    return


if __name__ == '__main__':
    main()

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

cnt = [0]*(10**6+10)
for a in al:
    if cnt[a]>1:
        continue
    for i in range(0,10**6+10,a):
        cnt[i] += 1

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

Solution (Python):

import collections

def main():
    n = int(input())
    A = sorted(map(int, input().split()))

    D = collections.defaultdict(int)
    for a in A:
        D[a] += 1

    m = max(A)
    S = set()

    ans = 0
    for i in range(n):
        a = A[i]

        if a in S:
            continue

        if D[a] == 1:
            ans += 1

        num = a
        while num <= m:
            S.add(num)
            num += a

    print(ans)


main()

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

a.sort()
li = [True] * (10**6 + 10)
ans = 0

for i in range(n):
    if not li[a[i]]:
        continue
    li[a[i]] = False
    tmp = a[i]
    while tmp < len(li):
        li[tmp] = False
        tmp += a[i]
    if i < n-1:
        if a[i+1] == a[i]:
            continue
    ans += 1


print(ans)

Solution (Python):




from __future__ import division, print_function 

import sys
import os
from collections import Counter, deque, defaultdict
import itertools
import math
import io


"""Uncomment modules according to your need"""













if sys.version_info[0] < 3:
    input = raw_input
    range = xrange

    filter = itertools.ifilter
    map = itertools.imap
    zip = itertools.izip



"""value of mod"""
MOD = 998244353
mod = 10**9 + 7

"""Uncomment next 4 lines if doing huge recursion"""




def prepare_factorial(mod=mod):
    """ returns two lists, factorial and inverse factorial modulo argument by default 10**9 +7 """
    
    fact = [1]
    for i in range(1, 200005):
        fact.append((fact[-1] * i) % mod)

    ifact = [0] * 200005
    ifact[200004] = pow(fact[200004], mod - 2, mod)
    for i in range(200004, 0, -1):
        ifact[i - 1] = (i * ifact[i]) % mod

    return fact, ifact

def modinv(n, p):
    """ returns N inverse modulo p """
    return pow(n, p - 2, p)

def ncr(n, r,  fact, ifact):
    """ takes 4 arguments: n , r and factorial and inverse factorial lists"""
    t = (fact[n] * (ifact[r]*ifact[n-r]) % MOD)% MOD
    return t


def get_n(Sum):    
    """this function returns the maximum n for which Summation(n) <= Sum"""
    ans = (-1 + sqrt(1 + 8*Sum))//2
    return ans

def sieve(n):
    """ returns a list of prime numbers till n """
    if n < 2: return list()
    prime = [True for _ in range(n + 1)]
    p = 3
    while p * p <= n:
        if prime[p]:
            for i in range(p * 2, n + 1, p):
                prime[i] = False
        p += 2
    r = [2]
    for p in range(3, n + 1, 2):
        if prime[p]:
            r.append(p)
    return r



def divs(n, start=1):
    """ returns a list of all divisors till n """
    divisors = []
    for i in range(start, int(math.sqrt(n) + 1)):
        if n % i == 0:
            if n / i == i:
                divisors.append(i)
            else:
                divisors.extend([i, n // i])
    return divisors



def divn(n, primes):
    """ returns the number of divisors, two arguments n and the sieve till n """
    divs_number = 1
    for i in primes:
        if n == 1:
            return divs_number
        t = 1
        while n % i == 0:
            t += 1
            n //= i
        divs_number *= t



def lrfind(d, x, default=-1):
    """ Takes 2 arguments an iterable and an element. returns a tuple (firstoccurence,lastoccurence) -1 if not found """
    left = right = -1
    for i in range(len(d)):
        if d[i] == x:
            if left == -1: left = i
            right = i
    if left == -1:
        return default, default
    else:
        return left, right

def gcd(x, y): 
    """ returns greatest common divisor of x and y """
    while y:
        x, y = y, x % y
    return x

def check_sorted(a):
    ''' returns True/False '''
    for i in range(len(a)-1):
        if a[i]>a[i+1]:
            return False
    return True
def ceil(n, k=1): return n // k + (n % k != 0) 
def input(): return sys.stdin.readline().strip()
def ii(): return int(input()) 
def mi(): return map(int, input().split()) 
def li(): return list(map(int, input().split())) 
def lw(): return input().split() 
def lcm(a, b): return abs(a * b) // gcd(a, b) 
def prr(a, sep=' ', end='\n'): print(sep.join(map(str, a)), end=end) 
def dd(): return defaultdict(int) 
def ddl(): return defaultdict(list) 
def write(s): return sys.stdout.write(s)













def main():
    
    n=ii()
    a=li()
    b=sorted(list(set(a)))
    countd=dd()
    for i in a:
        if i in countd:
            countd[i]+=1
        else:
            countd[i]=1
    answer={}
    for i in b:
        if countd[i]>1:
            answer[i]=False
        else:
            answer[i]=True
    for i in b:
        multiplier=2
        while(i*multiplier<=10**6):
            if i*multiplier in answer:
                answer[i*multiplier]=False
            multiplier+=1
    count=0
    for i in answer:    
        if answer[i]==True:
            count+=1
    print(count)






























""" -------- Python 2 and 3 footer by Pajenegod and c1729 ---------"""

py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange

import os, sys
from io import IOBase, BytesIO

BUFSIZE = 8192

class FastIO(BytesIO):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
        return s

    def read(self):
        while self._fill(): pass
        return super(FastIO, self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill();
            self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

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


class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            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')



""" main function"""

if __name__ == '__main__':
    main()

Solution (Python):
n,*a=map(int,open(0).read().split())
m=max(a)+9
l=[0]*m
for x in a:l[x]+=1
r=0
for i in range(m):
	if l[i]:
		r+=l[i]==1
		for j in range(i,m,i):l[j]=0
print(r)

Solution (Python):
from decimal import Decimal
from collections import Counter

N = int(input())
A = sorted([int(_) for _ in input().split()])
max_a = max(A)
min_a = min(A)
counter_A = Counter(A)
set_A = set(A)

for a in A:
  if a not in set_A:
    continue
  
  if counter_A[a] > 1:
    set_A.remove(a)
  
  i = 2
  while True:
    num = a * i
    if num > max_a:
      break
    if num in set_A:
      set_A.remove(num)
    i += 1

print(len(set_A))

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
a.sort()
M=max(a)
p=[]
for i in range(n):
    if i+1<=n-1:
        if a[i]==a[i+1]:
            p+=[j for j in range(a[i],M+1,a[i])]
        else:
            p+=[j for j in range(a[i]*2,M+1,a[i])]
    else:
        p+=[j for j in range(a[i]*2,M+1,a[i])]

print(len(set(set(a)-set(p))))

Solution (Python):
from collections import Counter
n = int(input())
A = sorted(map(int, input().split()))
M = A[-1]
c = Counter(A)
s = set()
ans = 0
for a in A:
    if a in s:
        continue
    if c[a] == 1:
        ans += 1
    i = 1
    while a * i <= M:
        s.add(a * i)
        i += 1
print(ans)

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

ans = 0

baisu = [0]*(a[n-1]+1)
an = a[n-1]

for i in range(n):
    a0 = a[i]
    a1 = a0
    while a1 <= an:
        baisu[a1] += 1
        a1 += a0


for i in range(n):
    if baisu[a[i]] == 1:
        ans += 1
print(ans)

Solution (Python):
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
A.sort()
c = Counter(A)
lst = [1] * (10**6+1)
res = 0

for i,a in enumerate(A):
  if lst[a] == 0: continue
  if i==N-1 or A[i+1] != a:
    res += 1
  for j in range(a, 10**6+1, a):
    lst[j] = 0

print(res)

Solution (Python):
from collections import Counter

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

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

for k, v in c.items():
    t = k*2
    while t <= 10**6:
        p[t] = False
        t += k

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

Solution (Python):
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time


def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def print_matrix(mat):
    for i in range(len(mat)):
        print(*['IINF' if v == IINF else "{:0=4}".format(v) for v in mat[i]])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
show_flg = False






















def primes(n):
    is_prime = [1] * (n + 1)
    is_prime[0] = 0
    is_prime[1] = 0
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = 0
    return is_prime


def is_prime(n):
    if n == 1:
        return False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
             return False
    return True


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def coprime(a, b):
    return gcd(a, b) == 1


def factorization(n):
    if n <= 1:
        return []

    ret = []
    while n > 2 and n % 2 == 0:
        ret.append(2)
        n //= 2
    i = 3
    while i <= math.sqrt(n):
        if n % i == 0:
            ret.append(i)
            n //= i
        else:
            i += 2
    ret.append(n)
    return ret


def main():
    N = I()
    A = LI()
    MX = 2 * 10**6
    ans = []

    
    
    
    
    
    
    
    

    
    

    a_map = Counter(A)

    n = MX
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = 1 in a_map
    for i in range(1, 10**6 + 1):
        if not is_prime[i]:
            continue
        if i not in a_map:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False

    ans = 0
    for i in range(N):
        if is_prime[A[i]] and a_map[A[i]] == 1:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter

from functools import lru_cache

sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


n = inp()
a = sorted(inpl())
cnt = collections.Counter(a)
ans = 0
dp = [0] * (10**6 + 1)
for i in a:
    if dp[i] == 0:
        for j in range(1, 10**7):
            if i * j > 10**6:
                break
            dp[i * j] = 1
        if cnt[i] == 1:
            ans += 1
print(ans)

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



sys.setrecursionlimit(10000000)

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

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

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


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


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

    N = ii()
    A = il()
    A.sort()

    already = set()
    cnt = collections.Counter(A)
    mx = max(A)
    ret = 0
    for a in A:
        if a in already: continue
        if cnt[a] == 1:
            ret += 1

        i = 1
        while a * i <= mx:
            already.add(a * i)
            i += 1
    print(ret)


if __name__ == '__main__':
    main()

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

d = {}
for a in A:
    d.setdefault(a, 0)
    d[a] += 1

A = sorted(set(A))
t = [True] * (10 ** 6 + 1)

for a in A:
    for i in range(a + a, 10 ** 6 + 1, a):
        t[i] = False

for a in d:
    if d[a] > 1:
        t[a] = False

result = 0
for a in A:
    if t[a]:
        result += 1
print(result)

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()))
s = set(A)
counter = Counter(A)
A.sort()
ans = [1]*(10**6+1)
for i in range(1,10**6+1):
    if i in s and ans[i]:
        tmp = i
        cnt = 2
        while tmp*cnt <= 10**6:
            ans[tmp*cnt] = 0
            cnt += 1
    else:
        ans[i] = 0
    if counter[i] != 1:
        ans[i] = 0
print(sum(ans)-1)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
ans = [0]*(10**6+1)
mul = set()
for i in range(N):
	if ans[A[i]] == 0:
		ans[A[i]] = 1
		p = A[i]*2
		while p <= 10**6:
			ans[p] = -1
			p += A[i]
	elif ans[A[i]] == 1:
		ans[A[i]] = 2

q = 0	
for i in range(10**6+1):
	if ans[i] == 1:
		q += 1
print(q)

Solution (Python):
from collections import Counter
import bisect

N = int(input())
cnt_A = Counter(map(int, input().split()))
keys = sorted(cnt_A.keys())
max_keys = max(keys)
flags = {key: True for key in keys}

for key in keys:
    if flags[key] is False:
        continue

    factor = 2
    while key * factor <= max_keys:
        idx = bisect.bisect(keys, key * factor)
        if keys[max(0, idx - 1)] == key * factor:
            del cnt_A[key * factor]
            flags[key * factor] = False
        factor += 1

print(sum([val if val == 1 else 0 for val in cnt_A.values()]))

Solution (Python):
n,x=int(input()),10**6+100
a,b,c=list(map(int,input().split())),[0]*(2*x),0
for i in a:
    b[i]+=1
for i in range(x):
    c+=1 if b[i]==1 else 0
    if b[i]==0:
        continue
    for j in range(1,x):
        if i*j>=x:
            break
        b[i*j]=0
print(c)

Solution (Python):
from math import gcd
from collections import Counter
n = int(input())
a = list(map(int,input().split()))
a.sort()
if n == 1:
    print(1)
    quit()
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
M = max(a)
cnt = [0]*(M+1)
ans = 0
for i in range(n):
    if cnt[a[i]]:
        continue
    j = a[i]
    if i == 0:
        if a[i] == a[i+1]:
            1
        else:
            ans += 1
    elif i == n-1:
        if a[i-1] == a[i]:
            1
        else:
            ans += 1
    elif a[i] == a[i+1] or a[i-1] == a[i]:
        1
    else:
        ans += 1
    while j <= M:
        cnt[j] = 1
        j += a[i]
print(ans)

Solution (Python):
from collections import defaultdict
import math
SUPER_A=10**6+1
n=int(input())
a_array=list(map(int,input().split()))
a_array.sort()
div_dict=defaultdict(bool)
count=0
for i in range(n):
    a=a_array[i]
    if div_dict[a]:
        count+=1
    else:
        for j in range(1,math.ceil(SUPER_A/a)):
            div_dict[j*a]=True
        if i + 1 < n and (a_array[i]==a_array[i+1]):
            count+=1
print(n-count)

Solution (Python):

import sys

N,*A = map(int, sys.stdin.buffer.read().split())

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

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

count = 0
for i in range(1,10**6+1):
  if T[i] == 1:
    continue
  if S[i] == 0:
    continue
  if S[i] == 1:
    count += 1
  for j in range(10**6//i+1):
    T[i*j] = 1

print(count)

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

table = [0 for i in range(10**6+1)]
ans = 0
a.sort()
a.append(10**7)
for i in range(n):
    el = a[i]
    if table[el] != 0:
        continue
    else:
        if el != a[i+1]:
            ans += 1
    idx = el
    while idx <= 10**6:
        table[idx] += 1
        idx += el

print(ans)

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

ac = A.count(1)
if ac == 1:
    print(1)
    exit()
if ac >= 2:
    print(0)
    exit()

num = [0]*1000005
for a in A:
    num[a] += 1

b = [False]*1000005
seen = [False]*1000005
cnt = 0
A = list(set(A))
A.sort()
for a in A:
    if seen[a]:
        continue

    seen[a] = True
    if b[a] == False:
        cnt += 1
        if num[a] > 1:
            cnt -= 1

    for i in range(a, 1000005, a):
        b[i] = True
print(cnt)

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

A.sort()

maxv = A[-1]
minv = A[0]

cash = set()
ok = set()
ans = 0
p = set()

for i in A:
    if i in cash:
        if i in p:
            ans -= 1
            p.remove(i)
        continue

    else:
        
        
        p.add(i)

        ans += 1

        c = 1
        cur = i

        while cur <= maxv:
            cash.add(cur)
            c += 1
            cur = i * c


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
P = [0] * (10**6+1)

for a in A:
    if P[a]==0:
        for i in range(10**7):
            x = a*i
            if x>10**6:
                break
            P[x] = 1
        if cnt[a]==1:
            ans +=1

print (ans)

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

s = set()
x = a[0]

count = 0
for i in range(n):
    flg = True
    flg2 = False
    if i < n - 1 and a[i] == a[i + 1]:
        flg = False
        flg2 = True
    if a[i] in s:
        flg = False
        flg2 = False

    if flg:
        count += 1
    if flg or flg2:
        x = a[i]
        while x <= 10 ** 6:
            s.add(x)
            x += a[i]
print(count)

Solution (Python):
N = int(input())
a = [int(x) for x in input().split()]
from collections import defaultdict
d = defaultdict(int)
ans = 0
for i in range(N):
    d[a[i]] += 1
for i in range(1,1000001):
    if d[i] == 1:
        ans += 1
        for j in range(2,2+10**6//i):
            d[j*i] = 0
    elif d[i] >= 2:
        for j in range(2,2+10**6//i):
            d[j*i] = 0
print(ans)

Solution (Python):

import sys
import math

sys.setrecursionlimit(10 ** 6)

def debug(s):
    if True:
        print(s)

def get_sieve_of_eratosthenes(n):
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while False:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

def filterTrue(a):
    return a

def solve(N: int, A: "List[int]"):
    A = sorted(A)
    table = [False for i in range(A[-1]+1)]
    alreadyDid = set()
    for a in A:
        table[a] = True
    for a in A:
        if a in alreadyDid:
            table[a] = False
            continue
        alreadyDid.add(a)
        i = a*2
        while i < len(table):
            table[i] = False
            i += a
    print(len(list(filter(filterTrue,table))))
    return



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