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

Solution (Python):
from sys import stdin

def main():

    n = int(stdin.readline().strip())
    a = list(map(int, stdin.readline().strip().split()))

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

    a.sort()

    dp = [True] * (a[-1] + 1)
    ans = 0

    for i in range(n):

        if a[i] == a[i-1]:
            continue

        if dp[a[i]]:

            for j in range(2 * a[i], a[-1] + 1, a[i]):
                dp[j] = False

            if i == n-1 or a[i] != a[i+1]:
                ans += 1

    print(ans)

main()

Solution (Python):
from sys import stdin

def main():

    n = int(stdin.readline().strip())
    a = list(map(int, stdin.readline().strip().split()))

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

    a.sort()

    dp = [True] * (a[-1] + 1)
    ans = 0

    for i in range(n):

        if a[i] == a[i-1]:
            continue

        if dp[a[i]]:

            for j in range(2 * a[i], a[-1] + 1, a[i]):
                dp[j] = False

            if i == n-1 or a[i] != a[i+1]:
                ans += 1

    print(ans)

main()

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

a.sort()

c = [0]*a[-1]

for ai in a:
    if c[ai-1] >= 1:
        c[ai-1] += 1
        continue
    i = ai
    while i <= a[-1]:
        c[i-1] += 1
        i += ai
print(sum(c[ai-1] == 1 for ai in a))

Solution (Python):
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
a.sort()
c = Counter(a)
m = max(a) + 1
dp = [False]*m
ans = 0
for ai in a:
    if dp[ai]:
        continue
    if c[ai] == 1:
        ans += 1
    for i in range(ai, m, ai):
        dp[i] = True
print(ans)

Solution (Python):
import math
N = int(input())
A = list(map(int,input().split()))
M = max(A)
cnt = [0 for i in range(M)]
for i in range(N):
    if cnt[A[i]-1] != 0:
        cnt[A[i]-1] = 2
    else:
        j = A[i]-1
        while j<M:
            cnt[j] += 1
            j += A[i]

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

Solution (Python):

listA=[]
while True:
    try:
        listA.append(list(map(int,input().split())))
    except:
        break;

lis=listA[1]
m=max(lis)
lis0=[0]*(m+1)
for i in lis:
    if lis0[i]!=2: 
        j=1
        while i*j<=m:
            lis0[i*j]+=1
            j+=1
            
count=0
for i in lis:
    if lis0[i]==1: count+=1
print(count)

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():

    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]
        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 += 1 + i % 2
            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 primeFactor2(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 += 1 + i % 2
            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)
        
        
    
    mod=10**9+7
    N=I()
    A=LI()
    from collections import defaultdict
    dd = defaultdict(int)
    for i in range(N):
        dd[A[i]]+=1
        
    A.sort()
    
    ans=0
    for i in range(N):
        if dd[A[i]]<2:
            L=divisors(A[i])
            flag=1
            for v in L[:-1]:
                if dd[v]:
                    flag=0
                    break
            if flag:
                ans+=1
                
    if A.count(1)==1:
        ans=1
    
                
    print(ans)
                    
        
        

                
    
    


main()

Solution (Python):
n=int(input())
l=list(map(int,input().split()))
ml=max(l)
m=[0]*(ml+1)
for i in l:
    m[i]+=1
for i in range(ml+1):
    if m[i]>=1:
        for j in range(2*i,ml+1,i):
            if m[j]>0:
                m[j]=0
                
for i in range(ml+1):
    if m[i]>=2:
        m[i]=0
print(sum(m))

Solution (Python):
n=int(input())
l=list(map(int,input().split()))
ml=max(l)
m=[0]*(ml+1)
for i in l:
    m[i]+=1
for i in range(ml+1):
    if m[i]>=1:
        for j in range(2*i,ml+1,i):
            if m[j]>0:
                m[j]=0
                
for i in range(ml+1):
    if m[i]>=2:
        m[i]=0
print(sum(m))

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

A.sort()
C = [0] * A[-1]
for Ai in A:
    if C[Ai - 1] >= 1:
        C[Ai - 1] += 1
        continue
    i = Ai
    while i <= A[-1]:
        C[i - 1] += 1
        i += Ai
print(sum([C[Ai - 1] == 1 for Ai in A]))

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

a.sort()
am = a[-1]

memo = [0] * (am+1)

for ai in a:
    memo[ai] = 1

p = -1

for ai in a:
    if ai == p:
        memo[ai] = 0
        continue
    for j in range(2, am // ai + 1):
        memo[ai * j] = 0
    p = ai

print(sum(memo))

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

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

C = {a: 0 for a in A}
for a in A:
    C[a] += 1

D = {a: 0 for a in A}
for a in A:
    if C[a] > 0:
        t = 2
        while a * t <= maxA:
            D[a * t] = 1
            t += 1

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

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

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

ans = 0
d = {}


for i in range(len(a)):
    if a[i] in d.keys():
        d[a[i]] += 1
    else:
        d[a[i]] = 1
max_ = max(a)
arr = [True] * (max_+1) 
ans = 0

for i in range(1, max_+1):
    if i in d.keys() and arr[i]:
        temp = i
        
        while (temp + i) <= (max_):
            
            arr[(temp+i)] = False

            temp += i

        if d[i] == 1:
            ans += 1

print(ans)

Solution (Python):



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

num = max(l)+1
rcd = [0 for _ in range(num)]

for x in l: 
    for y in range(x, num, x): 
            rcd[y] += 1

ans = 0
for k in l: 
    if rcd[k] == 1: 
        ans += 1

print(ans)

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

num = max(l)+1
rcd = [0 for _ in range(num)]

for x in l:
    for y in range(x, num, x):
            rcd[y] += 1

ans = 0
for k in l:
    if rcd[k] == 1:
        ans += 1

print(ans)

Solution (Python):
from collections import deque,Counter

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

memo = [0] * (10**6+10)
cnt = Counter(A)
for k,v in cnt.items():
    if memo[k] > 1:
        continue
    for j in range(k,10**6+1,k):
        memo[j] += v 



ans = 0
for num in cnt:
    ans += (memo[num] == 1)

print(ans)

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

num = max(l)+1
rcd = [0 for _ in range(num)] 

for v in l: 
    rcd[v] += 1

unq = []
for w in range(num): 
    if rcd[w] == 1:
        unq.append(w)


rcd = [0 for _ in range(num)] 

for x in l: 
    for y in range(2*x, num, x): 
        rcd[y] = 1 


ans = 0
for z in unq: 
    if rcd[z] == 0: 
        ans += 1 
print(ans)

Solution (Python):
import math


def main():
    amax = int(1e6+1)
    n = int(input())
    a = [int(v) for v in input().split()]
    dp = [0 for _ in range(amax)]
    dup = {}
    a.sort()
    for v in a:
        if dup.get(v) is None:
            dup[v] = 0
        else:
            dup[v] = 1
            continue
        if dp[v] == 0:
            for i in range(2, amax):
                if i * v > 1e6:
                    break
                dp[i*v] = 1
    ans = 0
    for v in a:
        if dp[v] == 0 and dup[v] == 0:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

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):
def primes(n):
    ass = []
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    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] = False
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass

def main():
    N = int(input())
    A = list(map(int, input().split()))
    max_A = max(A)
    ans = [0] * (max_A + 1)
    A.sort()
    for a in A:
        tmp = 1
        b = 0
        while b <= max_A:
            b = a * tmp
            if b > max_A:
                break
            ans[b] += 1
            tmp += 1
    cnt = 0
    for a in A:
        if ans[a] == 1:
            cnt += 1

    print(cnt)


if __name__ == "__main__":
    main()

Solution (Python):
def solve(n,a):
    m = max(a)
    dp = [False]*(m+1)
    dup = []
    for ai in a:
        if dp[ai]:
            dup.append(ai)
        dp[ai] = True
    for ai in a:
        for i in range(2,m//ai+1):
            dp[ai*i] = False
    for ai in dup:
        dp[ai] = False
    return dp.count(True)




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

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

INF = int(1e10)
MOD = int(1e9 + 7)
M = 10 ** 6 + 5

def main():
    from builtins import int, map
    N = int(input())
    A = list(map(int, input().split()))
    cnt = [0] * M

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

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

if __name__ == '__main__':
    main()

Solution (Python):



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


num = max(l)+1
rcd = [0 for _ in range(num)] 

for v in l: 
    rcd[v] += 1

unq = []
for w in range(num): 
    if rcd[w] == 1: 
        unq.append(w)



rcd = [0 for _ in range(num)] 
l = set(l) 
for x in l: 
    for y in range(2*x, num, x): 
        rcd[y] = 1 



ans = 0
for z in unq: 
    if rcd[z] == 0: 
        ans += 1 
print(ans)

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

num = max(l)+1
rcd = [0 for _ in range(num)]

for v in l:
    rcd[v] += 1

unq = []
for w in range(num):
    if rcd[w] == 1:
        unq.append(w)


rcd = [0 for _ in range(num)]
l = set(l)
for x in l:
    for y in range(2*x, num, x):
        rcd[y] = 1


ans = 0
for z in unq:
    if rcd[z] == 0:
        ans += 1
print(ans)

Solution (Python):
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    a_max = a[-1]
    is_divisible = [True]*(a_max+1)
    ans = 0
    is_divisible[0]= False
    el_old = 0
    for el in a:
        if is_divisible[el]:
            if el == el_old:
                ans-=1
                is_divisible[el] = False
                continue
            ans +=1
            k = 2
            while k*el <= a_max:
                is_divisible[k*el] = False
                k+=1
        el_old = el
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
remain = [0 for i in range(max(a) + 1)]
for ai in a:
    remain[ai] += 1
res = 0
max_a = max(a)
for i in range(1, max_a + 1):
    if remain[i] == 1:
        res += 1
    if remain[i]:
        for j in range(i * 2, max_a + 1, i):
            remain[j] = 0
print(res)

Solution (Python):

from collections import Counter
n, *A = map(int, open(0).read().split())
A.sort()
c, s = Counter(A), set()
M = max(A) + 1
ans = 0
for a in A:
    if a in s:
        continue
    ans += c[a] == 1
    for i in range(a, M, a):
        s.add(i)
print(ans)

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

Solution (Python):
from collections import Counter

n = int(input())
a = [int(x) for x in input().split()]
cnt = [0] * (10**6 + 1)

dic = Counter(a)

for i in set(a):
    if 1 < dic[i]:
        cnt[i] += 1
        
a = list(set(a))
a_max = max(a)
for i in a:
    for j in range(1, 10**6 + 1):
        if a_max < i * j:
            break
        
        cnt[i * j] += 1

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

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))


n = inp()
a = inpl()
c = Counter(a)
a.sort()
s = set()
res = 0
for x in a:
    if x in s:
        continue
    if c[x] == 1:
        res += 1
    b = 1
    while b*x <= 10**6:
        s.add(b*x)
        b += 1
print(res)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
A.sort()
bs = [True] * (A[-1] + 1)
bs[0] = False
last = None
for a in A:
    if bs[a]:
        start = 2 * a if a != last else a
        for j in range(start, A[-1] + 1, a):
            bs[j] = False
    last = a
print(len({a for a in A if bs[a]}))

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
a.sort()
flag = [True] * (a[-1] + 1)
memo = -1
for i in a:
    if memo == i:
        flag[i] = False
        continue
    memo = i
    tmp = 2 * i
    while tmp <= a[-1]:
        flag[tmp] = False
        tmp += i
ans = 0
for i in a:
    if flag[i]: ans += 1
print(ans)

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

num = 0

a_max = max(as_)
a_valid_map = [True] * (a_max + 1)
for i in range(len(as_) - 1):
    a = as_[i]
    if a_valid_map[a]:
        for j in range(a_max // a + 1):
            a_valid_map[a * j] = False
        if a != as_[i + 1]:
            num += 1
if a_valid_map[a_max]:
    num += 1

print(num)

Solution (Python):
def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    pre_A = -1
    dp = [True for i in range(A[-1]+1)]
    for i in range(N):
        if pre_A != A[i]:
            for j in range(2, A[-1]+1):
                x = j*A[i]
                if x <= A[-1]:
                    dp[x] = False
                else:
                    break
            pre_A = A[i]
        else:
            dp[A[i]] = False

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

resolve()

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
A.sort()
A_max = A[N-1]

boo = [1 for _ in range(A_max +1)]
tmp = A[0] 
kosuu = 2
while tmp * kosuu <= A_max:
    boo[tmp * kosuu] = 0
    kosuu += 1
pre = tmp
for i in range(1,N):
    tmp = A[i]
    if tmp == pre:
        boo[tmp] = 0
    else:
        kosuu = 2
        while tmp * kosuu <= A_max:
            boo[tmp * kosuu] = 0
            kosuu += 1
        pre = tmp
        
total = 0
for x in A:
    total += boo[x]
print(total)

Solution (Python):
def main():
    s = [input() for l in range(2)]
    N, A = int(s[0]), [int(x) for x in s[1].split()]
    """
    results = []

    for i in range(0, (N), 1):
        flag = 0
        for j in range(0, (N), 1):
            if i == j:
                pass
            else:
                if A[i] % A[j] == 0:
                    flag = 1
                    break
                else:
                    pass
        if flag == 1:
            results.append(0)
        else:
            results.append(1)
    cnt = 0
    for x in results:
        if x == 1:
            cnt += 1
    print(cnt)
    """
    
    maxA = max(A)
    
    C = {a: 0 for a in A}
    
    
    for a in A:
        C[a] += 1
    
    D = {a: 0 for a in A}
    for a in A:
        if C[a] > 0:
            t = 2
            while a * t <= maxA:
                D[a*t] = 1
                t+= 1

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



if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
a = sorted(list(map(int, input().split())))
max_a = a[-1]

q = [0] * (max_a + 1)
for i in a:
    if q[i] == 1 or q[i] == -1:
        q[i] = -1
        continue
    for j in range(2*i, max_a+1, i):
        q[j] = -1
    q[i] = 1

total = 0
for i in q:
    if i == 1:
        total += 1
print(total)

Solution (Python):
n = int(input()) 
*A, = map(int, input().split())
maxA = max(A)



C = {a : 0 for a in A}



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


D = {a : 0 for a in A}

for a in A:
    if C[a] > 0:
        t = 2
        while a*t <=maxA:
            
            
            D[a*t] = 1
            t += 1

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

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

if a[0] == a[-1]:
  if n > 1:
    print(0)
  else:
    print(1)
  exit()

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]
    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 ret
    
s = set()
ans = 0
for nm,i in enumerate(a):
  c = set(divisors(i))
  if c&s == set() and ((nm < n-1 and a[nm+1] != i) or nm == n-1): 
    ans += 1
  s.add(i)

print(ans)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

if a[0] == a[-1]:
  if n > 1:
    print(0)
  else:
    print(1)
  exit()

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 ret
    
s = set()
ans = 0
for nm,i in enumerate(a):
  c = set(divisors(i))
  if c&s == set() and ((nm < n-1 and a[nm+1] != i) or nm == n-1): 
    ans += 1
  s.add(i)

print(ans)

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

limit = max(A) + 1

dp = [True] * (limit + 1)
d = {}

for i in A:
    p = 2
    while i*p<=limit:
        dp[i*p] = False
        p += 1
    d.setdefault(i, 0)
    d[i] += 1

ans = []
for i in A:
    if dp[i] and d[i] == 1:
        ans.append(i)
print(len(ans))

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

count = Counter(lista)
lista.sort()

M = 1000001
P = [0] * (M+1)
ans = 0

for i in lista:
    if P[i] == 0:
        for j in range(M+1):
            x = i * j
            if x > M:
                break
            P[x] = 1
        if count[i] == 1:
            ans += 1

print(ans)

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

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

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

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

def calculate(n, arr):
    krr = [0 for i in range(1, 1000007)]

    for i in range(n):
        start = arr[i]

        if krr[start] > 0:
            krr[start] = 2
            continue

        for j in range(start, 1000006, start):
            krr[j] += 1

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

    print(result)


calculate(N, ARR)

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


from collections import Counter
def Main(N, A):
    A.sort()
    amax = A[-1]+1
    d = {}
    for i in range(1, amax):
        d[i] = 0
    for a in A:
        i = 1
        while a*i < amax:
            d[a*i] += 1
            i += 1
    ans = 0
    for a in A:
        if d[a] == 1:
            ans += 1
    return ans

print(Main(N, A))

Solution (Python):

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

    m = max(A) + 1
    dp = [0] * m

    for a in sorted(A):
        if dp[a] != 0:
            dp[a] = 2
            continue
        for i in range(a, m, a):
            dp[i] += 1

    print(sum(dp[i] == 1 for i in A))


if __name__ == '__main__':
    main()

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


dp = [False for _ in range(1000001)]

d = {}
for a in aL:
    if a in d:
        d[a] += 1
    else:
        d[a] = 1

ans = 0
for a in aL:
    if dp[a]:
        continue
    if d[a] > 1:
        c = 1
        while a * c <= 1000000:
            dp[a * c] = True
            c += 1
        continue
    ans += 1

    c = 1
    while a * c <= 1000000:
        dp[a * c] = True
        c += 1

print(ans)

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

multiple = [False] * 1_000_001
once = set()
twice = set()
count = 0

for a in sorted(map(int, input().split())):
  if a in once:
    if a in twice:
      continue
    else:
      count -= 1
      twice.add(a)
  elif multiple[a]:
    continue
  else:
    count += 1
    once.add(a)
    for x in range(a, 1_000_001, a):
      multiple[x] = True
print(count)

Solution (Python):
from collections import Counter
def main():
    M = 10 ** 6
    _ = int(input())
    A = list(map(int,input().split()))
    erato = [True] * (M+10)
    m = sorted(Counter(A).items())
    ans = 0
    for t in m:
        if t[1] == 1 and erato[t[0]]:
            ans += 1
        for i in range(t[0],M+1,t[0]):
            erato[i] = False
            
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter
def main():
    M = 10 ** 6
    _ = int(input())
    A = list(map(int,input().split()))
    erato = [True] * (M+10)
    m = Counter(A)
    one = []
    for k,v in m.items():
        if v == 1:
            one.append(k)
        else:
            for i in range(k,M+1,k):
                erato[i] = False
    one.sort()
    ans = 0 
    for i in one:
        ans += 1 if erato[i] else 0
        for j in range(i,M+1,i):
            erato[j] = False

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin
 
N = int(input())
A = sorted(int(x) for x in input().split())
max_num = A[-1] + 1
count = [0] * max_num

for i in A:
    if count[i] != 0:
        count[i] = 2
        continue
    else:
        for j in range(i, max_num, i):
            count[j] += 1

sum_num = sum(count[i] == 1 for i in A)
print(sum_num)

Solution (Python):
def main():
    M = 10 ** 6
    _ = int(input())
    A = list(map(int,input().split()))
    erato = [True] * (M+10)
    m = dict()
    for i in A:
        if i in m:
            m[i] += 1
        else:
            m[i] = 1
    one = []
    for k,v in m.items():
        if v == 1:
            one.append(k)
        else:
            for i in range(k,M+1,k):
                erato[i] = False
    one.sort()
    ans = 0 
    for i in one:
        ans += 1 if erato[i] else 0
        for j in range(i,M+1,i):
            erato[j] = False

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
if __name__ == "__main__":
    n = int(input())
    l_a = list(map(int, input().split()))
    s_a = list(set(l_a))

    s_a.sort()

    dub_a = [0]*(max(s_a)+1)

    for i in l_a:
        dub_a[i] += 1

    dp = [1]*(max(s_a)+1)

    for i in s_a:
        if dp[i] == 0:
            pass
        else:
            for j in range(2*i, len(dp), i):
                dp[j] = 0


    count = 0
    for i in s_a:
        if dp[i]==1 and dub_a[i]==1:
            count += 1
    print(count)

Solution (Python):
N = int(input())
A = list(map(int, input().split(" ")))
a_max = max(A)
cnts = [0] * (a_max + 1)
for a in A:
    v = a
    while v <= a_max:
        cnts[v] += 1
        v += a
cnt = 0
for a in A:
    if cnts[a] == 1:
        cnt += 1
print(cnt)

Solution (Python):
n = int(input())
a = sorted(list(map(int, input().split())))
amax = a[-1]

ans = 0
tmp = 0
prev = 0
t = [False] * (amax + 1)
for i in a:
    if i != prev:
        ans += tmp
    tmp = 0
    if not t[i]:
        tmp += 1
        k = i
        while k <= amax:
            t[k] = True
            k += i
    prev = i
ans += tmp
print(ans)