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 sys

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

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

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

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

print(count)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
a = sorted(a)
s = set()
s1 = set()
same_s = set()
ans = 0
for i in a:
    if i in s1:
        same_s.add(i)
    if i not in s:
        s1.add(i)
        ans +=1
        for j in range(10**6 // i + 1):
            s.add(j*i)
print(ans - len(same_s))

Solution (Python):
def LI(): return list(map(int, input().split()))
def I(): return map(int, input().split())
  
def main():
  m = int(input())
  a = LI()
  ans = 0
  if a.count(1) == 1:
    print(1)
    exit()
  n = max(a)
  num = [True]*(n+1)
  num[0] = num[1] = False
  a.sort()
  for i in range(m):
    if (i != m-1 and a[i]==a[i+1]) or (i != 0 and a[i]== a[i-1]): num[a[i]] = False
    for j in range(a[i]*2, n+1, a[i]):
      num[j] = False
  for aa in a:
    if num[aa]:
      ans += 1
  print(ans)

if __name__ == '__main__':
  main()

Solution (Python):
import collections

def main():
    N  = int(input()) 
    A=list(map(int, input().split()))
    C = collections.Counter(A)
    B = list(set(A))
    B.sort()
    lenb = len(B)
    Boo = [True]*lenb
    ZENBU = [False]*(10**6+4)

    if C[1]>1:
        print(0)
        return
    if C[1]==1:
        print(1)
        return

    for i in range(lenb):
        temp = 2
        if ZENBU[B[i]]==False:
            while B[i]*temp < 1000002:
                ZENBU[B[i]*temp] = True
                temp+=1

    cnt = 0
    for i in range(lenb):
        if ZENBU[B[i]]==False and C[B[i]]==1:
            cnt += 1

    print(cnt)


if __name__ == '__main__':
    main()

Solution (Python):
def div(arr, n):
    s = dict()


    max_ele = -10 ** 9
    for i in range(n):
        s[arr[i]] = 1

        max_ele = max(max_ele, arr[i])

    res = dict()
    for i in range(n):

        if (arr[i] != 0):

            for j in range(arr[i] * 2,max_ele + 1, arr[i]):

                if (j in s.keys()):
                    res[j] = 1
    return res


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

b=[]
t=0
c=div(a,n)
for i in range(len(a)):
        if a[i] not in c:
            b.append(a[i])
d={}
for i in b:
        if i in d:
            d[i]+=1
        else:
            d[i]=1
for key,val in d.items():
        if val==1:
            t+=1
print(t)

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

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

n = int(readline())
a = list(map(int,readline().split()))
a.sort()
if a[0] == a[-1]:
  if n > 1:
    print(0)
  else:
    print(1)
  exit()

if a[0] == 1:
  if a[0] == a[1]:
    print(0)
  else:
    print(1)
  exit()
  
def divisorize(fct):
    b, e = fct.pop()
    pre_div = divisorize(fct) if fct else [[]]
    suf_div = [[(b, k)] for k in range(e + 1)]
    return [pre + suf for pre in pre_div for suf in suf_div]

def factorize(n):
    fct = []
    b, e = 2, 0
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct
 
 
def num(fct):
    a = 1
    for base, exponent in fct:
        a = a * base**exponent
    return a
    
s = set()
if a[0] < a[1]:
  ans = 1
else:
  ans = 0
s.add(a[0])
for nm,i in enumerate(a[1:]):
  c = set()
  fct = factorize(i)
  for div in divisorize(fct):
      c.add(num(div))
  if c&s == set() and ((nm < n-2 and a[nm+2] != i) or nm == n-2):
    ans += 1
  s.add(i)

print(ans)

Solution (Python):
def solve(A,N):
    A.sort()
    if N == 1:
        return 1
    elif N == 2:
        if A[1] == A[0]:
            return 0
        elif A[1] % A[0] == 0:
            return 1
        else:
            return 2
    elif A[0] == 1:
        if A[1] >= 2:
            return 1
        else:
            return 0
    else:
        Col = set()
        if A[0] == A[1]:
            Col.add(A[0])
        for i in range(1,N-1):
            if A[i-1] == A[i] or A[i] == A[i+1]:
                Col.add(A[i])
        if A[N-1] == A[N-2]:
            Col.add(A[N-1])

        Mul = set()
        cand = set()
        for i in range(N):
            if A[i] not in Mul:
                if A[i] not in Col:
                    cand.add(A[i])
                for d in range(1,(A[N-1]//A[i])+1):
                    Mul.add(A[i] * d)

        return len(cand)

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

    print(solve(A,N))

if __name__ == "__main__":
    main()

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

F=[0]*(M+1)

for i in range(N):
    a=A[i]
    b=a
    while b<=M:
        F[b]+=1
        b+=a
    

T=0
for i in range(N):
    if F[A[i]]==1:
        T+=1

print(T)

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

A.sort()
A.append(-1)

x = A[0]
if x != 1:
    flag = True
    for a in A:
        if a % x != 0:
            flag = False
    if flag:
        print(0)
        exit()

used = [False] * A[-2]
ans = 0
for idx, a in enumerate(A[:-1]):
    if used[a - 1]:
        continue
    if a != A[idx + 1]:
        ans += 1
    for j in range(a, len(used) + 1, a):
        used[j - 1] = True
print(ans)

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

cand = set(a)

exist = set()
dup = set()
for item in a:
    if item in exist:
        dup.add(item)
    else:
        exist.add(item)

dame_set = set()

a.sort()
ret = 0

for val in a:
    if val in dup:
        if val in dame_set:
            continue
        else:
            i = 1
            cnt = 10 ** 6 // val
            while i <= cnt:
                tmp = i * val
                if tmp in cand:
                    dame_set.add(tmp)
                i += 1
    else:
        if val in dame_set:
            continue
        else:
            ret += 1
            i = 1
            cnt = 10 ** 6 // val
            while i <= cnt:
                tmp = i * val
                if tmp in cand:
                    dame_set.add(tmp)
                i += 1

print(ret)

Solution (Python):
def solve(A,N):
    A.sort()
    if N == 1:
        return 1
    elif N == 2:
        if A[1] == A[0]:
            return 0
        elif A[1] % A[0] == 0:
            return 1
        else:
            return 2
    elif A[0] == 1:
        if A[1] >= 2:
            return 1
        else:
            return 0
    else:
        Col = set()
        if A[0] == A[1]:
            Col.add(A[0])
        for i in range(1,N-1):
            if A[i-1] == A[i] or A[i] == A[i+1]:
                Col.add(A[i])
        if A[N-1] == A[N-2]:
            Col.add(A[N-1])

        Mul = set()
        cand = set()
        for i in range(N):
            if A[i] not in Mul:
                if A[i] not in Col:
                    cand.add(A[i])
                for d in range(1,(A[N-1]//A[i])+1):
                    Mul.add(A[i] * d)

        return len(cand)

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

    print(solve(A,N))

if __name__ == "__main__":
    main()

Solution (Python):
import collections
N = int(input())
A = list(map(int,input().split()))
A.sort()
A2 = set(A)
c = collections.Counter(A)

a = [0]*((10**6)+1)
ans = 0
for i in A2:
    k = 1
    while k <= A[-1]//i:
        a[i*k] += 1
        k += 1
for i in range(1,A[-1]+1):
    if c[i] == 1:
        if a[i] == 1:
            ans += 1
print(ans)

Solution (Python):
import sys
import collections
n=int(input())
a=list(map(int,input().split()))
if 1 in a:
  if a.count(1)==1:
    print(1)
    sys.exit()
  else:
    print(0)
    sys.exit()
C=list(collections.Counter(a).items())
t=[] 
for i in range(len(C)):
  if C[i][1]>1:
    t.append(C[i][0])
t=set(t) 
b=list(set(a))
m=len(b)
b.sort()
Lst=[]
for i in range(m):
  l=2
  num=b[i]*l
  while num<10**6+1:
    Lst.append(num)
    l+=1
    num=b[i]*l
c=set(Lst)
d=set(b)
e=c&d
print(m-len(e)-len(t)+len(e&t))

Solution (Python):
from collections import Counter
from itertools import product

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

    def getMinPFs(n):
        isPrimes = [False]*2 + [True]*(n-1)
        minPFs = [1] + list(range(1, n+1))
        for d in range(2, int(n**0.5)+1):
            if isPrimes[d]:
                minPFs[d] = d
                for x in range(d*d, n+1, d):
                    isPrimes[x] = False
                    if minPFs[x] == x:
                        minPFs[x] = d
        return minPFs

    def getPrimeFactors(x, minPFs):
        anss = []
        while minPFs[x] > 1:
            anss.append(minPFs[x])
            x //= minPFs[x]
        return anss

    maxA = max(As)
    minPFs = getMinPFs(maxA)
    As.sort()

    cntA = Counter(As)

    ans = 0
    setA = set()
    for A in As:
        if cntA[A] == 1:
            PFs = getPrimeFactors(A, minPFs)
            cnt = Counter(PFs)
            ps = list(cnt.keys())
            es = [range(cnt[p]+1) for p in ps]
            L = len(ps)
            for nums in product(*es):
                d = 1
                for i in range(L):
                    d *= ps[i]**nums[i]
                if d in setA:
                    break
            else:
                ans += 1

        setA.add(A)

    print(ans)


solve()

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

ans = 0

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

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


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

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

prime_q = []
for i in range(10**6+2):
    prime_q.append(True)
d = {}
for i in a:
    try:d[i] += 1
    except:d[i] = 1
ans = []
for i in set(a):
    if(prime_q[i] == True):
        ans.append(i)
        c = 1
        while(True):
            try:prime_q[i*c] = False
            except:break
            c+=1

num = 0
for i in ans:
    if(d[i] == 1):num+=1
print(num)

Solution (Python):

import sys
import math
sys.setrecursionlimit(10**8)
from bisect import bisect_left


def divisors(n):
    ret = set()
    for i in range(1, int(n ** 0.5) + 1):
        d, m = divmod(n, i)
        if m == 0:
            ret.add(i)
            ret.add(d)
    return ret


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

    
    
    
    

    
    ans = 0
    history = [False]*N
    for i in range(N):
        if history[i]:
            continue
        
        k = i
        for j in range(2, A[-1]//A[i] + 1):
            k = bisect_left(A, A[i]*j, lo=k)
            
            if A[k] % A[i] == 0:
                history[k] = True
        
        k = bisect_left(A, A[i])
        if k < i:
            history[i] = True
        if i+1 < N and A[i] == A[i+1]:
            history[i] = True
    print(N-sum(history))

    return


if __name__ == '__main__':
    main()

Solution (Python):

import sys


def solve(N: int, A: "List[int]"):
    if N == 1:
        print(1)
        return
    A.sort()
    if A[0] == 1 and not A[1] == 1:
        print(1)
        return
    arr = [0] * (A[-1] + 1) 
    for a in A:
        arr[a] += 1

    count = 0
    for i in range(0, len(arr)):
        if arr[i] == 0:
            continue
        elif arr[i] == 1:
            count += 1
        j = 2
        while i * j <= A[-1]:
            arr[i * j] = 0
            j += 1
    print(count)


    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):
from math import sqrt
from time import perf_counter
t0=perf_counter()
N=int(input())
A=list(map(int,input().split()))
A.sort()
def main():
    a=0
    s=set()
    t=0
    if A[0]!=1:
        for i in A:
            if i in s:
                if t==i:
                    a-=1
                    t=0
                continue
            for j in range(2,int(sqrt(i)+1.1)):
                if i%j:
                    continue
                if j in s:
                    break
                if i//j in s:
                    break
            else:
                t=i
                a+=1
            s.add(i)
            if perf_counter()-t0>1.9:
                a=N
                break                
    else:
        if N>1 and A[1]==1:
            a=0
        else:
            a=1
    print(a)
main()

Solution (Python):
from math import ceil

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

m = 10 ** 6
n_map = {}
v_a = []
for i in a:
    if i not in n_map:
        n_map[i] = 1
    else:
        n_map[i] += 1
v_a = [(k,v) for k, v in n_map.items()]

v_a.sort(key=lambda x: x[0])
res = 0
nn_map = {}
for i, v in v_a:
    if i in nn_map:
        continue
    for j in range(1, ceil(m / i) + 1):
        nn_map[i * j] = True
    if v == 1:
        res += 1
print(res)

Solution (Python):


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

    As.sort()

    setA = set(As)
    setDel = set()

    cands = []

    for a in As:
        if a in setDel:
            continue

        i = 1
        while a*i <= As[-1]:
            if a*i in setA:
                setDel.add(a*i)
            i += 1

        cands.append(a)

    
    dic = {}
    for a in As:
        if not a in dic:
            dic[a] = 0
        dic[a] += 1

    ans = 0
    for x in cands:
        if dic[x] > 1:
            continue
        ans += 1

    print(ans)


if __name__ == "__main__":
    solve()

Solution (Python):
n = int(input())
al = [int(i) for i in input().split()]  
al.sort()
ma = al[-1]
from collections import Counter
c = Counter(al)

if n == 1:
  print(1)
else:
  sn = set()
  total = 0
  l = len(al)
  for num in al:
    if num in sn:
      continue
    if c[num] == 1:
      total += 1
    tmp = num
    while tmp <= ma:
      sn.add(tmp)
      tmp += num
  print(total)

Solution (Python):



import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N = i2n()
    A = sorted(int(c) for c in i2s().split(' '))
    max_ = A[-1]
    B = {}
    if N == 1:
        print(1)
        return
    for i in range(0, N):
        if i == 0:
            if A[i + 1] == A[i]:
                B[A[i]] = 2
                continue
        elif i == N - 1:
            if A[i - 1] == A[i]:
                B[A[i]] = 2
                continue
        elif A[i - 1] == A[i] or A[i + 1] == A[i]:
            B[A[i]] = 2
            continue
        B[A[i]] = 1
    
    for b in B:
        if B[b] == 0:
            continue
        if B[b] == 2:
            B[b] = 0
        for i in range(2, max_ // b + 1):
            if b * i in B:
                B[b * i] = 0
                
    res = 0
    for v in B.values():
        if v:
            res += 1
    
    print(res)
    return

main()

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

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

A.sort()

lis=[0 for i in range(10**6)]

for i in A:
    if lis[i-1]==0:
        lis[i-1]=1
        j=2
        while i*j<=10**6:
            lis[i*j-1]=-1
            j+=1
    elif lis[i-1]==1:
        lis[i-1]=-2

cnt=0
for i in A:
    if lis[i-1]==1:
        cnt+=1

print(cnt)

Solution (Python):


from collections import Counter
N=int(input())
A=list(map(int,input().split()))
A.sort()
maxi=A[-1]
real=set()
forbid=set()

d=dict(Counter(A))


cnt=0
for i in range(N):
    if A[i] not in forbid:
        if d[A[i]]==1:
            cnt +=1
        p=maxi//A[i]
        for j in range(1,p+1):
            forbid.add(j*A[i])
        
        

print(cnt)

Solution (Python):
from collections import Counter


LEN = 10 ** 6
is_avl = [0] * (LEN + 1)
N = int(input())
A = Counter(map(int, input().split()))
for a in A:
    is_avl[a] = 1
for a in A:
    for i in range(2 * a, LEN + 1, a):
        is_avl[i] = 0
ans = 0
for a in A:
    if is_avl[a] == 1 and A[a] == 1:
        ans += 1
print(ans)

Solution (Python):
def e(x,y):
    z=1
    if x<y:
        z=x
        x=y
        y=z

    while x!=0 and y!=0 and z!=0 and x!=y:
        z=x%y
        x=y
        y=z
    return x

n=int(input(''))
a=input('')
a=a.split(' ')
for b in range(n):
    a[b]=int(a[b])

p=[]
for b in range(10**6+1):
    p.append(0)

for b in range(n):
    p[a[b]]+=1

for b in range(10**6+1):
    if p[b]>=1:
        c=b+b
        while c<=10**6:
            p[c]=0
            c=c+b

s=0
for b in range(10**6+1):
    if p[b]==1:
        s=s+1

print(s)

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

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

mx = max(a)

mark = [0 for _ in range(mx+1)]

for i in range(n):
	for x in range(a[i], mx+1, a[i]):
		mark[x] += 1

ans = 0

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

print(ans)

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

d = defaultdict(int)
for i in a:
  d[i] += 1

a.sort()
mx = max(a)

chk = [False for i in range(mx+1)]
cnt = 0
for i in range(n):
  if d[a[i]] >= 2:
    for j in range(a[i],mx+1,a[i]):
      chk[j] = True
    continue
  if chk[a[i]] == False:
    cnt += 1
  for j in range(a[i],mx+1,a[i]):
    chk[j] = True
print (cnt)

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

K = 10**6+1
num = [0] * K
l = [False] * K
for i in range(N):
    num[A[i]]+=1
    l[A[i]] = True

for i in range(1, K):
    if num[i]>0:
        if num[i]>1:
            l[i] = False
        j = 2
        while i*j < K:
            l[i*j] = False
            j += 1

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

print(ans)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
M = max(A)
num = [0] * (M)
T = [0] * (M)
for a in A:
  num[a-1] += 1
  T[a-1] = 1
for i in range(M):
  if num[i] != 0 and T[i] == 1:
    n = 2 * (i + 1)
    while n <= M:
      T[n-1] = 0
      n += (i + 1)
ans = 0
for i in range(M):
  if T[i] == 1 and num[i] == 1:
    ans += 1
print(ans)

Solution (Python):
from sys import stdin
from sys import setrecursionlimit
from collections import Counter
from numba import jit

setrecursionlimit(10 ** 7)

n = int(stdin.readline().rstrip())
a = list(map(int,stdin.readline().rstrip().split()))
a.sort()
b = list(set(a))
b.sort()
c = Counter(a)

se = set()

@jit
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]

for i in b:
    k = make_divisors(i)
    flag = True
    for j in k:
        if j in se:
            flag = False
            break
    if flag:
        se.add(i)

point = len(se)

for i in se:
    if c[i] > 1:
        point -= 1

print(point)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
MAX = max(A) 
Adic={}
for i in range(N):
  if A[i] not in Adic:
    Adic[A[i]] = 1
  else:
    Adic[A[i]] += 1
Aset = set(A)
if 1 in Aset: 
  if Adic[1] == 1:
    print(1)
  else:
    print(0)
  exit()
ans = 0
for j in range(N):
  temp = A[j]
  if Adic[temp] >= 2: 
    if temp in Aset:
      Aset.remove(temp)
  fmax = MAX//temp
  
  for i in range(2,fmax+10): 
    now = temp*i
    if now in Aset:
      Aset.remove(now)

print(len(Aset))

Solution (Python):
from collections import Counter, defaultdict

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

C = Counter(A)
D = defaultdict(bool)
for key in C.keys():
    D[key] = True

B = [True] * N
ans = 0
for i in range(N):
    if not D[A[i]]: continue
    if C[A[i]] > 1:
        D[A[i]] = False

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

ans = 0
for key in D:
    if D[key]:
        ans += 1
print(ans)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
A.sort()
d = {}
n = A[-1]
def makePrimeChecker(n):
    isPrime = [True] * (n + 1)
    i = 0
    for j in A:
        if i == j:
            isPrime[i] = False
            continue
        i = j
        if isPrime[i]:
            for j in range(i * 2, n + 1, i):
                isPrime[j] = False
    return isPrime
P = makePrimeChecker(n)
i = 0
ans = 0
for j in A:
    if i == j:
        continue
    else:
        i = j
        if P[i]:
            ans += 1
print(ans)

Solution (Python):
import math
N = int(input())
A_array = list(map(int, input().split()))

A_array.sort()

ans = 0

if A_array[0] == 1:
    if N >= 2 and A_array[1] != 1 or N == 1:
        print(1)
    else:
        print(0)
    exit()


ng_array = [0] * (10 ** 6)


for i, a in enumerate(A_array):
    if i != 0 and a == A_array[i - 1]:
        continue
    j = 2
    while a * j <= 10 ** 6:
        ng_array[a * j - 1] = 1
        j += 1


for i in range(N):
    a = A_array[i]
    if i != 0:
        if A_array[i] == A_array[i - 1]:
            continue
    if i != N - 1:
        if A_array[i] == A_array[i + 1]:
            continue
    if ng_array[a-1] == 0:
        ans += 1
print(ans)

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

C=[1 for i in range(10**6+1)]
for i in range(N):
    if C[A[i]]==0:  
        continue
    if C[A[i]]==-1:  
        C[A[i]]=0
        continue
    C[A[i]]*=-1  
    j=2
    while A[i]*j<=10**6:  
        C[A[i]*j]=0
        j+=1

print(C.count(-1))

Solution (Python):

import sys

sysread = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)
from heapq import heappop, heappush




import numpy as np






def run():
    N = int(input())
    A = list(map(int, sysread().split()))
    NN = 10 ** 6 + 1
    A = sorted(A)
    checks = np.array([True] * NN)
    ret = 0
    for i, a in enumerate(A[:-1]):
        if checks[a] and a != A[i+1]:
            ret += 1
        if checks[a]:
            checks[a:NN+1:a] = False
    if checks[A[-1]]:
        ret += 1


    print(ret)

if __name__ == "__main__":
    run()

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

Solution (Python):
n=int(input())
alist=list(map(int,input().split()))
alist.sort()
nolist=[False]*(10**6+1)

counter=0
for i,a in enumerate(alist):
    if not nolist[a]:
        for j in range(10**6 // a):
            nolist[a*(j+1)] = True

        if i == n-1:
            counter += 1
        elif alist[i+1] != a:
            counter += 1
print(counter)

Solution (Python):
def solve(A,N):
    A.sort()
    if N == 1:
        return 1
    elif N == 2:
        if A[1] == A[0]:
            return 0
        elif A[1] % A[0] == 0:
            return 1
        else:
            return 2
    else:
        Col = set()
        if A[0] == A[1]:
            Col.add(A[0])
        for i in range(1,N-1):
            if A[i-1] == A[i] or A[i] == A[i+1]:
                Col.add(A[i])
        if A[N-1] == A[N-2]:
            Col.add(A[N-1])

        Mul = set()
        cand = set()
        for i in range(N):
            if A[i] not in Mul:
                if A[i] not in Col:
                    cand.add(A[i])
                for d in range(1,(A[N-1]//A[i])+1):
                    Mul.add(A[i] * d)

        return len(cand)

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

    print(solve(A,N))

if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict

n = int(input())
As  = list(map(int, input().split()))
if n == 1:
    print(1)
    exit()

Ss = sorted(As)
cnt = 0
d = defaultdict(int)
As = [False] * (10**6+10)

for s in Ss:
    d[s] += 1

for s in Ss:
    if As[s]:continue
    else:
        if d[s] == 1:
            cnt += 1
        ind = 1
        while s * ind <= 10**6:
            As[s*ind] = True
            ind += 1

print(cnt)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
  
def chk(arr, n): 
  
    s = dict() 
    max_ele = -10**9
    for i in range(n):
        if arr[i] not in s: 
            s[arr[i]] = 1
        else:
            s[arr[i]] += 1
        max_ele = max(max_ele, arr[i]) 
      
    res = dict() 
    for i in range(n):
        for j in range(arr[i] * 2,  
                        max_ele + 1, arr[i]): 
                
            if (j in s.keys()): 
                res[j] = 1
    p = 0
    for i in arr:
        if i not in res.keys() and s[i] == 1:
            p += 1
    return(p)
  
print(chk(A, N) )

Solution (Python):
from math import sqrt
from random import randint
def Divisor_Set(n):
    s = set()
    for i in range(1, int(sqrt(n))+2):
        if n%i == 0:
            s.add(i)
            s.add(n//i)
    return s

def main1():
    n = int(input())
    a = list(map(int, input().split()))
    dic = {}
    for x in a:
        if x in dic:
            dic[x] += 1
        else:
            dic[x] = 1
    ans = 0
    a.sort()
    for i in range(n):
        v = a[i]
        if dic[v] > 1:
            continue
        lim = v//2 + 1
        f = True
        for j in range(i):
            if a[j] > lim:
                break
            if a[i] % a[j] == 0:
                f = False
                break
        if f:
            ans += 1
    print(ans)

def main2():
    n = int(input())
    a = list(map(int, input().split()))
    dic = {}
    for x in a:
        if x in dic:
            dic[x] += 1
        else:
            dic[x] = 1
    ans = 0
    for v in a:
        if dic[v] > 1:
            continue
        tmp = Divisor_Set(v)
        tmp.remove(v)
        f = True
        for x in tmp:
            if x in dic:
                f = False
                break
        if f:
            ans += 1
    print(ans)

if __name__ == "__main__":
    if randint(1, 2) == 1:
        main1()
    else:
        main2()