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):
def main():
    n = int(input())
    a = list(map(int, input().split()))
    a = sorted(a)

    max_a = max(a) + 1
    dp = [True] * max_a

    for idx in range(len(a)):
        if idx + 1 != len(a) and a[idx] == a[idx + 1]:
            dp[a[idx]] = False
        i = a[idx]
        x = 2
        while i * x < max_a:
            dp[i * x] = False
            x += 1

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


if __name__ == "__main__":
    main()

Solution (Python):
N=int(input())
A=sorted(map(int,input().split()))
m=max(A)
ans=0
dp=[True]*(m+1)
for i in range(N):
    if not dp[A[i]]:
        continue
    if i==N-1:
        ans+=1
    elif i<N-1 and A[i+1]!=A[i]:
        ans+=1
    for j in range(1,m//A[i]+1):
        dp[A[i]*j]=False
print(ans)

Solution (Python):
import sys

def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))

def main():
    n = II()
    aa = MII()
    aa.sort()
    maxa = aa[-1]
    dp = [False]*(maxa+1)
    for a in aa:
        dp[a] = True
    dup = set()
    for a in aa:
        if a in dup:
            dp[a] = False
            continue
        else:
            dup.add(a)
        if dp[a]:
            for j in range(a*2,maxa+1,a):
                dp[j] = False
    print(sum(1 for d in dp if d))



if __name__ == '__main__':
    main()

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

ndiv_sum = 0
max_num = A[-1]
no_div = [True] * (max_num+1)
for i in range(len(A)-1):
    if no_div[A[i]]:
        for j in range(A[i], max_num+1, A[i]):
            no_div[j] = False
        if A[i]!=A[i+1]:
            ndiv_sum += 1
if no_div[A[-1]]:
    ndiv_sum += 1
print(ndiv_sum)

Solution (Python):
from collections import Counter
n = int(input())
A = tuple(map(int, input().split()))
C = Counter(A)
A = list(set(A))
ok = [True] * (10**6+1)

for a in A:
    temp = a+a
    while temp < 10**6+1:
        ok[temp] = False
        temp += a

c = 0
for a in A:
    if C[a] == 1 and ok[a] == True:
        c += 1
print(c)

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

a = sorted(a)

max = a[len(a)-1]
line = [0]*(max+1)

for x in a:
    line[x] += 1
    
for x in a:
    if line[x] == 0:
        continue
    xx = x * 2
    j = 3
    while xx <= max:
        if line[xx] != 0:
            line[xx] = 0
        xx = x * j
        j += 1
for i in range(max+1):
    if line[i] == 1:
        count += 1
print(count)

Solution (Python):
from collections import Counter

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

m=a[-1]+1
dp=[True]*m
c=Counter(a)
ans=0
for x in a:
    if dp[x] and c[x]==1:
        ans+=1
    
    for j in range(2*x, m, x):
        dp[j]=False

print(ans)

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

ans=0
dp=[True]*(10**6+1)
for i in range(N):
    if not dp[A[i]]:
        continue
    if i==N-1:
        ans+=1
    elif i<N-1 and A[i+1]!=A[i]:
        ans+=1
    for j in range(1,10**6//A[i]+1):
        dp[A[i]*j]=False
print(ans)

Solution (Python):

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

a_frq_dict = collections.Counter(A)
A = sorted(a_frq_dict.keys())

bads = set()
max_a = max(A)
n = len(A)
for i in range(n):
    if A[i] in bads:
        pass

    elif a_frq_dict[A[i]] > 1:
        bads.add(A[i])
        for a in range(A[i]*2, max_a+1, A[i]):
            if a in a_frq_dict:
                bads.add(a)

    else:
        for a in range(A[i]*2, max_a+1, A[i]):
            if a in a_frq_dict:
                bads.add(a)

answer = set(A) - bads

print(len(answer))

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()
n = int(input())
a = list(map(int, input().split()))

check = [True for _ in range(10**6 + 5)]
dic = {}
if len(a) == 1:
    print(1)
    exit()

for i in a:
    if i in dic:
        dic[i] += 1
        continue
    dic[i] = 0
    now = 2 * i
    while (10**6 + 3 > now):
        check[now] = False
        now += i

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

Solution (Python):

from collections import Counter

N = int(input())
A = list(int(a) for a in input().split())
c = Counter(A)
ng = set([i[0] for i in c.items() if i[1] >= 2])
A.sort()

M = max(A)
primes = []
is_prime = [True] * (M+1)
for i, a in enumerate(A):
    if is_prime[a]:
        if a not in ng:
            primes.append(a)
        for j in range(a*2, M+1, a):
            is_prime[j] = False
print(len(primes))

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


N = int(input())

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

A.sort()
Set = set()

Amax = A[len(A) - 1]

counter = Counter(A)
ans = 0
for a in A:
    if a in Set:
        continue
    x = a
    while(x <= Amax):
        Set.add(x)
        x += a

    if counter[a] == 1:
        ans += 1

print(ans)

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

Solution (Python):
from collections import Counter
def main():
    n=int(input())
    A=list(map(int,input().split()))
    A.sort()
    C=Counter(A)
    m=A[-1]
    Flag=[True]*(m+1)
    ans=0
    for i,a in enumerate(A):
        if Flag[a]:
            ans+=int(C[a]==1)
            for i in range(a*2,m+1,a):
                Flag[i]=False
    print(ans)
    
if __name__=='__main__':
    main()

Solution (Python):


N = int(input())

d = [0] * (10**6 + 1) 
A = list(map(int, input().split()))

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

ans = 0
maxa = max(A) + 1
for i in range(1,maxa):
  if d[i] == 1:
    ans += 1

  if d[i] > 0:
    
    for j in range(i*2,maxa,i):
      d[j] = 0

print(ans)

Solution (Python):
from collections import Counter

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

is_p=[1 for i in range(10**6+1)]

for i in set(a):
  v=i
  if is_p[v]:
    for j in range(v+v,10**6+1,v):
      is_p[j]=0

c=Counter(a)

cnt=0
for i in a:
  if is_p[i]==1 and c[i]==1:
    cnt+=1

print(cnt)

Solution (Python):
from collections import deque, defaultdict, Counter
N = int(input())
A = list(map(int, input().split()))
c = Counter(A)
s = list(set(c))

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

for x in s:
  num = x * 2
  while num <= 10 ** 6:
    dp[num] = False
    num += x

ans = 0
for a in A:
  if c[a] == 1 and dp[a] == True:
    ans += 1
    
print(ans)

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

A.sort()
S = set(A)
M = max(A)

preA = 0
for i in A :
  if preA == i :
    S.discard(i)
  if i in S :
    num = i * 2
    while num <= M :
      S.discard(num)
      num += i    
  preA = i
  
print(len(S))

Solution (Python):
import sys
readline = sys.stdin.buffer.readline
from collections import Counter
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


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

    count = Counter(A)
    S = list(set(A))
    S.sort()
    max_A = max(A)

    bl = [True] *(max_A+1)

    for x in S:
        if bl[x] == False:
            continue
        t = x*2
        while t<=max_A:
            bl[t] = False
            t += x

    ans = 0
    for x in S:
        if count[x]==1 and bl[x]==True:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

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()

list_a = [0] * (10 ** 6 + 1)
list_b = [0] * (10 ** 6 + 1)

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

ans = 0
for i in range(1, 10 ** 6 + 1):
    if not list_a[i]:
        continue
    if list_a[i] == 1 and not list_b[i]:
        ans += 1
    for j in range(1, 10 ** 6 + 1):
        if i * j >= 10 ** 6 + 1:
            break
        list_b[i * j] = 1
print(ans)

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

A.sort()
V = set()

ans = 0
mx = max(A)
for a in A:
    if a in V:
        continue
    if cntA[a] == 1:
        ans += 1

    p = a
    while p <= mx:
        V.add(p)
        p += a

print(ans)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
B = set()
C = set()
for a in A:
    if a in B:
        C.add(a)
    else:
        B.add(a)
M = max(B)
bool = [1]*(M+1)
for c in C:
    bool[c] = 0
for b in B:
    for i in range(b*2, M+1, b):
        bool[i] = 0
ans = 0
for a in A:
    if bool[a] == 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):
n = int(input())
arr = list(map(int, input().split()))
arr.sort()

dp = [0] * (10**7)

cnt = 0
for i in range(n):
    if dp[arr[i]] == 0:
        for j in range(1, (10**6 + 10) // arr[i] + 1):
            dp[arr[i] * j] += 1
        if i < n - 1:
            if arr[i] == arr[i + 1]:
                continue
        cnt += 1
    else:
        continue

print(cnt)

Solution (Python):
def main1():
    N=int(input())
    A=list(map(int,input().split()))
    A.sort()
    ans=[0]*(10**6+1)
    if N ==1 :
        print(1)
        return 
    for i in  range(len(A)):
        ans[A[i]]+=1
        if ans[A[i]]==1:
            for j in range(A[i]*2,10**6+1,A[i]):
                ans[j]=2
    print(ans.count(1))
main1()

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

c = [0] * (m + 1)
for i in range(n):
    for j in range(a[i], m + 1, a[i]):
        c[j] += 1

ans = 0
for e in list(set(a)):
    if c[e] == 1:
        ans += 1

print(ans)

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

n = int(input())
a = list(map(int, input().split()))
MAX = 10 ** 6

c = Counter(a)
arr = np.zeros(MAX + 1, np.int64)
st = set()
for k, v in c.items():
    if v != 1:
        st.add(k)
    arr[k] = 1

for i in range(MAX + 1):
    if arr[i]:
        arr[i*2::i] = 0

    if i in st:
        arr[i] = 0

print(arr.sum())

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

A_max = max(A)
L = [0]*(A_max+1)
A.sort()

for a in A:
    temp = a
    while temp < A_max+1:
        L[temp] += 1
        temp += a

ans = 0
for a in A:
    if L[a] == 1:
        ans += 1

print(ans)

Solution (Python):
import sys

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

N = I()
A = LI()
A = sorted(A)

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

B = [0]*(10**6+1)  
C = [0]*(10**6+1)  
for i in range(len(A)):
    if B[A[i]] == 0:
        C[A[i]] = 1
    for j in range(A[i],10**6+1,A[i]):
        B[j] = 1

from collections import Counter

c = Counter(A)

for i in c.keys():
    if c[i] >= 2:
        C[i] = 0

print(sum(C))

Solution (Python):

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = lr()
A.sort()
bl = [True] * (A[-1]+1)
answer = 0
for i, a in enumerate(A):
    if i < N-1 and A[i+1] == a:
        pass
    elif bl[a]:
        answer += 1
    if bl[a]:
        bl[a] = False
        next = a + a
        while next <= A[-1]:
            bl[next] = False
            next += a

print(answer)

Solution (Python):
import itertools
from collections import Counter
h = int(input())
if h == 1:
	print(1)
	exit()
a = list(map(int,input().split()))
t = Counter(a)
b = []
for i, j in t.most_common():
	if j == 1:
		b.append(i)
bset = set(a)

def sieve(n):
	ret = []
	divlis = [-1]*(n+1)  
	flag = [True]*(n+1)
	flag[0] = False
	flag[1] = False
	ind = 2
	while ind <= n:
		if flag[ind]:
			ret.append(ind)
			ind2 = ind**2
			while ind2 <= n:
				flag[ind2] = False
				divlis[ind2] = ind
				ind2 += ind
		ind += 1
	
	return ret

k = sieve(1000)

def pfact(m):
	pf = {}
	cnt = 0
	i = k[cnt]
	st = len(k)
	while m > 1 and cnt < st:
		i = k[cnt]
		while m%i == 0:
			pf[i] = pf.get(i,0) + 1
			m //= i
		cnt += 1
	if m>1 : pf[m]=1
	return pf

def makediv(n):
	s = pfact(n)
	k = [range(i+1) for i in s.values()]
	ansl = []
	for i in itertools.product(*k):
		ans = 1
		for n, j in enumerate(s.keys()):
			ans *= (j**i[n])
		ansl.append(ans)
	ansl.sort()
	return ansl

ans = 0
for i in b:
	t=makediv(i)
	t.remove(i)
	mode = 1
	for l in t:
		if l in bset:
			mode = 0
			break
	if mode:
		ans += 1
print(ans)

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

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

def main():
    mod=10**9+7
    N=I()
    A=LI()
    M=10**6+5
    dp=[1]*M
    A.sort()
    L=[A[0]]
    L2=set([])
    for i in range(1,N):
        if A[i]!=L[-1]:
            L.append(A[i])
        else:
            L2.add(A[i])
            
    for i in range(len(L)):
        temp=L[i]
        if dp[temp]==1:
            temp+=L[i]
            while temp<M:
                dp[temp]=0
                temp+=L[i]
        
    ans=0    
    for i in L2:
        dp[i]=0
        
    for i in range(len(L)):
        if dp[L[i]]==1:
            ans+=1
            
            
    

         
            
    print(ans)
                
    
    


main()

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

used = [False] * a[-1]
res = 0
for i in range(n):
    if used[a[i]-1]:
        continue
    if i == n - 1 or a[i] != a[i+1]:
        res += 1
    for j in range(a[i], a[-1]+1, a[i]):
        used[j-1] = True

print(res)

Solution (Python):
from collections import Counter
n = int(input())
ns = list(map(int, input().split()))
c = Counter(ns)
ans = 0

l = [True] * (max(ns)+1)
for i in sorted(set(ns)):
    if l[i]:
        j = i*2
        while j < len(l):
            l[j] = False
            j += i

a = set([key for key, value in c.items() if value == 1])
for i in a:
    if l[i]:
        ans += 1
print(ans)

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

div = defaultdict(bool)
count = 0
for i in range(n):
    b = a[i]
    if div[b]:
        count += 1
    else:
        for j in range(1,ma//b+1):
            div[j*b] = True
        if(i+1<n and a[i] == a[i+1]):
            count += 1

print(n-count)

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

import numpy as np
from numba import njit


def main():
    @njit('i8(i4[::1],)', cache=True)
    def f(A):
        count = np.zeros((A.max() + 1))
        for a in A:
            if count[a] > 1:
                continue
            count[::a] += 1

        ret = 0
        for a in A:
            ret += count[a] == 1

        return ret

    N = int(input())
    A = np.array(readline().split(), np.int32)

    print(f(A))


if __name__ == '__main__':
    main()

Solution (Python):


N = int(input())

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

for a in map(int, input().split()):
  d[a] += 1

ans = 0

for i in range(1,10**6+1):
  if d[i] == 1:
    ans += 1

  if d[i] > 0:
    
    for j in range(i*2,10**6+1,i):
      d[j] = 0

print(ans)

Solution (Python):
import sys
from collections import Counter

N = int(input())
A = list(map(int, sys.stdin.readline().rsplit()))
C = Counter(A)
s = []
dp = [True] * (10 ** 6 + 1)

for a, b in C.items():
    if b == 1:
        s.append(a) 

a = set(A)
for ss in a:
    for m in range(2 * ss, 10 ** 6 + 1, ss):
        dp[m] = False

res = 0
for ss in s:
    if dp[ss] is True:
        res += 1

print(res)

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

a.sort()

m = a[-1]
dp = [True] * m
for i in range(n):
    if dp[a[i]-1]:
        t = a[i]
        j = 2
        while True:
            if t*j-1 < m:
                dp[t*j-1] = False
                j += 1
            else:
                break
a = Counter(a)
ans = 0
for i, j in a.items():
    if j == 1 and dp[i-1]:
        ans += 1
print(ans)

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

INF = 10**20
def main():
    N = int(input())
    A = list(map(int,input().split()))

    seen = set()
    dup = set()
    ng = 0
    B = []

    for a in A:
        if not a in seen:
            B.append(a)
            seen.add(a)
        else:
            dup.add(a)


    out = set()
    mx = max(B)
    for b in B:
        c = 2
        while c * b <= mx:
            out.add(c * b)
            c += 1

    for a in A:
        if a in out or a in dup: ng += 1


    print(N-ng)






if __name__ == "__main__":
  main()

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

def main():
    n = int(input())

    A = sorted(map(int, input().split()))
    counter = Counter(A)

    ans = 0
    maxi = max(A)
    cache = set()
    for a in A:
        if a in cache:
            continue

        x = a
        while x <= maxi:
            cache.add(x)
            x += a

        if counter[a] == 1:
            ans += 1

    print(ans)

main()

Solution (Python):
import sys
from collections import Counter

N = int(input())
A = list(map(int, sys.stdin.readline().rsplit()))
C = Counter(A)
s = []
dp = [True] * (10 ** 6 + 1)

for a, b in C.items():
    if b == 1:
        s.append(a) 

a = set(A)
for ss in a:
    for m in range(2 * ss, 10 ** 6 + 1, ss):
        dp[m] = False

res = 0
for ss in s:
    if dp[ss] is True:
        res += 1

print(res)

Solution (Python):
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")



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

    dp = [True] * (max(A) + 1)
    tmp = 0
    for a in A:
        if a == tmp:
            dp[a] = False
            continue
        tmp = a
        i = 2
        while a*i < len(dp):
            dp[a*i] = False
            i += 1
    
    ans = 0
    for a in A:
        if dp[a] == True:
            ans += 1
    
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce
from operator import mul
import pprint



sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

n = I()
A = sorted(LI())
ans = 0
cnt = Counter(A)
m = max(A) + 1
B = [0] * (10 ** 6 + 1)
for a in A:
    if B[a] == 0 and cnt[a] == 1:
        ans += 1
    for i in range(a * 2, m, a):
        B[i] = 1


print(ans)

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

dlen = A[-1]+3
d = [True]*dlen
for a in A:
    if d[a]:
        for i in range(a*2, dlen, a):
            d[i] = False

res = 0
for i in range(N):
    if i > 0:
        if A[i] == A[i-1]:
            continue
    if i < N-1:
        if A[i] == A[i+1]:
            continue
    if d[A[i]]:
        res += 1
print(res)

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

def main():
    n = int(input())

    A = sorted(map(int, input().split()))
    counter = Counter(A)

    if not A:
        print(0)
        return

    ans = 0
    maxi = max(A)
    cache = set()
    for a in A:
        if a in cache:
            continue

        x = a
        while x <= maxi:
            cache.add(x)
            x += a

        if counter[a] == 1:
            ans += 1

    print(ans)

main()

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(200000)
from collections import defaultdict
from bisect import bisect_left


def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def prime_factorization(n, primes):
    """
    nの素因数分解を求める
    """
    prime_factors = defaultdict(int)
    if n < 2:
        return prime_factors
    for p in primes:
        if p * p > n:
            break
        while n % p == 0:
            prime_factors[p] += 1
            n //= p
    if n > 1:
        prime_factors[n] = 1
    return prime_factors


def sieve(n):
    """
    n以下の素数を昇順に列挙する
    """
    is_prime = [True for i in range(n+1)]
    primes = []
    for i in range(2, n+1):
        if is_prime[i]:
            primes.append(i)
            for j in range(i+i, n+1, i):
                is_prime[j] = False
    return primes


def solve(N, A):
    A.sort()
    AMAX = max(A)
    ans = 0
    is_div = [True for i in range(AMAX+1)]
    for i in range(N):
        a = A[i]
        if is_div[a]:
            if not ((i > 0 and A[i] == A[i-1]) or (i < N-1 and A[i] == A[i+1])):
                ans += 1
            for j in range(a, AMAX+1, a):
                is_div[j] = False
    return ans


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

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

n = int(input())
A = sorted(map(int, input().split()))
U = 10**6
B = [0]*(U+1)
C = Counter(A)
ans = 0
for a in A:
  if B[a]:
    continue
  if C[a] == 1:
    ans += 1
  for j in range(a, U+1, a):
    B[j] = 1
print(ans)

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

As.sort()


all_nums = [0] * (As[-1] + 1)

for A in As:
    all_nums[A] += 1

dup = 0

for i, num in enumerate(all_nums):
    if num == 0: 
        continue
    if num > 1: 
        dup += num
    j = 2
    while i * j <= As[-1]:
        all_nums[i*j] = 0
        j += 1
    

print(sum(all_nums)-dup)

Solution (Python):


N = int(input())
A = sorted(map(int, input().split()))
maxA = A[N - 1]
dp = [0] * (maxA + 1)

for i in range(len(A)):
    cursor = A[i]
    while cursor <= maxA:
        dp[cursor] += 1
        cursor += A[i]

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

print(ans)

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

import numpy as np
from numba import njit


@njit('i8(i4[::1],)', cache=True)
def f(A):
    count = np.zeros((A.max() + 1))
    for a in A:
        if count[a] > 1:
            continue
        count[::a] += 1

    ret = 0
    for a in A:
        ret += count[a] == 1

    return ret

N = int(input())
A = np.array(readline().split(), np.int32)

print(f(A))

Solution (Python):
from collections import defaultdict

n = int(input())
a = list(map(int, input().split()))
a.sort()
d = defaultdict(int)
for ai in a:
    d[ai] += 1

m = a[-1]
x = [True for _ in range(m + 1)]

ans = 0
c = defaultdict(bool)
for ai in a:
    if x[ai] and d[ai] == 1:
        ans += 1
    if not c[ai]:
        c[ai] = True
        for j in range(2 * ai, m + 1, ai):
            x[j] = False
print(ans)

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

A = sorted(A)
C = Counter(A)
S=set(A)

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

ans=0
for i in range(1,A[-1]+1):
    if dp[i]:
        if i in S:
            for j in range(i,A[-1]+1,i):
                dp[j]=False
            if C[i]==1:
                ans+=1
print(ans)

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def 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 set(divisors)


def main():
    from collections import Counter

    n = int(readline())
    a = list(map(int, readline().split()))
    counter = Counter(a)
    a.sort()
    mx = max(a)

    ok = [True] * (mx + 1)

    for x in a:
        for y in range(2 * x, mx + 1, x):
            ok[y] = False

    ans = 0
    prev = -1
    for key, val in counter.items():
        if val > 1:
            pass
        else:
            if ok[key]:
                ans += 1

    print(ans)


if __name__ == '__main__':
    main()

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

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

ans=0
A.sort()

f=[0]*1000005

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

for i in range(1,1000001,1):
    if f[i]==0:
        continue
    j=i+i
    while j<=1000000:
        f[j]+=f[i]
        j=j+i

for i in A:
    if f[i]==1:
        ans+=1


print(ans)

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

for a in A:
    A_div[a] += 1
    if A_div[a] == 1:
        for j in range(2 * a, 10 ** 6 + 1, a):
            A_div[j] += 100

print(A_div.count(1))

Solution (Python):
N=int(input())
alist=list(map(int,input().split()))
max_a=max(alist)

exclude_set=set()
tlist=[False]*(max_a+1)
for a in alist:
  if tlist[a]:
    exclude_set.add(a)
  else:
    tlist[a]=True


for i in range(1,max_a//2+1):
  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 exclude_set:
    answer+=1
    
print(answer)

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

for a in A:
  B[a]+=1
  if B[a]==1:
    for n in range(2*a,10**6+1,a):
      B[n]+=2

print(B.count(1))

Solution (Python):
N = int(input())
A = sorted(list(map(int, input().split())))
if N == 1:
    print(1)
elif A[0] == 1 and A[1] == 1:
    print(0)
elif A[0] == 1:
    print(1)
else:
    Eratos = [False]*1000001
    ans = 0
    for i in range(N):
        if Eratos[A[i]]:
            ans += 1
        else:
            if i < N-1 and A[i] == A[i+1]:
                ans += 1
            for j in range(A[i], 1000001, A[i]):
                Eratos[j] = True
    print(N-ans)

Solution (Python):
import collections


def main():
    n = int(input())
    al = list(map(int, input().split()))
    al.sort()

    dp = [1]*(10**6+1) 
    for a in al:
        if dp[a] >= 0:
            dp[a] -= 1
            for i in range(2,10**6//a + 1):
                dp[a*i] -= 2
    
    ans = 0
    for a in al:
        if dp[a] >= 0: ans+=1
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
p = [True] * (10 ** 6 + 1)
s = list(set(a))
for x in s:
    t = x * 2
    while t <= 10 ** 6:
        p[t] = False
        t += x
ans = 0
for x in a:
    if c[x] == 1 and p[x] == True:
        ans += 1
print(ans)

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

A.sort()

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

B = [False] * (10**6 + 1)

ans = 0

for a in A:
    if B[a] == False:
        c = 1
        i = a * c
        while i <= 10 ** 6:
            B[i] = True
            c += 1
            i = a * c
        if D[a] == 1:
            ans += 1

print(ans)

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

ans = 0
A = [True]*(10**6+1)

for i in range(0, N):
    if not A[S[i]]:
        continue
    if 0 < i:
        if S[i-1] == S[i]:
            continue
    if i < N-1:
        if S[i] == S[i+1]:
            for j in range(1, 10**6//S[i]+1):
                A[S[i]*j] = False
            continue
    ans += 1
    for j in range(1, 10**6//S[i]+1):
        A[S[i]*j] = False

print(ans)

Solution (Python):
def resolve():
    n = int(input())
    a = list(map(int, input().split()))
    a1 = {}
    for i in range(len(a)):
        if a[i] in a1:
            a1[a[i]] += 1
        else:
            a1[a[i]] = 1
    a = sorted(list(a1.keys()))
    ans = [1] * a[-1]

    for i in a:
        if ans[i-1] == 1:
            for j in range(i-1, len(ans), i):
                ans[j] = 0
            ans[i-1] =1
    ans1 = 0
    for i in a:
        if a1[i] == 1:
            ans1 += ans[i-1]
    print(ans1)
resolve()

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
m = max(A)+10
dp = [0] * m

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

ans = 0
for i in range(1, m):
    if dp[i]:
        if dp[i] == 1:
            ans += 1
        for j in range(i, m, i):
            dp[j] = 0
print(ans)