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()
A_max = A[-1]

checked = [False] * (A_max+1)
ans = 0
for i in range(N):
    if i < N-1:
        if A[i] == A[i+1]:
            for j in range(A[i], A_max+1, A[i]):
                checked[j] = True
    if checked[A[i]]:
        pass
    else:
        ans += 1
        for j in range(A[i], A_max+1, A[i]):
            checked[j] = True

print(ans)

Solution (Python):
from collections import Counter

N=int(input())
A=Counter(list(map(int,input().split())))
nmax=10**6
iscop=[True]*(nmax+1)

for k in A.keys():
    if iscop[k]==False:
        continue

    for j in range(2,nmax//k+1):
        iscop[k*j]=False
ans=0
for k,v in A.items():
    if v<2 and iscop[k]:
        ans+=1

print(ans)

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

top = max(A)
out = [0]*(10**6+1)

for i in range(N):
  acm = A[i]
  while acm<=top:
    out[acm] += 1
    acm += A[i]
    
count = 0
for i in range(N):
  if out[A[i]] == 1:
    count += 1
print(count)

Solution (Python):
import sys, os, math, bisect, itertools, collections, heapq, queue

from decimal import Decimal
from collections import defaultdict, deque



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 = sorted(il())
    mx = max(A)
    st = set()
    cnt = collections.Counter(A)
    ret = 0
    for n in range(N):
        if A[n] not in st and cnt[A[n]] == 1:
            st.add(A[n])
            ret += 1

        a = 1
        while A[n] * a <= mx:
            st.add(A[n] * a)
            a+=1
    print(ret)


if __name__ == '__main__':
    main()

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

num = [0] * (10**6+10)
A.sort()
for a in A:
    if num[a]==1:
        num[a] = -1
    elif num[a] ==0:
        num[a]+=1
        for i in range(2,(A[n-1]//a)+1):
            num[i*a]=-1

print(num.count(1))

Solution (Python):

import sys
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]


INF = float("inf")
MOD = 10**9 + 7


def main():
    N = INT()
    A = LIST()
    A.sort()
    M = A[-1] + 1
    table = [0] * (M)

    for i in A:
        if table[i] == 0:
            table[i] = -1
            for j in range(i + i, M, i):
                table[j] = 1
        elif table[i] == -1:
            
            table[i] = -2
    
    cnt = 0
    for i in range(N):
        if table[A[i]] == -1:
            cnt += 1
    print(cnt)

    return


if __name__ == '__main__':
    main()

Solution (Python):

import sys
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]


INF = float("inf")
MOD = 10**9 + 7


def main():
    N = INT()
    A = LIST()
    A.sort()
    M = A[-1] + 1
    table = [0] * (M)

    for i in A:
        if table[i] == 0:
            table[i] = -1
            for j in range(i + i, M, i):
                table[j] = 1
        elif table[i] == -1:
            
            table[i] = -2
    
    cnt = 0
    for i in range(N):
        if table[A[i]] == -1:
            cnt += 1
    print(cnt)

    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    num = [True] * (max(A) + 1)
    appear = set()
    for a in A:
        if a not in appear:
            appear.add(a)
        else:
            num[a] = False

    for a in A:
        for i in range(a * 2, len(num), a):
            num[i] = False

    res = 0
    for a in A:
        if num[a]:
            res += 1
    print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):


import sys
stdin = sys.stdin

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    n = ni()
    a = na()
    d = [0] * (10**6+1)
    for ai in a:
        if d[ai] < 2:
            for i in range(1, (10**6//ai)+1):
                d[ai*i] += 1
    ans = 0
    for ai in a:
        if d[ai] == 1:
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):




from collections import Counter
n=int(input())
a=list(map(int,input().split()))
a.sort()
min_a=a[0]
max_a=a[n-1]

dic=Counter(a)

check=set()

for i in range(n):
  if a[i] not in check:
    if dic[a[i]]>=2:
      check.add(a[i])
    for j in range(2,int((max_a)/a[i])+1):
      check.add(a[i]*j)
ans=0
for i in range(n):
  if a[i] not in check:
    ans=ans+1

print(ans)

Solution (Python):
import collections

N = int(input())
A = [int(x) for x in input().split()]

c = collections.Counter(A)

A = list(set(A))
A.sort()

total = 10 ** 6 + 1

X = [0] * total

for a in A:
    for aa in range(a + a, total, a):
        X[aa] = 1

ans = 0
for i in range(1, total):
    if X[i] == 0 and c[i] == 1:
        ans += 1

print(ans)

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

N = int(input())
div = [0] * 1000005

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

for num in A:
    if div[num] == 0:
        for i in range(num, 1000005, num):
            div[i] += 1
    else:
        div[num] += 1
ans = 0
for num in A:
    if div[num] == 1:
        ans += 1

print(ans)

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

a_max = a[-1]
ans_list = [0] * a_max

ans = 0

for i in range(n-1):

    p = a[i]

    if ans_list[p-1] == 0:
        for q in range(1, (a_max//p)+1):
            ans_list[p*q-1] = 1
            
        if a[i] != a[i+1]:
            ans += 1

if ans_list[a_max-1] == 0:
    ans += 1

print(ans)

Solution (Python):
def main():
    n = int(input())
    a = list(map(int, input().rstrip().split(' ')))
    M = 10**6 + 5
    cnt = [0 for _ in range(M)]
            
    for ai in a:
        if cnt[ai] != 0:
            cnt[ai] = 2
            continue
        for i in range(ai, M, ai):
            cnt[i] += 1
    ans = 0
    for ai in a:
        if cnt[ai] == 1:
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
A = sorted(list(map(int, input().split())))
THE_NUM = 10**6 + 1

dp = [True] * THE_NUM

prev_num = -1
for i in A:
  
  if prev_num != i:
    for j in range(i * 2, THE_NUM, i):
      dp[j] = False
  else:
    dp[i] = False
  prev_num = i

ans = 0
for i in A:
  
  if dp[i] == True:
    ans += 1

print(ans)

Solution (Python):
import sys
from collections import Counter


def main():
    input = sys.stdin.buffer.readline
    _ = input()
    a_list = list(map(int, input().split()))
    res_set = set(a_list)
    
    a_counter = Counter(a_list)
    for e in a_counter.items():  
        if e[1] == 1:
            for i in range(e[0] * 2, 10**6 + 1, e[0]):  
                res_set.discard(i)
        else:
            for i in range(e[0], 2 * 10**6 + 1, e[0]):  
                res_set.discard(i)
    print(len(res_set))


if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter
n=int(input())
a=sorted(list(map(int,input().split())))
a_max=a[-1]
count=0
b=Counter(a)
count_list=[0]*(a_max)
for i in a:
  if b[i]==1:
    if count_list[i-1]==0:
      count+=1
      j=1
      while i*j<=a_max:
        count_list[i*j-1]+=1
        j+=1
  else:
    j=2
    while i*j<=a_max:
      count_list[i*j-1]+=1
      j+=1
print(count)

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

is_prime = [False] * (A_max+1)


for i in A_list:
    is_prime[i] = True

x = -1
for i in A_list:
    if not is_prime[i]:
        continue
    elif x == i:
        is_prime[i] = False
        continue
    for j in range(i*2, A_max+1, i):
        is_prime[j] = False
    x = i

count = 0
for i in A_list:
    if is_prime[i]:
        count += 1


print(count)

Solution (Python):
N = int(input())
A_list = list(map(int, input().split()))
A_list.sort()
A_max = A_list[-1]
count = 0
cnt_list = [1] * ((10 ** 6) + 1)
for i in range(len(A_list)-1):
    if cnt_list[A_list[i]] == 1:
        for j in range((A_max // A_list[i]) + 1):
            cnt_list[A_list[i] * j] = 0
        if A_list[i] != A_list[i+1]:
            count += 1
if cnt_list[A_list[-1]] == 1:
    count += 1
print(count)

Solution (Python):

n = int(input())
a = list(map(int, input().split()))
a.sort()
max_a = max(a)
ans = [1 for _ in range(max_a + 1)]
b = -1







for j in a:
    if b == j:  
        ans[j] = 0
    divided = j + j
    while divided < max_a + 1:
        ans[divided] = 0
        divided += j
    b = j

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

Solution (Python):

import math

n = int(input())
given_lst = sorted(list(map(int,input().split())))
max_num = max(given_lst)
lst_status = [1 for _ in range(max_num+1)]


prev_e = -99999
for e in given_lst:
    if prev_e == e:
        lst_status[e] = 0
    divided_num = e + e
    while(divided_num <= max_num):
        lst_status[divided_num] = 0
        divided_num += e

    prev_e = e

ans = 0
for e in given_lst:
    if lst_status[e] == 1:
        ans += 1

print(ans)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
a.sort()
flag = False
b = [False] * 1000010
for i in range(n - 1):
    if a[i] == a[i + 1]:
        if b[a[i]]:
            continue
        for j in range(a[i], 1000010, a[i]):
            b[j] = True

ans = 0
for i in range(n):
    if not b[a[i]]:
        ans += 1
        for j in range(a[i], 1000010, a[i]):
            b[j] = True

print(ans)

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

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:
    if d[a] > 1:
        t[a] = False
    for i in range(a + a, 10 ** 6 + 1, a):
        t[i] = False
print(sum(1 for a in A if t[a]))

Solution (Python):

from collections import Counter
n = int(input())
a = [int(i) for i in input().split()] 

c = Counter(a)
a.sort()
max_a = a[-1]
flag = [True for _ in range(max_a+1)]
ans = []
for i in a:
    if c[i] >= 2:
        flag[i] = False
    
    for j in range(i + i, max_a + 1, i):
        flag[j] = False
for i in a:
    if flag[i]:
        ans.append(i)

print(len(ans))

Solution (Python):
N = int(input())
nums = list(map(int, input().split()))
nums.sort()
div_length = max(nums)+1
divisible_list = {}

for i in range(0, div_length):
  divisible_list[i] = 0


for fNum in nums:
  for j in range(fNum, div_length, fNum):
   	divisible_list[j] += 1


answer = 0
for num in nums:
  if (divisible_list[num] == 1):
    answer += 1
print(answer)

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

C = {a:0 for a in A}

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

maxA = max(A)

D = {a:0 for a in A}

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

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

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 math
import collections
import fractions
import itertools

def solve():
    n = int(input())
    arr = list(map(int, input().split()))
    arr.sort()
    s = set()
    cnt = collections.Counter(arr)
    for i in range(n):
        if arr[i] in s:
            continue
        elif cnt[arr[i]] >= 2:
            s.add(arr[i])
        for j in range(2, 10**6//arr[i]+1):
            s.add(arr[i]*j)
    ans = 0
    for i in arr:
        if i in s:
            continue
        ans += 1
    print(ans)
    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
a.sort()
MAX = int(1e6) + 10
sieve = [0] * int(MAX)
for i in a:
    sieve[i] += 1
ans = 0
for idx, val in enumerate(sieve):
    if val == 0:
        continue
    elif val > 1:
        sieve[idx] = 0
    else:
        ans += 1
    for i in range(idx * 2, MAX, idx):
        sieve[i] = 0
print(ans)

Solution (Python):
from collections import Counter


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

sifter = {i: True for i in range(1, A[N - 1] + 1)}
counter = Counter(A)
ans = 0
for A_i in A:
  if sifter[A_i]:
    if counter[A_i] == 1:
      ans += 1
    for i in range(A_i, A[N - 1] + 1, A_i):
      sifter[i] = False
      
print(ans)

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

An.sort()
max_num = An[-1]

primes = [True] * max_num
once = [False] * max_num

i = 0
while i < n:
    once[An[i] - 1] = True

    j = 1
    while i + j < n:
        if An[i] == An[i + j]:
            once[An[i] - 1] = False
            j += 1
        else:
            break

    i += j

for i in range(n):
    if primes[An[i] - 1]:
        base = An[i]
        idx = An[i] * 2 - 1
        while idx < max_num:
            primes[idx] = False
            idx += base

ans = [x and y for (x, y) in zip(once, primes)]
print(ans.count(True))

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
S = set(A)
M = max(S)
A.sort()

pre_a = 0
for a in A:
    if a == pre_a:
        S.discard(a)
    if a in S:
        j = a * 2
        while j <= M:
            S.discard(j)
            j += a
    pre_a = a
print(len(S))

Solution (Python):
sieve=[0]*1000009
n=int(input())
s=sorted(map(int,input().split()))
for i in s:
    if sieve[i]<2:
        for j in range(i,1000009,i):sieve[j]+=1
print(sum(sieve[i]==1for i in s))

Solution (Python):
from collections import Counter
n=int(input())
a=list(map(int,input().split()))
ma=max(a)
a.sort()
era=[1]*(ma+1)

cn=Counter(a)

count=0
for i in range(n):
  if era[a[i]]==0:continue
  else:
    era[a[i]]=0
    if cn[a[i]]==1:
      count+=1
    for j in range(2*a[i],ma+1,a[i]):
      era[j]=0
print(count)

Solution (Python):

from collections import Counter

N = int(input().strip())
A_list = list(map(int, input().rstrip().split()))


cnt_A = Counter(A_list)
A_list.sort()

max_num = A_list[-1]
cnt = 0


for i in range(len(A_list)):
    if A_list[i] not in cnt_A:
        continue
    
    if cnt_A[ A_list[i] ] == 1:
        cnt += 1
    
    for j in range( 2, max_num // A_list[i] + 1 ):
        n = A_list[i] * j
        
        if n in cnt_A:
            del cnt_A[n]


print(cnt)

Solution (Python):
import sys
N = int(input())
if N == 1:
    print(1)
    sys.exit()
A = [int(i) for i in input().split()]
ls = [0 for i in range(10**6+1)]
s = set()
for a in A:
    if ls[a] == 0:
        cur = 1
        while a*cur <= 10**6:
            ls[a*cur] += 1
            cur += 1
        s.add(a)
    else:
        ls[a] += 1
ans = 0
for a in A:
    if ls[a] == 1:
        ans += 1
print(ans)

Solution (Python):

from collections import Counter

N = int(input().strip())
A_list = list(map(int, input().rstrip().split()))


cnt_A = Counter(A_list)
max_num = max(A_list)


for i in range(len(A_list)):
    if A_list[i] not in cnt_A:
        continue
    
    for j in range( 2, max_num // A_list[i] + 1 ):
        n = A_list[i] * j
        
        if n in cnt_A:
            del cnt_A[n]


ans = [ k for k,v in cnt_A.items() if v == 1 ]
print( len(ans) if ans else 0 )

Solution (Python):
from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations

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

    multiples = [1] * (10 ** 6 + 1)

    bucket = Counter(A)
    res = 0

    for num in A:
        if bucket[num] == 1 and multiples[num] == 1:
            res += 1
        if multiples[num] == 1:
            for i in range(num, 10**6+1, num):
                multiples[i] = 0
    
    print(res)

if __name__ == '__main__':
    main()

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

intList = list(map(int, input().split()))
intList.sort()

cntList = [1] * (intList[-1] + 1)

i = 0
j = 1
ans = 0

while i < (N - 1):
  base = intList[i]
  j = 1
  num = base
  if cntList[num] == 1:
    while num <= intList[-1]:
      if cntList[num] == 1:
        cntList[num] = 0
      j += 1
      num = base * j
    if intList[i] != intList[i+1]:
      ans += 1
  i += 1

if cntList[intList[-1]] == 1:
  ans += 1
  
print(ans)

Solution (Python):
def main():
  n=int(input())
  a=sorted(map(int,input().split()))
  maxa=a[-1]+1
  tf=[False]*maxa
  r=0
  n-=1
  for i in range(n):
    a_i=a[i]
    if tf[a_i] ==False:
      for j in range(a_i,maxa,a_i):
        tf[j]=True
      if a_i  <a[i+1]:
        
        r+=1
  if tf[-1] ==False:
    r+=1
  print(r)
main()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 9)

def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')




import numpy as np


def solve():
    N = II()
    A = LI()
    mx = max(A)+1
    B = np.zeros(mx)

    for a in A:
        for b in range(a, mx, a):
            B[b] = B[b] + 1
    

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

if __name__ == '__main__':
    solve()

Solution (Python):
import os
import sys
from collections import defaultdict, Counter
from itertools import product, permutations,combinations, accumulate
from operator import itemgetter
from bisect import bisect_left,bisect
from heapq import heappop,heappush,heapify
from math import ceil, floor, sqrt
from copy import deepcopy

def main():
    n = int(input())
    p_list = list(map(int, input().split()))
    x = sorted(list(set(p_list)))
    max_num = 10**6

    dp = [0] * (max_num + 1)
    for j in p_list:
        dp[j] += 1

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

    print(dp.count(1))
   
   
if __name__ == "__main__":
    main()

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

def main():
    N = int(input())
    A = sorted(list(map(int, input().split())))
    ng = [False] * (A[-1] + 1)
    check = [False] * (A[-1] + 1)
    for a in A:
        if check[a]:
            ng[a] = True
        check[a] = True

    if len(A) == 0:
        print(0)
        return
    MAX_PRIME = A[-1] + 1
    primes = []
    is_prime = [True] * (MAX_PRIME+1)
    for i in A:
        if is_prime[i]:
            primes.append(i)
            for j in range(2*i, MAX_PRIME+1, i):
                is_prime[j] = False
    
    ans = 0
    for a in A:
        if is_prime[a] and not ng[a]:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
n=int(input())
if n==1:
    print(1)
else:
    oklist=[True for i in range(1000001)]
    l=[int(i) for i in input().split()]
    l.sort()
    res=0
    for i in range(n):
        if oklist[l[i]]:
            if i==n-1 or (i<n-1 and l[i]!=l[i+1]):
                res+=1
            for j in range(1,1000001):
                if l[i]*j<=1000000:
                    oklist[l[i]*j]=False
                else:
                  break
    print(res)

Solution (Python):
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
from decimal import Decimal
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def dijkstra_heap(s, edge, n):
    
    d = [10**20] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


def lcm(x, y):
    return (x * y) // gcd(x, y)


def lcm_list(numbers):
    return reduce(lcm, numbers, 1)


def gcd_list(numbers):
    return reduce(gcd, numbers)


def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True



def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P


def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]


n = int(input())
a = sorted(list(map(int, input().split())))
m = max(a)
dp = [0 for i in range(m + 1)]
for i in a:
    cnt = 1
    while i * cnt <= m:
        dp[i * cnt] += 1
        cnt += 1
ans = 0

for i in range(n):
    if i > 0 and a[i] == a[i - 1]:
        continue
    if dp[a[i]] <= 1:
        ans += 1
print(ans)

Solution (Python):
def main():
    max_num = 10**6
    N = int(input())
    A = list(map(int, input().split()))
    M = {}
    for a in A:
        if a not in M:
            M[a] = 0
        M[a] += 1
    B = sorted(set(A))
    S = [0]*(max_num + 1)
    ans = 0

    for b in B:
        if S[b] != 0:
            continue
        if M[b] == 1:
            ans += 1
        v = b
        while v <= max_num:
            S[v] = 1
            v += b
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter

def main():
    n = int(input())
    a = sorted([int(i) for i in input().split()])
    table = [True for i in range(max(a))]
    res = 0
    amax = max(a)

    for i in a:
        if table[i-1] is False:
            continue
        for j in range(i*2, amax+1, i):
            table[j-1] = False

    c = Counter(a)
    for i in set(a):
        if table[i-1]:
            if c[i] == 1:
                res += 1
    print(res)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter

def main():
    n = int(input())
    a = sorted([int(i) for i in input().split()])
    table = [True for i in range(max(a))]
    res = 0
    amax = max(a)

    for i in a:
        if (amax/2) + 1 < i:
            break
        if table[i-1] is False:
            continue
        for j in range(i*2, amax+1, i):
            table[j-1] = False

    c = Counter(a)
    for i in set(a):
        if table[i-1]:
            if c[i] == 1:
                res += 1
    print(res)

if __name__ == '__main__':
    main()

Solution (Python):
import collections

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

c=[0 for _ in range(M+1)]

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

answer = 0

for i in a:
    if c[i] == 1:
        answer+=1


print(answer)

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

amax = a[-1]
dp = [True] * (amax+1)
ans = 0
for x in range(len(a)-1):
   i = a[x]
   if dp[i] == True:
      for j in range(amax//i+1):
         dp[i*j] = False
      if a[x] != a[x+1]:
         ans += 1
if dp[amax] == 1:
   ans += 1
print(ans)

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

cnt = [0] * 1000001

for i in A:
  if cnt[i] == 1:
    continue 
  if cnt[i] == 2:
    cnt[i] = 1
    continue
  cnt[i] = 2
  for j in range( (i+i),1000001,i):
    cnt[j] = 1

ans = 0
for i in range(1000001):
  if cnt[i] == 2:
    ans += 1

print(ans)

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

max_a = max(a)
l = [0] * max_a

for i in range(n):
  j = 1
  while a[i] * j - 1 < max_a:
    l[a[i] * j - 1] += 1
    j += 1

count = 0

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

print(count)

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

if __name__ == "__main__":
    main()

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

A.sort()

l = [0] * (A[N - 1] + 1)

for i in A:
        j = i 
        while j <= A[N - 1]: 
                l[j] += 1
                j += i 

cnt = 0 
for k in A:
        if l[k] == 1:
                cnt += 1

print(cnt)

Solution (Python):
def main():
  n=int(input())
  a=sorted(map(int,input().split()))
  maxa=a[-1]+1
  tf=[False]*maxa
  r=0
  n-=1
  for i in range(n):
    a_i=a[i]
    if tf[a_i] ==False:
      for j in range(a_i,maxa,a_i):
        tf[j]=True
      if a_i < a[i+1]:
        
        r+=1
  if tf[-1] ==False:
    r+=1
  print(r)
main()

Solution (Python):

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

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

l = [0]*(a[-1] + 1)

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

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

print(ans)

Solution (Python):
import collections

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

dp = collections.defaultdict(lambda: True)

for i in range(N):
    if i < N - 1 and A[i] == A[i + 1]:
        dp[A[i]] = False
    k = 2
    while True:
        if A[i] * k > A[-1]:
            break
        else:
            dp[A[i] * k] = False
            k += 1

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

Solution (Python):
import numpy as np

def main():
  N = int(input())
  A = list(map(int,input().split()))
  A.sort()
  d = np.zeros(A[-1]+1, dtype=np.uint64)
  
  for i in range(N):
    a = A[i]
    a1 = A[i-1]
    if a != a1:
      d[a::a] += 1
    else:
      d[a] += 1
  print(np.count_nonzero(d[A] == 1))
  
main()

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

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

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

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

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

for i in range(1, len(dp)):
    if dp[i]:
        for j in range(i+i, len(dp), i):
            dp[j] = 0
print(dp.count(1))