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

A.sort()

cnt = 0




dp = [True] * (A[-1] + 1)


for i in range(N):
    if dp[A[i]] == True:
        
        for j in range(A[i], A[-1] + 1, A[i]):
            dp[j] = False

        if i < N - 1:
            
            
            if A[i] != A[i + 1]:
                cnt += 1
        
        
        elif i == N - 1:
            cnt += 1

print(cnt)

Solution (Python):
from collections import Counter
n = int(input())
a = sorted(map(int, input().split()))
c = Counter(a)
s = set()
for i in range(n):
    if a[i] in s:
        continue
    elif c[a[i]] >= 2:
        s.add(a[i])
    for j in range(2,10**6//a[i]+1):
        s.add(a[i]*j)
print(sum(not (ai in s) for ai in a))

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

Solution (Python):
from collections import Counter
n = int(input())
a = sorted([int(x) for x in input().split()])
freq = Counter(a)
A = max(a)
good = [True]*(A+1)
ans = 0
for x in freq:
	for k in range(2*x,A+1,x):
		good[k] = False
	if good[x] and freq[x]==1:
		ans += 1
print(ans)

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

for i in range(N-1):
  if dp[A[i]] == True:
    for j in range(A[i], A[-1]+1,A[i]):
      dp[j] = False
    if A[i] != A[i+1]:
      cnt+=1
if dp[A[-1]] == True:
  cnt+=1
print(cnt)

Solution (Python):
N, *A = map(int, open(0).read().split())
A.sort()
dp = [True]*3*int(1e6)
x = -1
for a in A:
  if a == -1: continue
  x = a
  while x <= A[-1]:
    x += a
    dp[x] = False
  x = a

res = 0
for i, a in enumerate(A):
  if i > 0 and a == A[i-1]: continue
  if i < N-1 and a == A[i+1]: continue
  if dp[a]: res += 1
print(res)

Solution (Python):
def main():
    n = int(input())
    a = sorted(list(map(int,input().split())))
    dp = [0 for i in range(a[-1]+1)]
    lbl = []
    for i in range(n):
        if dp[a[i]]==2:
            lbl.append(a[i])
            continue
        if dp[a[i]]==1:
            continue
        else:
            for j in range(1,a[-1]//a[i]+1):
                dp[a[i]*j] = 1
            dp[a[i]] = 2
    for i in range(len(lbl)):
        dp[lbl[i]] = 0
    ans = 0
    for i in range(len(dp)):
        if dp[i] == 2:
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
memo = [0] * (10**6 + 1)
f = defaultdict(int)
for i in a:
    if f[i] > 1:
        continue
    f[i] += 1
    for j in range(i, 10**6+1, i):
        memo[j] += 1

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

Solution (Python):
from collections import Counter
n = int(input())
a = sorted(map(int, input().split()))
c = Counter(a)
s = set()
for i in range(n):
    if a[i] in s:
        continue
    elif c[a[i]] >= 2:
        s.add(a[i])
    for j in range(2,10**6//a[i]+1):
        s.add(a[i]*j)
print(sum([not (ai in s) for ai in a]))

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
a.sort()
max_num = a[-1] + 1
cnt = [0] * (max_num)
a.sort()
ans = 0


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

a = set(a)

for k in a:
    for l in range(k * 2, (max_num), k):
        cnt[l] += 1

for m in a:
    if cnt[m] == 1:
        ans += 1
    


print(ans)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
a.sort()
max_num = a[-1] + 1
cnt = [0] * (max_num)
a.sort()
ans = 0


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

a = set(a)

for k in a:
    for l in range(k * 2, (max_num), k):
        cnt[l] += 1

for m in a:
    if cnt[m] == 1:
        ans += 1
    


print(ans)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
cnt = [0] * (10 ** 6 + 1)
a.sort()
ans = 0


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

a = set(a)

for k in a:
    for l in range(k * 2, (10 ** 6 + 1), k):
        cnt[l] += 1

for m in a:
    if cnt[m] == 1:
        ans += 1
    


print(ans)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
cnt = [0] * (10 ** 6 + 1)
a.sort()
ans = 0


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

a = set(a)

for k in a:
    for l in range(k * 2, (10 ** 6 + 1), k):
        cnt[l] += 1

for m in a:
    if cnt[m] == 1:
        ans += 1
    


print(ans)

Solution (Python):

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    ans = 0
    OK = [True for i in range(10**6+1)]
    CNT = [0 for i in range(10**6+1)]
    for x in A:
        CNT[x] += 1
        if CNT[x] == 1:
            for i in range(2, 10**6+1):
                if i*x > 10**6:
                    break
                OK[i*x] = False
    for x in A:
        if CNT[x] == 1 and OK[x]:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import Counter
n = int(input())
A = list(map(int,input().split()))
mx = max(A)
C = Counter(A)
D = {a:True for a in A}
for a in A:
    if C[a]>1: D[a]=False
    for i in range(a*2, mx+1, a):
        D[i]=False
print(sum([D[a] for a in A]))

Solution (Python):
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]



def make_adjlist_d(n, edges):
    res = [[] for _ in range(n + 1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
        res[edge[1]].append(edge[0])
    return res


def make_adjlist_nond(n, edges):
    res = [[] for _ in range(n + 1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
    return res



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


def main():
    N = NI()
    A = NLI()
    A = sorted(A)

    ma = A[-1]
    hurui = [0] * (ma + 10)
    for a in A:
        if hurui[a] == 0:
            hurui[a] = 1
        else:
            hurui[a] = 10

    for a in A:
        if hurui[a] == 0:
            continue

        for i in range(a*2, ma+10, a):
            hurui[i] = 0

    print(hurui.count(1))



if __name__ == "__main__":
    main()

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

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

max_len_A = 10**6+1
data = [0]*max_len_A
A = list(set(A))

for a in A:
    if data[a]==0:
        for j in range(a+a, max_len_A, a):
            data[j]+=1


ans = len([a for a in A if data[a]==0 and count[a]==1])
print(ans)

Solution (Python):
import sys
from collections import Counter

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

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

s = set()
cnt = Counter(a)

for i in range(n):
    if a[i] in s:
        continue
    if cnt[a[i]] >= 2:
        s.add(a[i])
    for j in range(2,10**6//a[i]+1):
        s.add(a[i]*j)

ans = 0
for i in range(n):
    if a[i] in s:
        continue
    ans += 1

print(ans)

Solution (Python):


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

    As.sort()
    amax = max(As) + 1
    lis = [True] * amax
    ans = 0

    for i in range(N-1):
        if lis[As[i]]:
            for j in range(As[i], amax, As[i]):
                lis[j] = False
            if As[i] < As[i+1]:
                ans += 1
    if lis[-1]:
        ans += 1

    return ans

if __name__ == '__main__':
    
    print(main())

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
Ad = {}
for a in A:
    Ad[a] = Ad.get(a, 0) + 1
A, maxA, ans = sorted(Ad.keys()), max(Ad.keys()), 0

for a in A:
    if Ad[a] == 1:
        ans += 1
    if Ad[a] >= 1:
        if a == 1:
            break
        m = 2
        while a * m <= maxA:
            if a * m in Ad:
                Ad[a * m] = 0
            m += 1

print(ans)

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

c.sort()
a = c[N-1]
list_c = [0]*(a+1)
for i in c:
  mal = 2
  b = i
  while i<=a:
    list_c[i]+=1
    i = b*mal
    mal+=1
count = 0
for i in c:
  if list_c[i]==1:
    count+=1
print(count)

Solution (Python):
n = int(input())
aas = sorted(list(map(int, input().split())))
aas_len = len(aas)
if aas_len == 1:
    print(1)
    exit()
aas_max = aas[-1]
arr = [1]*(aas_max+1)
for i in range(aas_len):
    if arr[aas[i]] == 0:
        continue
    if arr[aas[i]] == 1:
        arr[aas[i]] = 2
    else:
        arr[aas[i]] = 0
        continue
    idx = aas[i]*2
    while idx <= aas_max:
        arr[idx] = 0
        idx += aas[i]
res = 0
for i in aas:
    if arr[i] != 0:
        res += 1
print(res)

Solution (Python):

import sys


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


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


def main():
    N = II()
    A = LI()
    A.sort()
    MAX = 10**6+1
    All = [0] * MAX

    setA = set(A)
    for i in A:
        k = i
        All[k] += 1
        k += i
        if All[i] >= 2:
            continue
        while k < MAX:
            All[k] += 1
            k += i

    ans = 0
    for i in range(1, MAX):
        if All[i] == 1 and i in setA:
            ans += 1

    print(ans)

    
    
main()

Solution (Python):
import numpy as np

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

vals, cnts = np.unique(A, return_counts=True)

if len(vals) == 1:
    print(0 if cnts[0] > 1 else 1)
elif vals[0] == 1:
    print(0 if cnts[0] > 1 else 1)
else:
    sat = np.ones(vals.max() + 1, dtype=int)
    for x in vals:
        sat[2 * x::x] = 0
    ans = ((sat[vals] == 1) & (cnts == 1)).sum().item()
    print(ans)

Solution (Python):
import numpy as np

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

vals, cnts = np.unique(A, return_counts=True)

if len(vals) == 1:
    print(0 if cnts[0] > 1 else 1)
elif vals[0] == 1:
    print(0 if cnts[0] > 1 else 1)
else:
    sat = np.ones(vals.max() + 1, dtype=bool)
    for x in vals:
        sat[2 * x::x] = False
    ans = (sat[vals] & (cnts == 1)).sum().item()
    print(ans)

Solution (Python):
import numpy as np

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

vals, cnts = np.unique(A, return_counts=True)

if len(vals) == 1:
    print(0 if cnts[0] > 1 else 1)
elif vals[0] == 1:
    print(0 if cnts[0] > 1 else 1)
else:
    sat = np.ones(vals.max() + 1, dtype=int)
    for x in vals:
        sat[2 * x::x] = 0
    ans = ((sat[vals] == 1) & (cnts == 1)).sum().item()
    print(ans)

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


def solve(string):
    n, *a = map(int, string.split())
    table = np.array([True] * (10**6 + 1))
    ma = max(a)
    for _a in a:
        if table[_a]:
            table[2*_a:ma + 1:_a]=False
    i = np.array([k for k,v in Counter(a).items() if v==1],dtype=np.int)
    return str(table[i].sum())


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Solution (Python):
from collections import Counter


def solve(string):
    n, *a = map(int, string.split())
    table = [True] * (10**6 + 1)
    ma = max(a)
    for _a in a:
        if table[_a]:
            for i in range(2 * _a, ma + 1, _a):
                table[i] = False
    return str(sum(table[k] for k, v in Counter(a).items() if v == 1))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

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


def solve(string):
    n, *a = map(int, string.split())
    table = np.array([True] * (10**6 + 1))
    for _a in a:
        if table[_a]:
            table[2*_a::_a]=False
    i = np.array([k for k,v in Counter(a).items() if v==1],dtype=np.int)
    return str(table[i].sum())


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

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

def main():
  n = int(input())
  a = list(map(int, input().split(' ')))
  a.sort()
  a_max = a[-1]
  b = 0
  db = [0] * a_max
  for i in range(1, n-1):
    if a[i] != a[i+1] and a[i] != a[i-1]:
      db[a[i]-1] = 1
  if n == 1 or a[0] != a[1]:
    db[a[0]-1] = 1
  if n > 1 and a[-1] != a[-2]:
    db[-1] = 1
  for i in a:
    t = 2
    while(i * t <= a_max):
      db[i*t-1] = 0
      t += 1
  print(sum(db))
  

if __name__=='__main__':
  main()

Solution (Python):

import sys


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


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


def main():
    N = II()
    A = LI()
    A.sort()
    MAX = 10**6+1
    All = [0] * MAX

    setA = set(A)
    for i in A:
        k = i
        All[k] += 1
        k += i
        if All[i] >= 2:
            continue
        while k < MAX:
            All[k] += 1
            k += i

    ans = 0
    for i in range(1, MAX):
        if All[i] == 1 and i in setA:
            ans += 1

    print(ans)

    
    
main()

Solution (Python):

import sys


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


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


def main():
    N = II()
    A = LI()
    A.sort()
    MAX = A[-1]+1
    All = [0 for i in range(MAX)]

    setA = set(A)
    for i in A:
        k = i
        All[k] += 1
        k += i
        if All[i] == 2:
            continue
        while k < MAX and i in setA:
            All[k] += 1
            k += i

    ans = 0
    for i in range(1, MAX):
        if All[i] == 1 and i in setA:
            ans += 1

    print(ans)

    
    
main()

Solution (Python):
import numpy as np
n=int(input())
a=list(map(int,input().split()))+[10**6+1]
a=sorted(a)
flag=np.array([0 for i in range(10**6+1)])
ans=0
for i in range(n):
    if flag[a[i]]==0:
        flag[::a[i]]=1
        if a[i]!=a[i+1]:
            ans+=1
print(ans)

Solution (Python):
from collections import Counter, defaultdict

n = int(input())
a = list(map(int, input().split()))
dic = Counter(a)
memo1 = set()
memo2 = set()

MAX = 10 ** 6 + 1
for i in a:
  if i in memo1:
    continue
  if i in dic:
    if dic[i] > 1:
      memo2.add(i)
  for j in range(i*2, MAX, i):
    if j in dic:
      memo2.add(j)
  memo1.add(i)
ans = len(memo1) - len(memo2)
print(ans)

Solution (Python):
import sys
from collections import Counter

import numba as nb
import numpy as np

input = sys.stdin.readline


@nb.njit("i8(i8[:],i8[:])", cache=True)
def solve(keys, values):
    MAX_A = 10 ** 6
    divisible = [False] * (MAX_A + 1)
    ans = 0
    for k, v in zip(keys, values):
        if v == 1 and not divisible[k]:
            ans += 1
        for i in range(k, MAX_A + 1, k):
            divisible[i] = True
    return ans


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

    A.sort()
    c = Counter(A)
    keys = np.array(tuple(c.keys()), dtype=np.int64)
    values = np.array(tuple(c.values()), dtype=np.int64)

    ans = solve(keys, values)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import Counter

import numba as nb
import numpy as np

input = sys.stdin.readline


@nb.njit("i8(i8[:],i8[:])")
def solve(keys, values):
    MAX_A = 10 ** 6
    divisible = [False] * (MAX_A + 1)
    ans = 0
    for k, v in zip(keys, values):
        if v == 1 and not divisible[k]:
            ans += 1
        for i in range(k, MAX_A + 1, k):
            divisible[i] = True
    return ans


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

    A.sort()
    c = Counter(A)
    keys = np.array(tuple(c.keys()), dtype=np.int64)
    values = np.array(tuple(c.values()), dtype=np.int64)

    ans = solve(keys, values)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import Counter

import numba as nb
import numpy as np

input = sys.stdin.readline
MAX_A = 10 ** 6


@nb.njit("i8(i8[:],i8[:])")
def solve(keys, values):
    divisible = [False] * (MAX_A + 1)
    ans = 0
    for k, v in zip(keys, values):
        if v == 1 and not divisible[k]:
            ans += 1
        for i in range(k, MAX_A + 1, k):
            divisible[i] = True
    return ans


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

    A.sort()
    c = Counter(A)
    keys = np.array(tuple(c.keys()), dtype=np.int64)
    values = np.array(tuple(c.values()), dtype=np.int64)

    ans = solve(keys, values)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import Counter

input = sys.stdin.readline
MAX_A = 10 ** 6


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

    A.sort()
    divisible = [False] * (MAX_A + 1)
    ans = 0
    for k, v in Counter(A).items():
        if v == 1 and not divisible[k]:
            ans += 1
        for i in range(k, MAX_A + 1, k):
            divisible[i] = True

    print(ans)


if __name__ == "__main__":
    main()

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

a.sort()
amx=max(a)+1
l=[True]*amx
ans=0

for i in range(n-1):
    if l[a[i]]:
        for j in range(a[i],amx,a[i]):
            l[j]=False
        if a[i]<a[i+1]:
            ans+=1

if l[-1]:
    ans+=1

print(ans)

Solution (Python):
import numpy as np
from collections import Counter
n = int(input())
aa = list(map(int, input().split()))
ngs = np.zeros((10**6)+1, dtype=int)

for a in set(aa):
    ngs[2*a::a] = 1
    
dic = Counter(aa)
times = np.array(list(dic.keys()))[np.array(list(dic.values())) > 1]

for i in times:
    ngs[i] = 1
cnt = 0
for a in aa:
    cnt += 1-ngs[a]
print((cnt))

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

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






N = getN()
A = getList()
L = max(A)

dp = [1] * (L + 1)
dp[0] = 0
num_list = [0] * (L + 1)

for i in A:
    if num_list[i] == 0:
        for j in range(i * 2, L + 1, i):
            dp[j] = 0
    num_list[i] += 1

ans = 0
for i in range(L + 1):
    if num_list[i] == 1 and dp[i] == 1:
        ans += 1
print(ans)

Solution (Python):
n = int(input())
a = sorted(list(map(int,input().split())))
am = a[-1]+1
div = [1]*am
ans = 0

for i in range(n-1):
  a_i = a[i]
  if div[a_i]:
    for j in range(a_i,am,a_i):
      div[j] = 0
    if a_i < a[i+1]:
      ans += 1
if div[-1]:ans += 1
print(ans)

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

for i in sorted(a):
  if 1 <= dp[i]:
    dp[i] += 1
    continue

  for j in range(1, ma//i + 1):
    dp[j * i] += 1

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

Solution (Python):

_, *a = map(int, open(0).read().split())
a.sort()
p = [0] * a[-1]
for i in a:
    for j in range(1, a[-1] // i + 1):
        p[j * i - 1] += j
print(sum(i == 1 for i in p))

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

a.sort()

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

ans = [1] * (a[n-1]+1)

for i in range(n):
    if i >= 1 and a[i] == a[i-1]:
        ans[a[i]] = 0

    else:
        j = 2
        while j*a[i] <= a[n-1]:
            ans[j*a[i]] = 0
            j += 1


sum = 0

for i in range(n):
    sum += ans[a[i]]


print(sum)

Solution (Python):


import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())
    N = next(it)
    A = [next(it) for i in range(N)]

    if N == 1:
        print(1)
        return

    ax = max(A)+1
    dp = [0]*ax
    for ai in A:
        da = dp[ai]
        if da > 1:
            continue
        dp[ai] += 1
        if da == 0:
            for aj in range(2*ai, ax, ai):
                dp[aj] = 2
    ans = 0
    for ai in A:
        if dp[ai] == 1:
            ans += 1
    print(ans)


if __name__ == "__main__":
    resolve()

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

max_per = max(As)
ansList = [0 for _ in range(max_per + 10)]

for A in As:
    checkList = [i for i in range(A, max_per+1, A)]
    

    for check in checkList:
        ansList[check] += 1

ans = 0

for A in As:
    if(ansList[A] == 1):
        ans += 1

print(ans)

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

Solution (Python):
x = int(input())
p = sorted(list(map(int,input().split())))
d = [True]*(p[-1]+1)
e = [False]*(p[-1]+1)
for i in p:
    if e[i]:
        d[i] = False
        continue
    else:
        e[i] = True
    idx = 2*i
    while idx < len(d):
        d[idx] = False
        idx += i

cnt = 0
for i in p:
    cnt += int(d[i])    
print(cnt)

Solution (Python):
counter = [0 for i in range(10**6+1)]
n = int(input())
a = sorted(list(map(int,input().split())))
for i in a:
  counter[i] += 1
l  = [0 for i in range(10**6+1)]
cou = 0
for i in range(n):
  b = a[i]
  if l[b]==0:
    cou += 1
    for j in range(b,10**6+1,b):
      l[j] = 1
    if counter[b]>=2:
      cou -=1
print(cou)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random,resource

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n = I()
    a = sorted(LI())

    m = max(a)
    t = [False] * (m + 1)
    r = 0
    for i in range(n):
        ai = a[i]
        if t[ai]:
            continue
        for j in range(ai, m+1, ai):
            t[j] = True
        if i < n-1 and a[i+1] == ai:
            continue
        r += 1

    return r


print(main())

Solution (Python):
n=int(input(""))
aa=input("").split(" ")
lista=[]
for i in range(n):
    lista+=[int(aa[i])]
lista.sort()
listtf=[]
s=0
for i in range(lista[n-1]):
    listtf+=[True]
for i in range(n):
    
    if(listtf[lista[i]-1]):
        if(i<n-1 and lista[i]==lista[i+1]):
            s-=1
        s+=1
        t=1
        while(t*lista[i]<=lista[n-1]):
            listtf[lista[i]*t-1]=False
            t+=1
print(s)

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

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

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
a.sort()
m = a[-1]
c = [0] * (m + 1)

for ai in a:
    for i in range(ai, m + 1, ai):
        c[i] += 1

ans = 0
for ai in a:
    if c[ai] == 1:
        ans += c[ai]

print(ans)

Solution (Python):
from collections import Counter
n=int(input())
inp = list(map(int,input().split()))
c=Counter(inp)
arr=[1]*(max(inp)+1)
inp.sort()
d=Counter([])
for i in range(len(arr)):
    if c[i]>=1 and arr[i]==1:
        if d[i]==0:
            d[i]+=1
        else:
            continue
        k=2
        while k*i<len(arr):
            arr[k*i]=0
            k+=1
ans=0
for item in d.keys():
    if c[item]==1:
        ans+=1
print (ans)

Solution (Python):
def main():
    n = int(input())
    A = list(map(int,input().split()))
    A.sort()
    A_max = A[-1]
    g = []
    table = [True]*(A_max+1)
    for i,a in enumerate(A):
        if table[a]:
            temp = a
            while A_max >= temp:
                table[temp] = False
                temp+=a
            if i==n-1 or a!=A[i+1]:
                g.append(a)
    print(len(g))
main()

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] > 1:
        D[a] = 1
    for b in range(2 * a, maxA + 1, a):
        D[b] = 1
print(sum([D[a] == 0 for a in A]))

Solution (Python):
import collections


if __name__ == "__main__":
    N = int(input())
    A = [int(x) for x in input().split(" ")]
    counter = collections.Counter(A)

    duplicates = [key for key, val in counter.items() if val >= 2]
    A = [key for key in counter]

    A.sort()
    max_a = A[-1]
    multiples = set()
    ans = []

    for a in A:
        if a not in multiples:
            ans.append(a)
            for i in range(1, 10 ** 9):
                if a * i > max_a:
                    break
                multiples.add(a * i)

    print(len(set(ans) - set(duplicates)))

Solution (Python):
from collections import Counter
n = int(input())
a = list(map(int,input().split()))
a.sort()
ct = Counter(a)
st = set()
ans = 0
x = max(a)
for i in range(n):
    if a[i] in st:
        continue
    if ct[a[i]]>1:
        st.add(a[i])
    for j in range(2,x//a[i]+1):
        st.add(a[i]*j)
for i in range(n):
    if not a[i] in st:
        ans += 1
print(ans)

Solution (Python):
n=int(input())
a=[int(x) for x in input().rstrip().split()]
a.sort()
ma=max(a)
dp=[0]*ma
for i in a:
  dp[i-1]+=1

l=[0]*ma
ans=0
for i in a:
  j=i
  if l[i-1]==0 and dp[i-1]==1:
    ans+=1
  while(j<=ma):
    l[j-1]+=1
    if j+i<=ma:
      j+=i
    else:
      break
print(ans)

Solution (Python):
import numpy as np

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

A = np.array(A)

A.sort()

d = {}

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

sieve = [True] * (A[-1] + 1)

for a in A:
    if sieve[a] == False:
        continue
    if d[a] > 1:
        sieve[a] = False
    for i in range(a + a, A[-1] + 1, a):
        sieve[i] = False

print(sum(1 for a in A if sieve[a]))

Solution (Python):
from numba import njit


@njit(fastmath=True)
def fact(x):
    i = 1
    while i * i <= x:
        if x % i == 0:
            yield i
            yield x // i
        i += 1


def main():
    n = int(input())
    a = tuple(map(int, input().split()))

    c = [0] * (max(a) + 1)

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

    ans = n
    for e in a:
        c[e] -= 1
        for fct in fact(e):
            if c[fct]:
                ans -= 1
                break

        c[e] += 1

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np

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

A = np.array(A)

A.sort()

d = {}

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



sieve = [True] * (A[-1] + 1)

for a in A:
    if d[a] > 1:
        sieve[a] = False
    for i in range(a + a, A[-1] + 1, a):
        sieve[i] = False

print(sum(1 for a in A if sieve[a]))

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
l = max(A)+1
li = [0]*(l)
A.sort()

for a in A:
  if li[a] == 0:
    li[a] = 1
    for i in range(a*2, l, a):
      li[i] = 2
  elif li[a] == 1:
    li[a] = 2
print(li.count(1))

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
l = max(A)+1
li = [0]*(l)
A.sort()

for a in A:
  if li[a] == 0:
    li[a] = 1
    for i in range(a*2, l, a):
      li[i] = 2
  elif li[a] == 1:
    li[a] = 2
print(li.count(1))

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

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

m = 10**6+10
d = [False] * (m+1)
ans = 0
for i in range(n):
    same = (i > 0 and a[i] == a[i-1]) or (i < (n-1) and a[i] == a[i+1])
    x = a[i]
    if not d[x] and not same: ans += 1
    
    if (i > 0 and a[i] == a[i-1]): continue
    for j in range(x, m+1, x):
        d[j] = True
    
print(ans)