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

Solution (Python):

import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys


buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def eratosthenes(n):
    p = []
    t = [True] * n

    for i in range(2, int(math.ceil(math.sqrt(n)))):
        if t[i]:
            p.append(i)
            for j in range(2*i, n, i):
                t[j] = False

    for j in range(i+1, n):
        if t[j]:
            p.append(j)

    return p, t

P, T = eratosthenes(int(math.sqrt(10**6))+1)

def e(n):
    c = []
    for p in P:
        while n % p == 0:
            
            c.append(p)
            n //= p
        if n == 1:
            break
    if n != 1:
        
        c.append(n)
    return c


@mt
def slv(N, A):
    ans = 0
    A.sort()
    ac = Counter(A)
    for i in range(N):
        
        a = A[i]
        if ac[a] >= 2:
            continue
        c = e(a)
        for j in range(len(c)):
            f = False
            for i in combinations(c, r=j):
                m = reduce(mul, i, 1)
                
                if ac[m] >= 1:
                    
                    break
            else:
                f = True
            if not f:
                break
        else:
            ans += 1

    return ans


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))

    
    
    
    


if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    c = Counter(a)
    used = set()
    m = 10**6 + 1
    cnt = [0]*m
    ans = 0
    for ai in a:
        if c[ai]>1:
            if ai not in used:
                used.add(ai)
                for i in range(ai, m, ai):
                    cnt[i] += 1
        else:
            if cnt[ai] == 0:
                ans += 1
                for i in range(ai, m, ai):
                    cnt[i] += 1
    print(ans)

if __name__ == "__main__":
    solve()

Solution (Python):
N = int(input())
l = [int(x) for x in input().split()] + [1000001]
l.sort()
ans = 0
t = 0
M = [False] * 10 ** 6
for i in range(N):
    if not M[l[i]-1]:
        if l[i] != l[i+1]:
            ans += 1
        t = l[i]
        while t <= 10 ** 6:
            M[t-1] = True
            t += l[i]
print(ans)

Solution (Python):

N = int(input())
li = [True for _ in range(0, 10**6 + 1)]
A = list(map(int, input().split()))
A.sort()
used = {}
for i in range(N):
    if A[i] not in used.keys():
        used[A[i]] = 1
    else:
        used[A[i]] += 1
ans = 0
for k in used.keys():
    if used[k] > 1:
        for j in range(k, 10**6 + 1, k):
            li[j] = False
for i in range(N):
    if li[A[i]] and used[A[i]] == 1:
        ans += 1
    else:
        continue
    for j in range(A[i], 10**6 + 1, A[i]):
        li[j] = False
print(ans)

Solution (Python):
def main():

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

    d = dict()
    for v in A:
        d[v] = d.get(v, 0) + 1
    if 1 in d:
        if d[1] == 1: return 1
        else: return 0

    A = list(set(A))
    A.sort()
    s = set()
    ans = 0
    for i in range(len(A)):
        if d[A[i]] == 1:
            if A[i] not in s:
                ans += 1
        k = 1
        while k * A[i] <= A[-1]:
            s.add(k * A[i])
            k += 1

    return ans


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

Solution (Python):
from collections import Counter
 
N = int(input())
A_raw = Counter(list(map(int, input().split())))
A = [x[0] for x in A_raw.items() if x[1] == 1]
A.sort()
B = [x[0] for x in A_raw.items() if x[1] > 1]
B.sort()
seen = [0]*(1000000+1)
for b in B:
    if seen[b] == 0:
        x = b
        j = 1
        while x <= 1000000:
            seen[x] = 1
            j += 1
            x = b*j
ans = 0
for a in A:
    if seen[a] == 0:
        ans += 1
        x = a
        j = 1
        while x <= 1000000:
            seen[x] = 1
            j += 1
            x = a*j
print(ans)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
if n!=1 and len(set(a))==1:
  print(0)
  exit()
l=[0 for i in range(10**6+1)]
for i in range(n):
  l[a[i]]+=1
if n!=1 and min(a)>max(a)/2:
  ct=0
  for i in range(len(l)):
    if l[i]==1:
      ct+=1
  print(ct)
  exit()
d={}
ans=0
for i in range(n):
  x=a[i]
  if x not in d:
    if l[a[i]]==1:
      flag=1
      for j in range(1,int(x**0.5)+2):
        if x%j==0:
          if x!=j and l[j]>0:
            flag=0
            break
          if x!=x//j and x%(x//j)==0 and l[x//j]>0:
            flag=0
            break
      if flag==1:
        ans+=1
        d[x]=1
      else:
        d[x]=0
  else:
    ans+=d[x]
print(ans)

Solution (Python):
bun = input()
lst = input().split()
nlst = []
for i in range(1000000):
    nlst.append(0)
for i in range(len(lst)):
    nlst[int(lst[i])-1] += 1
for i in range(1000000):
    if nlst[i] > 0:
        for j in range((i+i+1),1000000,i+1):
            nlst[j] = 0
count = 0
for i in range(1000000):
    if nlst[i] == 1 :
        count += 1
print(count)

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

        if i == 0:
            for j in range(a[-1] // a[i]):
                box[a[i] * (j + 1)] = 0
            if a[1] != a[0]:
                ans += 1
        elif i == n - 1:
            if box[-1] == 1:
                ans += 1
        else:
            if a[i] != a[i - 1] and a[i] != a[i + 1]:
                if box[a[i]] == 1:
                    ans += 1
                    for j in range(a[-1] // a[i]):
                        box[a[i] * (j + 1)] = 0
            elif a[i] == a[i + 1]:
                for j in range(a[-1] // a[i]):
                    box[a[i] * (j + 1)] = 0
    print(ans)

Solution (Python):



import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf



import math

import bisect
from collections import defaultdict

def solve(data):
    is_unique = defaultdict(lambda: 0)
    times = [False] * (data[-1] + 3)
    for d in data:
        is_unique[d] += 1
        v = d * 2
        
        
        while v < len(times):
            times[v] = True
            v += d
    
    
    
    
    ans = 0
    for d in data:
        if is_unique[d] > 1:
            continue
        if times[d] == False:
            ans += 1
    return ans

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

Solution (Python):

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)


from collections import Counter,deque,defaultdict





n=n0()
A=n1()

A.sort()
m=A[-1]

d=defaultdict(int)
d2=defaultdict(int)

for i in A:
    d2[i]+=1

ans=0
for a in A:
    if d[a]==0:
        if d2[a]<=1:
            ans+=1
        i=a
        while i<=m:
            d[i]=1
            i+=a
print(ans)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
if n == 1:
    print(1)
    exit()
flag = [True for i in range(10**6+1)]
a.sort()
for i in range(n):
    if flag[a[i]] == False:
        continue
    if i >= 1:
        if a[i] == a[i-1]:
            continue
    for j in range(2,(10**6)//a[i]+1):
        flag[a[i]*j] = False
ans = 0
for i in range(n):
    if flag[a[i]]:
        if i >= 1:
            if a[i] == a[i-1]:
                continue
        if i < n-1:
            if a[i] == a[i+1]:
                continue
        ans+=1
print(ans)

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

maxA = max(A)
era = [0]*(maxA+1)

for i in range(0,N,1):
    if era[A[i]]==0:
        era[A[i]]=1
    else:
        era[A[i]]=-1

ans = 0

for i in range(1,maxA+1,1):
    if era[i]==1:
        for j in range(2*i,maxA+1,i):
            era[j]=0
        ans+=1
    elif era[i]==-1:
        for j in range(2*i,maxA+1,i):
            era[j]=0

print(ans)

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

def multi(n):
    i = 2
    while True:
        yield n * i
        i += 1

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

anmax = 10**6

for n in sorted(d):
    if n not in d:
        continue

    for m in multi(n):
        if m > anmax:
            break

        if m in d:
            del d[m]

    
    if d[n] > 1:
        del d[n]


print(len(d))

Solution (Python):

import sys
from collections import deque, Counter


def solve(N: int, A: "List[int]"):
    d_A = Counter(A)
    s = sorted(d_A.keys())
    if s[0] == 1:
        print((d_A[1] == 1)*1)
        return
    
    is_d = [0]*(2*10**6)

    for s_t in s:
        lim = 10**6 // s_t +1
        for i in range(1,lim):
            is_d[i*s_t] +=1
    
    ans = 0
    for s_t in s:
        if (d_A[s_t] == 1) and (is_d[s_t]==1):
            ans+=1
    print(ans)


        

    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    A = [int(next(tokens)) for _ in range(N)]  
    solve(N, A)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
import  math
from heapq import *
import fractions
from collections import defaultdict
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))


N=int(input())
A=nl()
A.sort()
A_MAX=10**6+5
p_l=[0]*(A_MAX)
c=0
if(len(A)==1):
    print(1)
    sys.exit(0)

for i in range(len(A)):
    if(p_l[A[i]]!=0):
        continue
    for k in range(A[i],A_MAX,A[i]):
        if(p_l[k]):
            continue
        p_l[k]=1
    if(i<(len(A)-1) and A[i]==A[i+1]):
        continue
    c+=1
    

print(c)

Solution (Python):
n = int(input())
A = list(map(int, input().split()))
A=sorted(A)
up=max(A)
table=[0]*(up+1)
for i in range(n):
    table[A[i]]+=1
aset=set(A)

for i in range(len(aset)):
    if table[A[i]]>0:
        j=2
        while A[i]*j<up+1:
            if table[A[i]*j]>0:
                table[A[i]*j]=-1
            j+=1

cnt=0
for x in table:
    if x==1:
        cnt+=1
print(cnt)

Solution (Python):
import os, sys, atexit
from io import BytesIO, StringIO
 
input = BytesIO(os.read(0, os.fstat(0).st_size)).readline
_OUTPUT_BUFFER = StringIO()
sys.stdout = _OUTPUT_BUFFER
 
@atexit.register
def write():
    sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
n = int(input())
l = list(map(int, input().split()))
l.sort()
vis = [0] * 1000004
for i in l: vis[i] -= -1
for i in range(n):
    tmp = l[i]
    while tmp <= l[n - 1]:
        if vis[tmp]:
            if tmp == l[i]:
                if vis[tmp] > 1: vis[tmp] = 0
            else:
                vis[tmp] = 0
        tmp += l[i]
ans = 0
for i in vis: ans += i
print(ans)

Solution (Python):
import collections

N = int(input())
A_list = [int(e) for e in input().split()]





A_counter = collections.Counter(A_list)

max_A = max(A_list)

A_list.sort(reverse=False)
OK_set = set(A_list)

ans = list()



for i in range(0,N):
    A = A_list[i]

    if A*2 <= max_A:
        multiple_set = {A*j for j in range(2,1+max_A//A)}
        
        OK_set -= multiple_set

    if A_counter[A] != 1:
        OK_set -= {A}
    
    

print(len(OK_set))

Solution (Python):
visited=[False]*(10**6+1)

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

if N>=2 and A[1]==1:
  print(0)
  exit()
if A[0]==1 or N == 1:
  print(1)
  exit()
  
ans=0
for i in range(N):
  if visited[A[i]]:
    continue
  if i < N-1 and A[i]==A[i+1]:
    index = 1
    while A[i]*index<=10**6:
      visited[A[i]*index]=True
      index+=1
    continue
  ans+=1
  index=1
  while A[i]*index<=10**6:
    visited[A[i]*index]=True
    index+=1
    
print(ans)

Solution (Python):
import math
from collections import defaultdict
n = int(input())
a = list(map(int,input().split()))
a.sort()
num = 10**6+10
input_list = defaultdict(int)
sqrt = math.sqrt(num)

ans = 0
for serial in a:



    if input_list[serial] == 1:
        
        continue
    if input_list[serial] == 2:
        
        ans -= 1
        input_list[serial] = 1
        continue
    input_list[serial] = 2
    for s in range(serial*2, num, serial): 
        input_list[s] =1
    ans +=1

    
print(ans)

Solution (Python):

import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 7)


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


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

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

if A[0] == A[1] == 1:
    print(0)
    exit()
if A[0] == 1:
    print(1)
    exit()


S = set()

for a in A:
    i = 2
    while a * i <= 10 ** 6:
        S.add(a * i)
        i += 1

ans = []
for a in A:
    if not a in S:
       ans.append(a)


D = defaultdict(int)
for a in ans:
    D[a] += 1

L = []
for k, v in D.items():
    if v > 1:
        continue
    L.append(k)


print(len(L))

Solution (Python):
N = int(input())
l = list(map(int, input().split()))
M = max(l)

h = [1]*(M+1)
g = [0]*(M+1)

for v in l:
    if g[v] == 1:
        h[v] = 0
    g[v] = 1
    s = v*2
    while s <= M:
        h[s] = 0
        s += v
cnt = 0
for v in l:
    if h[v] == 1:
        cnt += 1
print(cnt)

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))



def read_a_int(): return int(read())


def read_ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) 
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    


MOD = 10**9 + 7
INF = 2**31  

from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  




'''
エラトステネスの篩の数列版じゃない？
1  2  3  4  5  6  7  8  9  10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30

小さい方から倍数を取ってけば良いかな
'''


N = read_a_int()
A = read_ints()


cnt = Counter(A)
A = []
B = []
for k, v in cnt.items():
    if v == 1:
        A.append(k)
        
    else:
        B.append(k)


A.sort()
AMAX = 10**6 + 10
is_first = [True] * (AMAX + 1)
for a in B:
    if is_first[a]:
        for j in range(a, AMAX + 1, a):
            is_first[j] = False

cnt = 0  
for a in A:
    if is_first[a]:
        cnt += 1
        for j in range(a, AMAX + 1, a):
            
            is_first[j] = False
print(cnt)

Solution (Python):
n = int(input())
A = [int(x) for x in input().split()]
A.sort()
lim = A[-1]
se = [True for i in range(lim + 1)]
ans = 0
for i, a in enumerate(A):
    if se[a]:
        if not((i != n - 1 and A[i + 1] == a) or (i != 0 and A[i - 1] == a)):
            ans += 1
        tmp = a
        while not tmp > lim:
            se[tmp] = False
            tmp += a
print(ans)

Solution (Python):
from collections import defaultdict
import sys
N=int(input())
alist=list(map(int,input().split()))

adic=defaultdict(int)
for a in alist:
  adic[a]+=1

noset=set()
aset=set()
max_a=0
for a,v in adic.items():
  aset.add(a)
  max_a=max(max_a,a)
  if v>=2:
    noset.add(a)
  
if not aset:
  print(0)
  sys.exit(0)
  
tlist=[False]*(max_a+1)
for a in aset:
  tlist[a]=True


for i in range(1,len(tlist)):
  if not tlist[i]:
    continue
  else:
    for j in range(2*i,len(tlist),i):
      tlist[j]=False
      

answer=0
for i in range(len(tlist)):
  if tlist[i] and not i in noset:
    answer+=1
    
print(answer)

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

seen = set()
A_set = set()
A_largest = 0
for a in A:
    if a > A_largest:
        A_largest = a
    if a not in seen:
        A_set.add(a)
        seen.add(a)
    else:
        if a in A_set:
            A_set.remove(a)

for b in range(1, A_largest+1):
    if b in seen:
        n = 2
        c =b*n
        while c <= A_largest:
            if c in A_set:
                A_set.remove(c)
            c += b

print(len(A_set))

Solution (Python):
from collections import Counter

n = int(input())
alist = [int(v) for v in input().split()]
dup_set = {k for k, v in Counter(alist).items() if v >= 2}
alist = sorted(set(alist))
adict = {a: False for a in alist}
a_max = alist[-1]
max_ind = -1

count = 0
if 1 in adict:
    count = 0 if 1 in dup_set else 1
else:
    for a, f in adict.items():
        if f:
            continue
        if a not in dup_set:
            count += 1
        for k in range(a, a_max + 1, a):
            if k in adict:
                adict[k] = True
                if k == a_max:
                    max_ind -= 1
                    if abs(max_ind) <= len(alist):
                        a_max = alist[max_ind]

print(count)

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
dp=[0]*(10**6+1)
A.sort()
A.append(10**9+7)
ans=0
for i in range(N):
  if dp[A[i]]==0:
    if A[i]!=A[i+1]:
      ans+=1
    for j in range(1,int(10**6//A[i])+1):
      dp[A[i]*j]+=1
print(ans)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
a.sort()
e=[1]*(10**6+1)
from collections import Counter
d=Counter(a)
if d[0]==1:exit(print(1))
if d[0]>1:exit(print(0))
ans=0
for i in a:
  if d[i]==1 and e[i]==1:ans+=1
  if e[i]==1:
    for j in range(i,10**6+1,i):e[j]=0
print(ans)

Solution (Python):
from collections import defaultdict

N=int(input())

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

dic=defaultdict(int)
max_dic=0

for i in range(N):
    if A[i] in dic:
        dic[A[i]]+=1
    else:

        dic[A[i]]=1
        max_dic=max(A[i],max_dic)

dic1=dic.copy()

for k in dic1:
    cn=k
    while cn<=max_dic:
        cn+=k
        if cn in dic:
            del dic[cn]

result=0

for m in dic:
    if dic[m]==1:
        result+=1

print(result)

Solution (Python):
from collections import Counter

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

MAX = 10 ** 6
is_divisible = [True] * (MAX + 1)
is_divisible[0] = False
for i in S:
    if not is_divisible[i]:
        continue
    for j in range(i * 2, MAX + 1, i):
        is_divisible[j] = False

for k, v in Counter(A).items():
    if v > 1:
        is_divisible[k] = False

ans = len([a for a in A if is_divisible[a]])
print(ans)

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

    a.sort()
    tf = [0] * (a[-1] + 1)
    for ea in a:
        tf[ea] = 1
    for i1 in range(n - 1):
        if a[i1] == a[i1 + 1]:
            tf[a[i1]] = 0

        for i2 in range(2, a[-1]//a[i1] + 1):
            tf[a[i1] * i2] = 0
    r = sum(tf)
    print(r)


if __name__ == '__main__':
    main()

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


ar = [0] * size

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

for i in range(n):
	ar[br[i]] += 1


i = 1
cnt = 0
while i < size:
	if ar[i] is -1 or ar[i] is 0:
		i += 1
		continue
	
	if ar[i] == 1:
		
		cnt += 1

	j = i
	while j < size:
		ar[j] = -1
		j += i

	i +=1



print(cnt)

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

Solution (Python):
import sys
import collections

sys.setrecursionlimit(10**6)
readline = sys.stdin.readline


MAXNUM = 1000001

def main():
    N = int(input())
    A = list(map(int, readline().split()))
    A.sort()
    Acounter = collections.Counter(A)
    acount1 = Acounter[1]
    if acount1 >= 1:
        if acount1 == 1:
            print(1)
            return
        else:
            print(0)
            return
    numset = set()
    for a in A:
        acount = Acounter[a]
        if a in numset:
            continue
        if acount > 1:
            numset.update(set(range(a, MAXNUM, a)))
        else:
            numset.update(set(range(2*a, MAXNUM, a)))

    cnt = 0
    for a in A:
        cnt += a not in numset

    print(cnt)

if __name__ == "__main__":
    main()

Solution (Python):
import sys

N = int(input())
A = list(map(int, sys.stdin.readline().strip().split()))
A = sorted(A)

maxA = A[-1]
halfA = maxA // 2

ans = [False] * maxA
for i in range(N):
    if i != N - 1 and A[i + 1] == A[i]:
        continue
    if i != 0 and A[i - 1] == A[i]:
        continue
    ans[A[i] - 1] = True

for i in A:
    if i > halfA:
        break
    j = i + i
    while j <= maxA:
        ans[j - 1] = False
        j += i

print(sum(ans))

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
from collections import deque
list=[0 for i in range(10**6+1)]
for i in A:
  list[i]+=1

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

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

max_A = max(A)
table = [False]*(max_A+1)
for i in A:
    if table[i] == False:
        table[i] = True
    else:
        table[i] = -1

mem = []        
for i in A:
    if table[i] == -1:
        table[i] = True
        mem.append(i)

for i in range(1, max_A+1):
    if table[i] == True:
        n = 2
        while i*n < max_A+1:
            table[i*n] = False
            n += 1

for i in mem: 
    if table[i] == True:
        table[i] = False
        
print(table.count(True))

Solution (Python):
import numpy as np

n = int(input())
a = np.array(list(map(int, input().split())))
a.sort()
li = np.zeros(a[-1])

u, counts = np.unique(a,return_counts=True)

for item in a[::-1]:
  li[item-1::item] = 0
  li[item-1] = 1



for i in range(len(u)):
  if counts[i] >=2:
    li[u[i]-1] = 0

print(int(li.sum()))

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
li = [1]*(10**6+5)
a.sort()
ans = 1
 
for i in range(a[0], len(li), a[0]):
  li[i] = [0]
 
flag = False
flag2 = True
for i in range(1, len(a)):
  if a[i-1] == a[i]:
    flag = True
    continue
  else:
    if flag and flag2:
      ans -= 1
    flag = False
  if li[a[i]] == 1:
    flag2 = True
    ans += 1
    for j in range(a[i], len(li), a[i]):
      li[j] = 0
  else:
    flag2 = False
if flag and flag2:
  ans -= 1
print(ans)

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

ct = Counter(As)
L = 10**6+1
flags = [True] * L
ans = 0
for k in sorted(ct.keys()):
    c = ct[k]
    if not flags[k]:
        continue
    flags[2*k::k] = [False] * ((L-k-1) // k)
    if ct[k] == 1:
        ans += 1
print(ans)

Solution (Python):



import sys
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline




n = int(input())
a = list(map(int, input().split()))
a.sort()
max_a = a[-1]
counter_a = Counter(a)

if n == 1:
    print(1)
    sys.exit()
    
if len(set(a)) == 1:
    print(0)
    sys.exit()

lis_prime = [False] * (max_a+1)
for a_ in a:
    lis_prime[a_] = True

primes = []
for i in range(len(lis_prime)):
    if lis_prime[i]:
        if counter_a[i]==1:
            primes.append(i)

        j = 2 * i
        while True:
            if j > max_a:
                break
            lis_prime[j] = False
            j += i

print(len(primes))

Solution (Python):
'''     
        
        
        

import sys
import math


def get_ints(): return map(int, input().strip().split())
def get_list(): return list(get_ints())

def printspx(*args): return print(*args, end="")
def printsp(*args): return print(*args, end=" ")
def printchk(*args): return print(*args, end=" \ ")

MODPRIME = int(1e9+7); BABYMODPR = 998244353;

ONLINE_JUDGE = 1
if not ONLINE_JUDGE:
    sys.stdin = open("input.txt","r")  
    sys.stdout = open("output.txt","w")  
    sys.stderr = open("output.txt","w")  


n = int(input())
li = get_list()
flagli= [True]*n
d = {}
li.sort()
se = set(li)
for i in range(n):
    try:
        d[li[i]].append(i)
    except:
        d[li[i]] = [i]

for i in range(n):
    j = li[i]
    if flagli[i]:
        while j <= li[-1]:
            if j in d:
                for val in d[j]:
                    if val != i:
                        flagli[val] = False
            j += li[i]
for k, v in d.items():
    if len(v) > 1:
        for i in v:
            flagli[i] = False


ans = 0
for i in flagli:
    if i:ans+=1
print(ans)

'''
>>> COMMENT THE STDIN!! CHANGE ONLINE JUDGE !!
THE LOGIC AND APPROACH IS BY ME @luctivud ( UDIT GUPTA )
SOME PARTS OF THE CODE HAS BEEN TAKEN FROM WEBSITES LIKE::
(I Own the code if no link is provided here or I may have missed mentioning it)
DO NOT PLAGIARISE.
TESTCASES:
>>> COMMENT THE STDIN!! CHANGE ONLINE JUDGE !!
'''

Solution (Python):
import numpy as np
import sys
from collections import Counter
input = sys.stdin.buffer.readline
N = int(input())
A = sorted(list(map(int, input().split())))

B = np.ones(10**6 + 1, np.bool)
S = set()
for a in A:
    if B[a]:
        B[a * 2::a] = 0
        S.add(a)



c = Counter(A)

for key, value in zip(c.keys(), c.values()):
    if value >= 2 and key in S:
        S.remove(key)

ans = len(S)
print(ans)

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

Solution (Python):
n = int(input())
A = [int(s) for s in input().split()]
A.sort()
MAX_VAL = A[-1]+1

duplicate = {}
for a in A:
    if a in duplicate:
        if duplicate[a]:
            continue
        else:
            duplicate[a] = True
            continue
    duplicate[a] = False

ng_map = {}
counter = 0
for a in A:
    if a in ng_map:
        continue
    if not(a in duplicate and duplicate[a]):
        counter += 1
    for i in range(a, MAX_VAL, a):
        ng_map[i] = True

print(counter)

Solution (Python):
from collections import Counter
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
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 LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n=II()
    mx=10**6
    aa=LI()
    ac=Counter(aa)
    

    ok=[True]*(mx+1)
    ans=0
    for a,c in sorted(ac.items()):
        if ok[a]:
            if c==1:ans+=1
            for b in range(a*2,mx+1,a):
                ok[b]=False
    print(ans)

main()

Solution (Python):
n = int(input())
A = list(map(int, input().split()))
maxA = max(A)
tbl = set()
dup = set()
vis = set()
for a in A:
   if a in vis:
      dup.add(a)
   else:
      vis.add(a)
   s = a
   while s < maxA:
      s += a
      tbl.add(s)

cnt = 0
for a in A:
   if a in dup:
      continue
   if a not in tbl:
      cnt += 1
print(cnt)

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

maxer = max(a)
for i in range(1, maxer + 1):
    m[i] = 1
    d[i] = 1

for i in a:
    if m[i] != 0 and d[i] != 0:
        d[i] = 0
        k = 2
        while True: 
            t = i * k
            if t <= maxer:
                m[t] = 0
                k += 1
            else:
                break
    elif d[i] == 0:
        m[i] = 0
        
res = 0
for i in a:
    if m[i] == 1:
        res += 1

print(res)

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

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

    
    return divisors

def main():
    A.sort()
    S = set(A)
    m = max(A)
    X = [0]*(m+1)
    for i in range(1, m+1):
        j = i
        if j not in S:
            continue
        while j <= m:
            X[j] += 1
            j += i
    

    D = {}
    for i in range(n):
        if A[i] not in D:
            D[A[i]] = 1
        else:
            D[A[i]] += 1

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

    
    
            

if __name__ == '__main__':
    main()