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

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

n = ni()
a = na()
a.sort()
cnt = Counter(a)
elem = [True]*(a[-1]+1)

for i in a:
  for j in range(i*2,a[-1]+1,i):
    elem[j] = False
ans = 0
for v in a:
  if elem[v] == True and cnt[v] == 1:
    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):
n = int(input())
a = list(map(int,input().split()))
import collections
c = collections.Counter(a)
a = list(set(a))
n = len(a)
a = sorted(a)
B = [True]*(a[-1]+1)
ans = 0
for i in range(n):
    if B[a[i]]:
        if c[a[i]] == 1:
            ans += 1
        j = 2
        while a[i]*j <= a[-1]:
            B[a[i]*j] = False
            j += 1
print(ans)

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

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












A_set = list(set(A_list))
maxA =  A_set[-1]
dp = [1] * (( 10 ** 6) + 1)

cntli = [0] * (( 10 ** 6) + 1)
unique =[]
for i in A_list:
    cntli[i] += 1
for i in range((( 10 ** 6) + 1)):
    if cntli[i] == 1:
        unique.append(i)

for elem in A_set:
    for i in range(2 * elem,  10 ** 6 + 1, elem):
        dp[i] = 0

ans = 0
for i in unique:
    if not (dp[i] == 0):
        ans += 1

print(ans)

Solution (Python):
import numpy as np


def main():
    input()
    a = [int(i) for i in input().split()]
    a.sort()
    dp = np.zeros(a[-1] + 1, dtype=np.int)
    for ai in a:
        if dp[ai] == 0:
            dp[ai] = 1
            dp[ai * 2:a[-1] + 1:ai] = 2
        else:
            dp[ai] = 2
    
    print(len(dp[dp == 1]))


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
a.sort()
c = [0]*(1000001)
for i in a:
    c[i] += 1
b = list(set(a))
ans = []
b.sort()

num = [True]*(1000001)

for i in range(len(b)):
    now = b[i]
    if num[now]:
        ans.append(now)
        for j in range(now, 1000001, now):
            num[j] = False


count = 0
for i in ans:
    if c[i] == 1:
        count += 1

print(count)

Solution (Python):
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def main():

    N = in_n()
    A = sorted(list(in_nn()))

    maxA = max(A)
    ans = [True] * (maxA + 1)
    d = set()

    for i in range(N):
        if A[i] in d:
            ans[A[i]] = False
        for j in range(A[i] * 2, maxA + 1, A[i]):
            if not j:
                break
            else:
                ans[j] = False
        d |= {A[i]}

    count = 0
    for i in range(N):
        count += ans[A[i]]

    print(count)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    a.sort()
    b = 0
    dp = [True] * (a[-1] + 1)
    for ai in a:
        if not dp[ai]:
            continue
        for j in range(ai * 2, a[-1] + 1, ai):
            dp[j] = False
        if ai == b:
            dp[ai] = False
        b = ai
    print(sum(dp[ai] for ai in a))


if __name__ == '__main__':
    main()

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

max_a = max(a)
flag = [True for i in range(max_a+1)]

dup = set()
for i in range(n):
    if a[i] in dup:
        flag[a[i]] = False
    else:
        dup.add(a[i])
        for j in range(2*a[i], max_a+1, a[i]):
            flag[j] = False

ans = 0
for i in a:
    ans += flag[i]
print(ans)

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

max_a = max(a)
flag = [True for i in range(max_a+1)]

dup = set()
for i in range(n):
    if a[i] in dup:
        flag[a[i]] = False
    else:
        dup.add(a[i])
    for j in range(2*a[i], max_a+1, a[i]):
        flag[j] = False

ans = 0
for i in a:
    ans += flag[i]
print(ans)

Solution (Python):
n = int(input())
A = list(map(int,input().split()))
d = {}
for a in A:
    d.setdefault(a,0)
    d[a] += 1       

A = sorted(set(A))
t = [True] * (10 ** 6 + 1)

for a in A:
    if d[a] > 1:
        t[a] = False
    for i in range(a+a, 10 ** 6 + 1, a):
        t[i] = False
print(sum(1 for a in A if t[a]==True))

Solution (Python):
import sys
from collections import Counter

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    _ = int(rl())
    A = list(map(int, rl().split()))
    
    counter = Counter(A)
    A.sort()
    B = [True] * (10 ** 6 + 1)
    ans = 0
    for ai in A:
        if B[ai]:
            for i in range(ai, 10 ** 6 + 1, ai):
                B[i] = False
            if counter[ai] == 1:
                ans += 1
    print(ans)


if __name__ == '__main__':
    solve()

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

for a in A:
    if cnt[a] != 0:
        cnt[a] += 1
        continue
    for j in range(a, MAX, a):
        cnt[j] += 1
ans = 0
for a in A:
    if cnt[a] == 1:
        ans += 1
print(ans)

Solution (Python):

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

max_a = max( a )

c = {} 
d = {} 
for a_i in a:
    try:
        c[ a_i ] += 1
    except KeyError:
        c[ a_i ] = 1
        d[ a_i ] = False 

for a_i in a:
    if c[ a_i ] > 0:
        tmp = 2 * a_i
        while tmp <= max_a:
            d[ tmp ] = True
            tmp += a_i

ans = 0
for a_i in a:
    if c[ a_i ] == 1 and d[ a_i ] == False:
        ans += 1

print( ans )

Solution (Python):
import sys
import heapq
from collections import Counter
from math import sqrt

n = int(input())
a_s = [int(i) for i in sys.stdin.readline().split()]
a_s.sort()
_max = max(a_s)
ct = Counter(a_s)
cnt = 0
ls = [False] * (10**6+1)
for a in a_s:
    if ls[a]:
        cnt += 1
        continue
    elif ct[a] > 1:
        cnt += 1
    for i in range(a, _max+1, a):
        if ls[i]:
            continue
        if i % a == 0:
            ls[i] = True

print(n - cnt)

Solution (Python):

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


max_a = a[-1]
b = [0] * (max_a + 1)
ans = set()
for i in a:
    if b[i] == 1:
        if i in ans:
            ans.remove(i)
        continue
    
    for j in range(i, max_a+1, i):
            b[j] = 1
    ans.add(i)

print(len(ans))

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
A.sort()
Amax = A[-1]
dp = [1]*(Amax+1)
ans = 0
for i in range(len(A)-1):
  p = A[i]
  if dp[p] == 1:
    for q in range(Amax//p+1):
      dp[p*q] = 0
    if A[i] != A[i+1]: 
      ans += 1
if dp[Amax] == 1:
  ans += 1
print(ans)

Solution (Python):
from collections import Counter

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

max_ = 10 ** 6 + 1
b = [True] * (max_ + 1)
data.sort()
c = Counter(data)

ans = 0
for d in data:
    if b[d]:
        for j in range(d, max_, d):
            b[j] = False
        
        if c[d] == 1:
            ans += 1

print(ans)

Solution (Python):
from collections import Counter

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

max_ = 10 ** 6 + 1
b = [True] * (max_ + 1)
data.sort()
c = Counter(data)

ans = 0
for d in data:
    if b[d]:
        for j in range(d, max_, d):
            b[j] = False
        
        if c[d] > 1:
            continue
        else:
            ans += 1

print(ans)

Solution (Python):



n = int(input().rstrip("\n"))
a = [int(_) for _ in input().rstrip("\n").split(" ")]
a.sort()
from collections import defaultdict

counter = defaultdict(int)

limit = 10 ** 6
for num in a:
  counter[num] += 1
  if counter[num] >= 2:
    continue
  current = num
  while current <= limit:
    current += num
    counter[current] += 1

answer = 0
for num in a:
  if counter[num] == 1:
    answer += 1


print(answer)

Solution (Python):
n=int(input())
a=sorted(list(map(int,input().split())))
d=[1]*(a[-1]+1)
for i in a:
  if d[i]==1:
    for j in range(a[-1]//i):
      d[i*(j+1)]=0
    d[i]=1
dic={}
for i in a:
  if i not in dic:
    dic[i]=1
  else:
    d[i]=0
ans=0
for i in a:
  if d[i]==1:
    ans+=1
print(ans)

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

d = {}
for a in A:
    d.setdefault(a, 0)
    d[a] += 1

A = sorted(set(A))
t = [True] * (10 ** 6 + 1)
for a in A:
    if d[a] > 1:
        t[a] = False
    for i in range(a + a, 10 ** 6 + 1, a):
        t[i] = False
print(sum(1 for a in A if t[a]))

Solution (Python):

def main():
    import sys
    imput = sys.stdin.readline
    
    
    
    N = int(input())
    A = list(map(int, input().split()))

    
    from collections import Counter
    M = max(A) + 1
    B = [True] * (M+1)
    A = sorted(A)
    C = Counter(A)

    answer = 0
    for a in A:
        if B[a]:
            for j in range(a, M, a):
                B[j] = False
            if C[a] > 1:
                continue
            else:
                answer += 1

    print(answer)

    
if __name__ == "__main__":
    main()

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

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

for elem in a:
    cnt[elem] += 1

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

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

for elem in a:
    for m in range(elem*2,10**6+1,elem):
        cnt[m] = 1

ans = 0
for elem in unique:
    if cnt[elem] == 0:
        ans += 1

print(ans)

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


n = int(input())
A = list(map(int, input().split()))
A.sort()
is_divisible = np.zeros(10**6+1, dtype=np.int64)


def update(num):
    nums = np.arange(num, 10**6+1, num)
    is_divisible[nums] = True

counter = Counter(A)
ans = 0
for a, count in counter.items():
    if count == 1 and not is_divisible[a]:
        ans += 1
        
    update(a)

print(ans)

Solution (Python):





import math
import sys
import bisect
import heapq  
import collections
from collections import deque
import pprint

inf = 10**18
mod = 10**9+7

n = int(input())
a = list(map(int, input().split()))
a.sort()
if n == 1:
    print(1)
    sys.exit()
if n == 2:
    if a[0] == a[1]:
        print(0)
    elif a[1]%a[0] == 0:
        print(1)
    else:
        print(2)
    sys.exit()

b = []
pre = a[0]
if a[0] != a[1]:
    if pre == 1:
        print(1)
        sys.exit()
else:
    if pre == 1:
        print(0)
        sys.exit()

judge = [False for i in range(10**6+1)]
for num in a:
    judge[num] = True
for i in range(1,(10**6)):
    if judge[i]:
        for j in range(i*2,10**6+1,i):
            judge[j] = False
ans = 0
for i in range(1,10**6+1):
    if judge[i]:
        ans+=1
subans = 0
c = collections.Counter(a)
for k,v in c.items():
    if v > 1 and judge[k]:
        subans+=1
print(ans-subans)

Solution (Python):
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

n = int(readline())
a = np.array(read().split(), np.int32)

b = np.zeros(10**6 + 10, np.int32)
cnt = 0

for x in a:
    if b[x] > 1:
        continue
    b[::x] += 1

for x in a:
    if b[x] == 1:
        cnt += 1

print(cnt)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
a.sort()
l = [True] * (10**6 + 1)
cnt = 0
for i in range(n):
  d = a[i]
  if l[d]:
    if i < n-1 and a[i] != a[i+1]:
      cnt += 1
    elif i == n-1:
      cnt += 1
    for j in range(d, 10**6 + 1, d):
      l[j] = False
print(cnt)

Solution (Python):

def main():
    import sys
    imput = sys.stdin.readline
    
    
    
    N = int(input())
    A = list(map(int, input().split()))

    
    from collections import Counter
    M = max(A) + 1
    B = [True] * (M+1)
    A = sorted(A)
    C = Counter(A)

    answer = 0
    for a in A:
        if B[a]:
            for j in range(a, M, a):
                B[j] = False
            if C[a] > 1:
                continue
            else:
                answer += 1

    print(answer)

    
if __name__ == "__main__":
    main()

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


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)

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


def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    max = A[-1]
    count = Counter(A)
    S = list(count.keys())
    C = []
    for s in S:
        if count[s] > 1:
            continue
        else:
            C.append(s)

    is_prime = np.ones(max + 1, np.bool)
    for a in A:
        if is_prime[a]:
            is_prime[a * 2 :: a] = 0
        else:
            continue
    answer = 0
    for c in C:
        if is_prime[c]:
            answer += 1
        else:
            continue
    print(answer)


if __name__ == "__main__":
    main()

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

a=[0]*((10**6)+1)
for i in L:
    a[i]+=1

uni=[]
for i in range((10**6)+1):
    if a[i]==1:
        uni.append(i)
a=[0]*((10**6)+1)
L=list(set(L))
for i in L:
    for m in range(i*2,(10**6)+1,i):
        a[m]=1
ans=0
for i in uni:
    if a[i]==0:
        ans+=1 
print(ans)

Solution (Python):
import collections
N = int(input())
A = list(map(int,input().split()))
S = set()
D = set()
for a in A:
    if a in S:
        D.add(a)
    else:
        S.add(a)
M = max(S)
A = [0]*(M+1)
for s in S:
    if s in D:
        A[s] += 1
    for i in range(2*s,M+1,s):
        A[i]+=1
count = 0
for s in S:
    if A[s]==0:
        count += 1
print(count)

Solution (Python):

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

temp = [0] * (10 ** 6 + 1)
for i in A:
    j = i
    while j <= A[-1]:
        temp[j] += 1
        j += i

result = 0
for i in A:
    if temp[i] == 1:
        result += 1

print(result)

Solution (Python):
import sys
from collections import Counter

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = list(map(int, input().split()))
    c = Counter(A)
    c = sorted(c.items(), key=lambda x: x[0])
    ans = 0
    isOK = [True] * (10 ** 6 + 1)
    for k, v in c:
        if not isOK[k]:
            continue

        if v > 1:
            for i in range(k, 10 ** 6 + 1, k):
                isOK[i] = False
            continue

        ans += 1
        for i in range(2 * k, 10 ** 6 + 1, k):
            isOK[i] = False

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
N=int(input())
A=list(map(int, input().split()))
A=sorted(A)
D=[1]*(A[-1]+1)
for i in A:
  if D[i]==1:
    for j in range(A[-1]//i):
      D[i*(j+1)]=0
    D[i]=1
dic={}
for i in A:
  if i not in dic:
    dic[i]=1
  else:
    D[i]=0
ans=0
for i in A:
  if D[i]==1:
    ans+=1
print(ans)

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

Solution (Python):
M = int(input())
A=list(map(int,input().split()))
A.sort()
ma=A[-1]
is_prime = [True] * (ma + 1)
for i in A:
    if not is_prime[i]:
        continue
    for j in range(i * 2, ma + 1, i):
        is_prime[j] = False
k=[i for i in range(ma + 1) if is_prime[i]]
N=[]
if len(A)==1:
    print(1)
else:
    if A[0] !=A[1]:
        N.append(A[0])
    for i in range(1,len(A)-1):
        if A[i-1]!=A[i] and A[i]!=A[i+1]:
            N.append(A[i])
    if A[len(A)-2] != A[len(A)-1]:
        N.append(A[len(A)-1])
    s=set(k) & set(N)
    print(len(s))

Solution (Python):
M = int(input())
A=list(map(int,input().split()))
A.sort()
ma=A[-1]
is_prime = [True] * (ma + 1)
for i in A:
    if not is_prime[i]:
        continue
    for j in range(i * 2, ma + 1, i):
        is_prime[j] = False
k=[i for i in range(ma + 1) if is_prime[i]]
N=[]
if len(A)==1:
    print(1)
else:
    if A[0] !=A[1]:
        N.append(A[0])
    for i in range(1,len(A)-1):
        if A[i-1]!=A[i] and A[i]!=A[i+1]:
            N.append(A[i])
    if A[len(A)-2] != A[len(A)-1]:
        N.append(A[len(A)-1])
    s=set(k) & set(N)
    print(len(s))

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
visited=[False for i in range(10**6+1)]
ban=[False for i in range(10**6+1)]
from collections import Counter
A.sort()
D=dict(Counter(A))
for n in A:
    if visited[n]==False:
        visited[n]=True
        for j in range(2,10**6):
            if 10**6<n*j:
                break 
            ban[n*j]=True
ans=0
for n in A:
    if D[n]==1 and ban[n]==False:
        ans+=1
print(ans)

Solution (Python):
from collections import Counter

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

MAX = 10 ** 6 + 10
multiples = [0] * MAX

for a in list(set(A)):
    for j in range(a * 2, MAX, a):
        multiples[j] = 1

d = Counter(A)
dup = [k for k, v in d.items() if v > 1]
for i in dup:
    multiples[i] = 1

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

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
A.sort()
used = [0 for _ in range(int(1e6+1))]

ans = 0
for i in A:
    if used[i] > 0:
        used[i] += 1
        continue
    for j in range(i, len(used), i):
        used[j] += 1
for a in A:
    if used[a] == 1:
        ans += 1
print(ans)

Solution (Python):
import sys

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

done=[0 for i in range(max_val)]
cnt=0
ans=0

for i in a:

  if 1<=done[i-1]:
    done[i-1]+=1
    continue

  done[i-1]+=1
  cnt=1
  while(i*cnt<=max_val):
    cnt+=1
    if cnt*i<=max_val:
      done[cnt*i-1]+=1

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

print(ans)

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

for ll in l:
  for i in range(ll,m+1,ll):
    check[i]+=2
  check[ll]-=1
print(check.count(1))

Solution (Python):
import sys

n=int(input())
a=[int(x) for x in input().rstrip().split()]
a.sort()
max_val=max(a)
dp=[True for i in range(max_val)]
done=[0 for i in range(max_val)]
cnt=0
ans=0

for i in a:

  if 1<=done[i-1]:
    done[i-1]+=1
    continue

  done[i-1]+=1
  cnt=1
  while(i*cnt<=max_val):
    cnt+=1
    if cnt*i<=max_val:
      done[cnt*i-1]+=1

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

print(ans)

Solution (Python):
N = 5
ARR = [24, 11, 8, 3, 16]

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

def calculate(n, arr):
    maxValue = max(arr) + 1
    maxValue = 1000006
    krr = [0 for i in range(maxValue)]

    for start in arr:
        if krr[start] > 0:
            krr[start] = 2
            continue

        for i in range(start, maxValue, start):
            krr[i] += 1

    result = 0
    for ar in arr:
        if krr[ar] == 1:
            result = result + 1

    print(result)


calculate(N, ARR)

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

C = {a:0 for a in A}
D = {a:0 for a in A}
for a in A:
    C[a] += 1
for a in A:
    if C[a] > 0:
        t = 2
        while a*t <= maxA:
            D[a*t] = 1
            t += 1
ans = 0
for a in A:
    if C[a] == 1 and D[a] == 0:
        ans += 1
print(ans)

Solution (Python):
n,*a=map(int,open(0).read().split())

ma=1001001
nums=[0]*ma

for i in a:
    nums[i]+=1
    if nums[i]==1: 
        for j in range(i+i,ma,i):
            nums[j]+=2
            
ans=nums.count(1)
print(ans)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")


def solve():
    n = II()
    a = LI()
    dp = [True] * (10 ** 6 + 1)
    a.sort()
    ans = 0
    d = defaultdict(int)
    for i in a:
        if d[i]:
            d[i] = 0
            ans -= 1
        if dp[i]:
            d[i] = 1
            ans += 1
            dp[i] = False

            for j in range(i * 2, 10 ** 6 + 1, i):
                dp[j] = False
    print(ans)
    return



if __name__ == '__main__':
    solve()

Solution (Python):

"""
Created on Sun Jun 14 21:14:26 2020

@author: NEC-PCuser
"""

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

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

for i in A:
    first_flg = True
    for j in range(i, 10 ** 6 + 1, i):
        if first_flg == True and a[j - 1] != 0:
            a[j - 1] += 1
            break
        a[j - 1] += 1
        first_flg = False


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

print(count)

Solution (Python):
import numpy as np
N = int(input())
A = list(map(int,input().split()))
aa = sorted(A)
ans = [0 for i in range(aa[-1]+1)]
for i in aa:
  ans[i] += 1
  if ans[i] == 1:
    for j in range(i*2,aa[-1]+1,i):
      ans[j] += 2
print(ans.count(1))

Solution (Python):
import collections
n = int(input())
a_list = list(map(int, input().split()))
a_dict = dict(collections.Counter(a_list))
sorted_dict = sorted(a_dict.items(), key=lambda x:x[0])
a_set = set(a_list)
m = max(a_list)
for key, count in sorted_dict:
    if  key in a_set:
        j = key * 2
        while j <= m:
            a_set.discard(j)
            j += key
    if count > 1:
        a_set.discard(key)

print(len(a_set))

Solution (Python):
def main():
    n, *a = map(int, open(0).read().split())
    if n == 1:
        print(1)
        return

    m = max(a) + 1
    l = [0] * m
    for i in a:
        for j in range(i, m, i):
            l[j] += 2
        l[i] -= 1

    ans = sum(l[i] == 1 for i in a)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
def main():
    n, *a = map(int, open(0).read().split())
    if n == 1:
        print(1)
        return

    m = max(a) + 1
    l = [0] * m
    for i in a:
        for j in range(i, m, i):
            l[j] += 2
        l[i] -= 1

    ans = l.count(1)
    print(ans)


if __name__ == "__main__":
    main()

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

for i in a:
    cnt[i] += 1
    
unique = []

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

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

a = list(set(a))

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

for i in unique:
    if cnt[i] == 0:
        ans += 1
        
print(ans)

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

amax = max(A)
sieve = [False] * (amax+1)
exist = [0] * (amax+1)

for a in A:
    if exist[a] > 0:
        exist[a] += 1
        continue
    exist[a] += 1
    for i in range(a*2, amax+1, a):
        sieve[i] = True

ans = 0
for a in A:
    if not sieve[a] and exist[a] == 1:
        ans += 1

print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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

    A.sort()

    ma = A[-1]
    B = [0] * (ma + 1)

    ans = set()
    for a in A:
        if B[a] == 1:
            if a in ans:
                ans.remove(a)
            continue
        for aa in range(a, ma + 1, a):
            B[aa] = 1

        ans.add(a)

    print(len(ans))


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
cnt = 0
max = int(10e5+1)
l = [0] * (max+1)
for n in A:
    if l[n] != 0:
        l[n] = 2
        continue
    for j in range(n, max+1, n):
        l[j] += 1
for n in A:
    if l[n] == 1:
        cnt += 1
print(cnt)

Solution (Python):
import math
n = int(input())
a = [int(i) for i in input().split()]

a.sort()
b = [0 for _ in range(a[-1])]
c = 0
for i in a:
    x = i-1
    while len(b) > x:
        b[x] += 1
        x += i 
for i in a:
    if b[i-1] == 1:
        c += 1
print(c)

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):
M=10**7
_,*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()))
maxa = max(a)

d = {}
for ai in a:
  if ai in d:
    d[ai] += 1
  else:
    d[ai] = 1
d = sorted(d.items())


e = [True for _ in range(maxa+1)]
for ai,c in d:
  if c > 1:
    e[ai] = False
  for i in range(2,maxa//ai+1):
    e[ai*i] = False

ans = 0
for ai,_ in d:
  if e[ai]:
    ans += 1
print(ans)

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

from collections import Counter
c=Counter(a)

max_a=max(a)
bls=[0]*(max_a+1)
for a_i in a:
    for j in range(a_i, max_a+1, a_i):
        bls[j]+=1
ans=0
for a_i in a:
    if bls[a_i]==1 and c[a_i]==1:
        ans+=1
print(ans)

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

A.sort()

m_a = max(A)
check = [0]*(m_a+2)

for i in A:
    check[i]+=1
    if check[i]==1:
        for j in range(i*2,m_a+1,i):
            check[j]+=100

print(check.count(1))

Solution (Python):

import copy
import random
import bisect 
import fractions 
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) 

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N = int(input())
A = LI()

A.sort()
table = [0 for i in range(10**6 + 1)] 

cc = collections.Counter(A)


cnt = 0
for a in A:
    if table[a] == 0:
        for i in range(10 ** 6):
            if a * i > 10 ** 6:
                break
            table[a * i] = 1
        if cc[a] == 1:
            cnt += 1


print(cnt)

Solution (Python):
n = int(input())
A = sorted(map(int, input().split()))
nux = A[-1]+1
ans = 0
table = [True]*nux
for i, s in enumerate(A):
    if table[s] == False:
        continue
    if i == n-1:
        ans += 1
    elif A[i+1] != s:
        ans += 1
    b = 1
    while b*s < nux:
        table[b*s] = False
        b += 1
print(ans)

Solution (Python):

N=int(input())
A=list(map(int,input().split()))
dp=[False]*(10**6+1)
A.sort()
ans=0
before_ = -1
for i in A:
  if dp[i]==False:
    for j in range(2*i,10**6+1,i):
      dp[j]=True
  if before_ == i:
      dp[i]=True
  before_=i

for i in A:
  if dp[i]==False:
    ans+=1
print(ans)

Solution (Python):
import sys
from collections import Counter
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    dup = set()
    for k, v in D.items():
        if v > 1:
            dup.add(k)

    judge = [False] * (A[-1] + 1)
    res = 0
    for a in A:
        if judge[a]:
            continue
        else:
            if a not in dup:
                res += 1
            for i in range(a, A[-1] + 1, a):
                judge[i] = True

    print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):
n = int(input())
a_list = list(map(int, input().split()))
a_set = set(a_list)
m = max(a_list)
a_list.sort()
 
pre_a = 0
for a in a_list:
    if a == pre_a:
        a_set.discard(a)
    if a in a_set:
        j = a * 2
        while j <= m:
            a_set.discard(j)
            j += a
    pre_a = a

print(len(a_set))

Solution (Python):
n = int(input())
A = list(map(int, input().split()))
nux = max(A)
B = set(A)
A.sort()
ans = 0
table = [True]*(nux+1)
for ii, s in enumerate(A):
    if table[s] == False:
        continue
    if ii == n-1:
        ans += 1
    elif A[ii+1] != s:
        ans += 1
    i = 1
    while i*s <= nux:
        table[i*s] = False
        i += 1

print(ans)

Solution (Python):
N = int(input())
a = list(map(int, input().split()))
a.sort()
A = max(a)
b = [0]*A
for i in range(N):
  if b[a[i]-1] == 0:
    for j in range(a[i], A+1, a[i]):
      b[j-1] += 1
  elif b[a[i]-1] == 1:
      b[a[i]-1] += 1
n = 0      
for i in range(N):
  if b[a[i]-1] == 1:
    n += 1
print(n)

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

M = 10**6+1
cnt = [0]*M
ans = 0
for a in A:
    if cnt[a] != 0:
        cnt[a] = 2
    else:
        for i in range(a, M, a):
            cnt[i] += 1
for a in A:
    if cnt[a] == 1:
        ans += 1
print(ans)

Solution (Python):
n=int(input())
a=[int(x) for x in input().split()]
a.sort()
m=a[-1]
b=[1]*(m+1)
b[0]=0
p=0
q=1
r=0
for c in range(m+n):
    if p>=n or q>m:
        break
    if a[p]>q:
        if r!=q:
            b[q]=0
        q+=1
        continue
    elif a[p]<q:
        p+=1
        continue
    else:
        p+=1
        if r==q:
            b[q]=0
            continue
        for d in range(2,m//q+1):
            b[d*q]=0
        r=q
print(sum(b))

Solution (Python):
def d170(n,a):
    k=max(a)+1
    count=0
    dp=[0 for i in range(k)]
    for x in a:
        if dp[x]!=0:
                dp[x]=2
                
        else:
            for j in range(x,k,x):
                     dp[j]+=1
    for x in a:
        if dp[x]==1:
            count+=1
    return count
    
n=int(input())
a=list(map(int, input().split()))    
print(d170(n,a))

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
M = max(A)+1
cnt = [0]*M
ans = 0
for a in A:
    if cnt[a] != 0:
        cnt[a] = 2
    else:
        for i in range(a, M, a):
            cnt[i] += 1
for a in A:
    if cnt[a] == 1:
        ans += 1
print(ans)

Solution (Python):
import numpy as np

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

flgs = np.full(10**6+1, False)
flgs[As] = True

for i, A in enumerate(As):
    if flgs[A] == True:
        flgs[::A] = False
        if i+1 == len(As) or As[i+1] != A:
            flgs[A] = True

print(np.count_nonzero(flgs))

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