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):
from collections import Counter

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

A.sort()
A_counter = Counter(A)

dp = [True for _ in range(10**6+1)]
for a in A_counter:
    if dp[a] == False:
        continue
    for j in range(a*2, 10**6+1, a):
        dp[j] = False

c = 0
for a, v in A_counter.items():
    if dp[a] and v == 1:
        c += 1

print(c)

Solution (Python):
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
def main():
    n, *a = map(int, read().split())
    a.sort()
    a = tuple(a)
    TorF = [0] * (a[-1] + 1)
    for ae in a:
        TorF[ae] = 1
    for i1 in range(n - 1):
        a1 = a[i1]
        if TorF[a1]:
            m = a[-1] // a1 + 1
            for i2 in range(2, m):
                TorF[a1 * i2] = 0
        if a[i1 + 1] == a[i1]:
            TorF[a[i1]] = 0
    r = sum(TorF)
    print(r)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
def main():
    n, *a = map(int, read().split())
    a.sort()
    a = tuple(a)
    TorF = [0] * (a[-1] + 1)
    for ae in a:
        TorF[ae] = 1
    for i1 in range(n - 1):
        a1 = a[i1]
        if TorF[a1]:
            m = a[-1] // a1 + 1
            for i2 in range(2, m):
                TorF[a1 * i2] = 0
        if a[i1 + 1] == a[i1]:
            TorF[a[i1]] = 0
    r = sum(TorF)
    print(r)

if __name__ == '__main__':
    main()

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

f = [0 for i in range(10**6+5)]
for x in a:
    f[x] += 1
for i in range(1, len(f)):
    if f[i] == 0:
        continue
    for j in range(2*i, len(f), i):
        f[j] = 0
ans = 0
for v in f:
    if v == 1:
        ans += 1
print(ans)

Solution (Python):
from itertools import combinations
from collections import Counter
class Osa_k:
    def __init__(self, n_max):
        self.n_max = n_max
        self.min_factor = min_factor = list(range(n_max + 1))
        min_factor[2::2] = [2] * (n_max // 2)
        min_factor[3::6] = [3] * ((n_max + 3) // 6)
        for i in range(5, int(n_max ** .5) + 1, 2):
            if min_factor[i] == i:
                for j in range(i*i, n_max + 1, i):
                    if min_factor[j] == j:
                        min_factor[j] = i

    def __call__(self, n):
        min_factor = self.min_factor
        n_twoes = (n & -n).bit_length() - 1
        res = [2] * n_twoes
        n >>= n_twoes
        resappend = res.append
        while n > 1:
            p = min_factor[n]
            resappend(p)
            n //= p
        return res
    
    def div(self, n):
        factors = self.__call__(n)
        res = {1, n}
        for i in range(1, len(factors)):
            for j in combinations(factors, i):
                r = 1
                for p in j:r *= p
                res |= {r}
        return res

if __name__ == "__main__":
    n, *a = map(int, open(0).read().split())
    b, c = set(a), Counter(a)
    P = Osa_k(10**6)
    cnt = 0
    for i in b:
        if c[i] > 1:continue
        for d in P.div(i):
            if d != i and d in b:break
        else:cnt += 1
    print(1 if n == 1 else cnt)

Solution (Python):
from collections import Counter
n, *A = map(int, open(0).read().split())
A.sort()
c, s = Counter(A), set()
M = max(A) + 1
ans = 0
for a in A:
    if a in s:
        continue
    ans += c[a] == 1
    for i in range(a, M, a):
        s.add(i)
print(ans)

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

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

aMax = a[-1]
l = len(a)
count = 0
k = 0
kSet = set()

for i in range(n):
    value = a[i]
    if not(value in kSet):
        if i != 0 and a[i-1] == value:
            count -= 1
            kSet.add(value)
            continue
        count += 1
        j = 2
        k = 0
        while k < aMax:
            k = a[i] * j
            kSet.add(k)
            j += 1

print(count)

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

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

aMax = a[-1]
l = len(a)
count = 0
k = 0
kSet = set()

for i in range(n):
    value = a[i]
    if not(value in kSet):
        if i != 0 and a[i-1] == value:
            count -= 1
            kSet.add(value)
            continue
        count += 1
        j = 2
        k = 0
        while k < aMax:
            k = a[i] * j
            kSet.add(k)
            j += 1
    
    

print(count)

Solution (Python):
import sys

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

array = [0 for i in range((10 ** 6)+1)]
for v in a:
  array[v] += 1
  
for i in range(1, len(array)):
  if array[i] == 0:
    continue
    
  for j in range(i*2, len(array), i):
    array[j] = 0
    
count = 0
for v in array:
  if v == 1:
    count += 1
    
print(count)

Solution (Python):
import sys
def I(): return int(sys.stdin.readline().rstrip())
def IL(): return map(int,sys.stdin.readline().rstrip().split())

def solve():
    m = a[-1]+1
    ava = [0]*m
    for rep in a:
        ava[rep] += 1
        if ava[rep]==1:
            for item in range(2*rep,m,rep):
                ava[item] += 2

    print(ava.count(1))
    return

if __name__=='__main__':
    n = I()
    a = list(IL())
    a.sort()
    solve()

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

a_max = a[-1]
dp = [1]*a_max

for i in set(a):
    j = 2
    while i*j <= a_max:
        dp[i*j-1] = 0
        j += 1

a.append(0)
ans = 0
for i in range(n):
    if dp[a[i]-1] and a[i-1] != a[i] and a[i] != a[i+1]:
        ans += 1
print(ans)

Solution (Python):

from collections import Counter

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


lim = 10 ** 6 + 10
ok = [True] * (lim + 1)
ans = 0
ctr = Counter(X)
for n in sorted(X):
    if ok[n]:
        if ctr[n] == 1:
            ans += 1
        for j in range(n, lim + 1, n):
            ok[j] = False

print(ans)

Solution (Python):







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





s=[False]*(10**6+1)
cnt=0
for i,aa in enumerate(a):
  if s[aa]:
    continue

  
  if i+1 == len(a) or aa != a[i+1]:
    cnt+=1
  for i in range(1,10**6+1):
    ma=aa*i
    if ma > 10**6:
      break
    s[ma]=True

print(cnt)

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





s=set()
cnt=0
for i,aa in enumerate(a):
  if aa not in s:
    
    if i+1 == len(a) or aa != a[i+1]:
      cnt+=1
    
    for i in range(1,10**6+1):
      ma=aa*i
      if ma > 10**6:
        break
      s.add(ma)

print(cnt)

Solution (Python):


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

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

Amax = max(A)
dp = [True] * Amax
seen = set()

for a in A:
    if a in seen:
        dp[a-1] = False
        continue
    i = 2
    while i * a <= Amax:
        dp[i*a-1] = False
        i += 1
    seen.add(a)


B = [dp[a-1] for a in A]
print(sum(B))

Solution (Python):


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

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

Amax = max(A)
dp = [True] * Amax
seen = set()

for a in A:
    if a in seen:
        dp[a-1] = False
    i = 2
    while i * a <= Amax:
        dp[i*a-1] = False
        i += 1
    seen.add(a)


B = [dp[a-1] for a in A]
print(sum(B))

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

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

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

a_uniq = []

for i in range(10 ** 6 + 1):
    if cnt[i] == 1:
        a_uniq.append(i)

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

for i in list(set(a)):
    for j in range(2 * i, 10 ** 6 + 1, i):
        cnt[j] = 1

ans = 0

for i in a_uniq:
    if cnt[i] == 0:
        ans += 1

print(ans)

Solution (Python):
n=int(input())
A=sorted(list(map(int,input().split())))
B=[0]*(1+A[-1])
for i in A:
    B[i]+=1
    if B[i]==1:
        for j in range(2*i,A[-1]+1,i):
            B[j]+=1
    else:
        continue
ans=0
for i in A:
  if B[i]==1: ans+=1

print(ans)

Solution (Python):
import sys
from collections import deque

input = sys.stdin.readline

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

a.sort()
tf = [True] * a[-1]
dup = [False] * a[-1]


for i in range(n):
    if tf[a[i]-1] == True:
        
        if dup[a[i]-1] == True:
            tf[a[i]-1] = False
        else:
            dup[a[i]-1] = True
            for j in range(a[i]*2, a[-1]+1, a[i]):
                tf[j-1] = False
                

c = 0



for x in a:
    if tf[x-1]:
        c += 1

print(c)

Solution (Python):
n = int(input())
arr = list(map(int, input().split()))
arr = sorted(arr)
m = arr[-1]
li = [0]*(m+1)
cnt = 0
        
for i in arr:
  for j in range(i, m+1, i):
    li[j] += 1

for i in arr:
  if li[i] == 1:
    cnt += 1

print(cnt)

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

for i in a:
  for j in range(i,m+1,i):
    arr[j]+=1

cnt = 0
for i in a:
  if arr[i] ==1:
    cnt += 1

print(cnt)

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

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

maxVal = max(A)+1
isPrime = [0] * maxVal
isDuplicate = [0] * maxVal
isDivisible = [0] * maxVal

for i in range(len(A)-1):
    if A[i] == A[i+1]:
        isDuplicate[A[i]] = 1

for i in range(len(A)):
    if not isDivisible[A[i]]:
        isPrime[A[i]] += 1

        j = 2
        while A[i] * j < maxVal:
            isDivisible[A[i] * j] = 1

            j += 1

ans = isPrime.count(1)

print(ans)

Solution (Python):
def solve(ls):
    n = len(ls)
    lim = max(ls)
    sieve = [1] * (lim + 1)
    result = 0
    ls.sort()
    for i in range(n):
        x = ls[i]
        if sieve[x] == 0:
            continue
        
        if not (i + 1 < n and x == ls[i + 1]):
            result += 1
        y = x
        while y <= lim:
            sieve[y] = 0
            y += x
    return result


def main(istr, ostr):
    n = list(map(int, istr.readline().strip().split()))
    ls = list(map(int, istr.readline().strip().split()))
    result = solve(ls)
    print(result, file=ostr)


if __name__ == "__main__":
    import sys

    main(sys.stdin, sys.stdout)

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

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

divisible = [False] * (a_max + 1)

count = 0
i = 0
for i in range(n):
    if divisible[a_list[i]]:
        continue
    if i < n - 1 and a_list[i] == a_list[i + 1]:
        while i < n - 1 and a_list[i] == a_list[i + 1]:
            i += 1
    else:
        count += 1
    x = a_list[i]
    while x <= a_max:
        divisible[x] = True
        x += a_list[i]
print(count)

Solution (Python):
import itertools
N = int(input())
A = list(map(int, input().split()))
count = {}
for a in A:
  if a not in count:
    count[a] = 0
  count[a] += 1

def check(a):
  if count[a] > 1:
    return 0

  if 1 in count:
    if a == 1 and count[1] == 1:
      return 1
    return 0

  
  ok = True
  sqr_a = 1 + int(a**0.5)
  for s in itertools.chain([2], range(3, sqr_a, 2)):
    if a % s:
      continue
    c = s
    while c < sqr_a:
      if a % c == 0 and (c in count or (a//c) in count):
        
        ok = False
        break
      c *= 2
  return ok
  
ans = 0
for a in A:
  ans += check(a)
print(ans)

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

for i in a:
  while 1:
    try:
      num[i*cnt]+=1
      cnt+=1
      
      
    except IndexError:
      break
  cnt=1      

count=0

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

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

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

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

print(dp.count(1))

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


def solve():
    amax = max(A)+1
    memo = [0] * amax
    for a in A:
        i = 1
        while i*a < amax:
            memo[i*a] += 1
            i += 1

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

    return count

if __name__ == "__main__":
    print(solve())

Solution (Python):
n = int(input())
a_ls = list(map(int, input().split()))
a_ls.sort()
a_max = a_ls[-1]
times_ls = [0] * (a_max + 1)
divisible_ls = [0] * (a_max + 1)
for i in range(n):
    base = a_ls[i]
    times_ls[base] += 1
    times = 2
    while base*times <= a_max:
        divisible_ls[base*times] = 1
        times += 1
ans = 0
for i in range(1,a_max+1):
    if times_ls[i] == 1 and divisible_ls[i] == 0:
        ans += 1
print(ans)

Solution (Python):
import sys

n = int(input())

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

m = max(A)

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

dp = [True] * m

for a in A:
  if C[a] > 0:
    C[a] += 1
    continue
  C[a] += 1
  i = 2
  while a * i <= m:
    dp[a*i - 1] = False
    i += 1
    
ans = 0

for a in A:
  if C[a] < 2 and dp[a - 1] == True:
    ans += 1

print(ans)

Solution (Python):
n=int(input())
A=sorted(list(map(int,input().split())))
B=[0]*(A[-1]+1)
for i in A:
  B[i]+=1
  if B[i]>=2:
    continue
  for j in range(2*i,A[-1]+1,i):
    B[j]+=1
ans=0
for i in A:
  if B[i]==1:
    ans=ans+1
print(ans)

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

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

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

print(dp.count(1))

Solution (Python):
n,a=int(input()),sorted(list(map(int,input().split())))
m=a[-1]+1
s=[0]*m
for i in a:
  s[i]+=1
for i in set(a):
  if s[i]:
    for j in range(i*2,m,i):
      s[j]=0
print(s.count(1))

Solution (Python):
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

M=10**6+10
n=int(input())
a=Counter(lmp()).most_common()
a=sorted(a, key=lambda x: x[0])
c=[0]*M
for j,x in a:
    if c[j]==0:
        k=2
        while j*k<M:
            c[j*k]=1
            k+=1
ans=0
for x,y in a:
    if c[x]==0 and y==1:
        ans+=1
print(ans)

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

MAX_A = 1000001

dp = [0]*MAX_A

for i in A:
  if dp[i] == 0:
    for j in range(i, MAX_A,i):
      dp[j] += 1
  else:
    dp[i] += 1

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

print(c)

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

List = [0 for x in range(1000001)]
answer = 0

def main(a, List):
    if List[a] >= 1:
        List[a] = List[a] + 1
        return List
    else:
        for i in range(a, 1000001, a):
            List[i] = List[i] + 1
    return List

def Answer(A, List):
    answer = 0
    for a in A:
        if List[a] == 1:
            answer += 1
    return answer

for a in A:
    main(a, List)

print(Answer(A, List))

Solution (Python):
n = int(input())
A = list(map(int, input().split()))
A.sort()
A_max = A[-1]
dp = [1] * (A_max + 1)
ans = 0

for i in range(len(A)-1):
    p = A[i]
    if dp[A[i]] == 1:
        for j in range(A_max // p + 1):
            dp[j*p] = 0
        if A[i] != A[i+1]:
            ans += 1
            
if dp[A_max] == 1:
    ans += 1

print(ans)

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


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

  not_divisible = [False]*(10**6+1)
  for i in range(N):
    not_divisible[A[i]] = True

  prev = 0
  for i in range(N):
    if not_divisible[A[i]]:
      j = A[i] + A[i]
      while j <= A[-1]:
        not_divisible[j] = False
        j += A[i]
    if prev == A[i]:
      not_divisible[A[i]] = False
    prev = A[i]

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

  print(cnt)


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

    MAX = max(A) + 1
    flg = [0] * MAX
    tmp = set()
    for a in A:
        if a in tmp:
            flg[a] = 1
        tmp.add(a)

    res = 0
    for a in A:
        if not flg[a]:
            res += 1
        for i in range(a, MAX, a):
            flg[i] = 1
    print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):

def inputlist(): return [int(j) for j in input().split()]

ans = 0
from collections import Counter
N = int(input())
A = inputlist()
A.sort()
dic = Counter(A)
dp = [1 for _ in range(A[-1]+1)]
for i in range(N):
    if dp[A[i]]:
        j = 2
        while A[i]*j <= A[-1]:
            dp[A[i]*j] = 0
            j +=1
        if dic[A[i]] == 1:
            ans+=1
print(ans)

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

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

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

for i in a:
	if baisuu[i]>=1:
		baisuu[i]=2
		continue

	for j in range(i,10**6+1,i):
		baisuu[j]+=1

ans=0

for i in a:
	if baisuu[i]==1:
		ans+=1

print(ans)

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

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

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

for i in a:
	if baisuu[i]>=1:
		baisuu[i]=2
		continue

	for j in range(i,10**6+1,i):
		baisuu[j]+=1

ans=0

for i in a:
	if baisuu[i]==1:
		ans+=1

print(ans)

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

A = sorted(A, key=lambda x: x)
all = [True] * 1000001
ans = 0
for i in range(N):
    if all[A[i]] == False:
        continue
    if i == N - 1 or A[i+1] > A[i]:
        ans += 1
    b = A[i]
    while b < 1000001:
        all[b] = False
        b += A[i]

print(ans)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
LN = max(A) + 1
L = [0 for i in range(LN)]
count = 0
for i in A:
    for j in range(i, LN, i):
        L[j] += 1
for i in A:
    if L[i] == 1:
        count += 1
print(count)

Solution (Python):
inf =  1100000
def main():
  N =  int(input())
  a = list(map(int, input().split()))
  a.sort()
  detect = [0] *inf
  for x in a:
    if detect[x] != 0:
      detect[x] = 2
      continue
    for i in range(x, inf, x):
      detect[i] += 1
  ans = 0
  for i in range(N):
    if detect[a[i]] == 1:
      ans += 1
  print(ans)
  
if __name__ == "__main__":
  main()

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

num_list=set()
prime_list=set()

from collections import Counter
dic=Counter(a)
a=set(a)

for i in dic:
  if dic[i]>=2:
    dic[i]=0
  if i not in num_list:
    for j in range(i*2,k+1,i):
      if j in a:
        dic[j]=0
        num_list.add(j)

print(sum(dic.values()))

Solution (Python):
n = int(input())
lst = [int(i) for i in input().split()]
lst.sort()


if 1 in lst:
  count = 0
  for i in range(n):
    if lst[i] == 1:
      count += 1
    if count == 2:
      break
  if count == 1:
    print(1)
  else:
    print(0)
else:
  tf_lst = [1] * lst[n - 1]
  count = 0
  if n > 1:
    pre = 0
    for i in range(n):
      tf_lst[pre:lst[i] - 1] = [0] * (lst[i] - pre - 1)
      pre = lst[i]
      if tf_lst[lst[i] - 1] == 0:
        continue
      if i <= n - 2:
        if lst[i] == lst[i + 1]:
          tf_lst[lst[i] - 1] = 0
      for j in range(lst[i] * 2, lst[n - 1] + 1, lst[i]):
        tf_lst[j - 1] = 0
    
    for i in tf_lst:
      count += i
  else:
    count += 1
  print(count)

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

Solution (Python):
import numpy as np

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

m = np.zeros(max(a)+1, dtype=int)
cnt = 0

for i in range(n):
    x = a[i]
    if i == n-1:
        if m[x] == 0:
            cnt +=1
    else:
        if m[x] == 0 and a[i] != a[i+1]:
            cnt +=1
    m[x::x] += 1
print(cnt)

Solution (Python):
def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    a = [0] * 1000005
    A_max = A[-1]

    for i in A:
        for j in range(1, A_max//i + 1):
            a[i * j] += 1

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

if __name__ == "__main__":
    resolve()

Solution (Python):
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
from functools import reduce

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

a.sort()

count = Counter(a)

b = [1 for i in range((max(a) + 1))]

for aa in a:
    for j in range(2*aa,len(b), aa):
        b[j] = 0

c = 0
for d in count.items():
    if d[1] == 1 and b[d[0]] == 1: c += 1

print(c)

Solution (Python):
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
from functools import reduce

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

a.sort()

count = Counter(a)

b = [1]*(max(a) + 1)

for aa in a:
    for j in range(2*aa,len(b), aa):
        b[j] = 0

c = 0
for d in count.items():
    if d[1] == 1 and b[d[0]] == 1: c += 1

print(c)

Solution (Python):
import sys
read = sys.stdin.readline
import time
import math
import itertools as it
def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
start_time = time.perf_counter()


N = inp()
A = inpl()
A.sort()
dp = [False] * 1001001
nt = -1

for i in A:
    if i != nt:
        dp[i] = True
    else:
        dp[i] = False
    nt = i

ans = 0
mx = A[N-1]
nt = -1
for i in A:
    if dp[i]:
        ans += 1
    if i == nt:
        continue
    nt = i
    j = i
    while j <= mx:
        dp[j] = False
        j += i

print(ans)


end_time = time.perf_counter()
print('time:', end_time-start_time, file=sys.stderr)

Solution (Python):
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
counter = Counter(A)
B = [1] * (max(A) + 1)
for a in A:
    for k in range(a  * 2,len(B),a):
            B[k] = 0
print(sum(B[a] == 1 and counter[a] == 1 for a in A))

Solution (Python):

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

MAX = 10 ** 6 + 1
prime = [True] * MAX
counted = set()
for v in X:
    if v in counted:
        prime[v] = False
        continue
    for j in range(2 * v, MAX, v):
        prime[j] = False
    counted.add(v)

ans = 0
for v in X:
    ans += int(prime[v])
print(ans)

Solution (Python):
from collections import Counter

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

counter = Counter(A)

dp = [1] * (max(A) + 1)
for Ai in A:
    for j in range(Ai * 2, len(dp), Ai):
        dp[j] = 0

print(sum([dp[Ai] == 1 and counter[Ai] == 1 for Ai in A]))

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
num = [0]*(10**6+1)
for x in a:
    if num[x] != 0:
        num[x] = 2
        continue
    for i in range(x, 10**6+1, x):
        num[i] += 1

ans = 0
for x in a:
    if num[x] == 1:
        ans += 1

print(ans)

Solution (Python):
import sys
N=int(sys.stdin.readline().strip())
A=map(int, sys.stdin.readline().split())
A.sort()
max_A=A[-1]

L=[ 0 for _ in range(max_A+1) ]
for a in A:
    L[a]+=1

for i,x in enumerate(L):
    if 1<x:
        L[i]=0

for a in A:
    for i in range(a*2,max_A+1,a):
        L[i]=0

print sum(L)

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

print(dp.count(1))

Solution (Python):
n,a=int(input()),sorted(list(map(int,input().split())))
m=a[-1]+1
s=[0]*m
for i in a:s[i]+=1
for i in set(a):
	if s[i]:
		for j in range(i*2,m,i):s[j]=0
print(s.count(1))

Solution (Python):
from collections import Counter

N = int(input())
A = [int(i) for i in input().split()]
num = set(A)
count = Counter(A)
dp = [True] * (10**6 + 1)

for a in num:
    for n in range(a+a, 10**6+1, a):
        dp[n] = False

ans = 0
for a in num:
    if count[a] == 1 and dp[a] == True:
        ans += 1

print(ans)

Solution (Python):



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

t = {}
for av in a:
    if av not in t:
        t[av] = 1
    else:
        t[av] += 1
limit = a[-1]

d = [True] * (limit + 1)
for av in a:
    start = av
    
    if t[av] == 1:
        start *= 2
    for i in range(start, limit + 1, av):
        d[i] = False

ans = 0
for av in a:
    if d[av]:
        ans += 1

print(ans)

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

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

for v in a:
    if xs[v] == 0:
        for j in range(v, len(xs), v):
            xs[j] += 1
    else:
        xs[v] += 1
print(len(list(filter(lambda v: xs[v] == 1, a))))

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

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

for v in a:
    if xs[v] == 0:
        for j in range(v, len(xs), v):
            xs[j] += 1
    else:
        xs[v] += 1
print(len(list(filter(lambda v: xs[v] == 1, a))))

Solution (Python):
n = int(input())
A = sorted(list(map(int, input().split())))
dp = [0] * (10 ** 6 + 10)
for x in A:
    i = 0
    while x + i <= 10 ** 6 + 10:
        if dp[(x-1)] == 2:
            break
        else:
            dp[(x-1) + i] += 1
            i += x

cnt = 0
for x in A:
    if dp[x-1] == 1:
        cnt += 1

print(cnt)

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

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

B = [0] * (max(A)+1)
C = []
for i in range(n):
    B[A[i]] += 1

C = A[:]
C.sort()
D = [0] * (10**6+5)

ans = 0
for i in range(len(C)):
    
    if D[C[i]] == 0 and B[C[i]] == 1:
        ans += 1
    j = C[i]
    D[j] = 1
    if i==0 or C[i-1] != C[i]:
        while j < len(D):
            D[j] = 1
            j += C[i]
print(ans)

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

m=max(A)

X=[0]*(m+1)

A.sort()

for i in range(n):
    for j in range(A[i]*2,m+1,A[i]):
        X[j]=2
    X[A[i]]+=1


print(X.count(1))

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

m=max(A)

X=[0]*(m+1)

A.sort()

for i in range(n):
    for j in range(A[i],m+1,A[i]):
        X[j]+=1

ans=0

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

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

if __name__ == "__main__":
    main()

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

li = [1]*(max(A)+1)
for j in range(N):
    for i in range(A[j]*2,A[-1]+1,A[j]):
        li[i] = 0

for key,val in cA.items():
    if val >1:
        li[key]=0
        
sA = sum([li[i] for i in A])
print(sA)

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

for i in range(n-1):
    p = a[i]
    if dp[p] == 1:
        for j in range(aMax//p+1):
            dp[p*j] = 0
        if a[i] != a[i+1]:
            ans += 1
if dp[aMax] == 1:
    ans += 1
print(ans)

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

MAX_N = max(A)+ 1
cnt = [0] * MAX_N
for a in A:
    for i in range(a, MAX_N, a):
        if cnt[i] <= 2: 
            cnt[i] += 1
            
ans = 0
for a in A:
    if cnt[a] == 1:
        ans += 1
print(ans)

Solution (Python):
n=int(input())
*l,=map(int, input().split())
solv=0
max=max(l) +1
count=[0 for i in range(max)]
for i in l:
    for j in range(i,max,i):
        count[j] += 1
for k in l:
    if count[k] == 1:
        solv += 1
print(solv)

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
A.sort()
TF={a:True for a in A}
for i in range(N):
    if TF[A[i]]==True:
        if i > 0 and A[i - 1] == A[i]:
            TF[A[i]] = False
        m=A[N-1]//A[i]
        for j in range(2,m+1):
            s=A[i]*j
            if s in TF:
                TF[s]=False
print(len([1 for a in A if TF[a]==True]))

Solution (Python):



def LI():
    return list(map(int,input().split()))
    
n=int(input())
a=LI()
a.sort()
nums=[0]*(10**6+100)
for q in a:
    if nums[q]==0:
        nums[q]=1
        for j in range(2*q,10**6+1,q):
            nums[j]+=9
    elif nums[q]==1:
        nums[q]+=9
        

cnt=0
for i in nums:
    if i==1:
        cnt+=1
print(cnt)

Solution (Python):
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from collections import Counter

n=int(input())
l=lnii()

def eratosthenes(lim):
  num=[1 for i in range(lim)]
  for i in set(l):
    if num[i]:
      for j in range(i+i,lim,i):
        num[j]=0
  return num

lim=10**6+5
num=eratosthenes(lim)

count=Counter(l)

ans=0
for i in l:
  if num[i]==1 and count[i]==1:
    ans+=1

print(ans)

Solution (Python):
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from collections import Counter

n=int(input())
l=lnii()

def eratosthenes(lim):
  num=[1 for i in range(lim)]
  for i in set(l):
    for j in range(i+i,lim,i):
      num[j]=0
  return num

lim=10**6+5
num=eratosthenes(lim)

count=Counter(l)

ans=0
for i in l:
  if num[i]==1 and count[i]==1:
    ans+=1

print(ans)

Solution (Python):
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from collections import Counter

n=int(input())
l=lnii()

def eratosthenes(lim):
  num=[1 for i in range(lim)]
  for i in set(l):
    for j in range(i+i,lim,i):
      num[j]=0
  return num

lim=10**6+5
num=eratosthenes(lim)

count=Counter(l)

ans=0
for i in l:
  if num[i]==1 and count[i]==1:
    ans+=1

print(ans)