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



Sample input:
5
24 11 8 3 16


Sample output:
3

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
m = max(a)
y = [0] * (m + 1)
for i in a:
    x = i
    while x <= m:
        y[x] += 1
        x += i
ans = 0
for j in a:
    if y[j] == 1:
        ans += 1

print(ans)

Submission status: Accepted

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

for i in a:
    dp[i] += 1
    if dp[i] == 1:
        for j in range(i*2,a_max+1,i):
            dp[j] = 2
print(dp.count(1))

Submission status: Accepted

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

max_A = A[-1] + 1
ans = [0] * max_A

for i in A:
    ans[i] += 1
    if ans[i] == 1:
        for j in range(i*2, max_A, i):
            ans[j] = 2

print(ans.count(1))

Submission status: Accepted

Solution code:
#dame datta....
from collections import Counter
def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = sorted(A)
    a = Counter(A)
    l = [0] * (10**6+1)
    v = [0] * (10**6+1)
    for i in B:
        if v[i] == 1 or l[i] == 1:
            continue
        else:
            v[i] = 1
        t = 2*i
        while t < 10**6 + 1:
            l[t] = 1
            t += i
    r = 0
    for i in A:
        if l[i] == 0 and a[i] == 1:
            r += 1
    return r
print(main())

Submission status: Accepted

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

x = max(a)
dp = [0] * (x+1)
for ai in a:
    i = 1
    while i * ai <= x:
        dp[i * ai] += 1
        i += 1

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

print(ans)

Submission status: Accepted

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

A.sort()
chk_list = [0]*(A[-1]+1)

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

for i in A:
    if chk_list[i] == 2:
        continue

    if chk_list[i] == 1:
        chk_list[i] = 2
        continue

    chk_list[i] = 1
    for j in range(i*2, A[-1]+1, i):
        chk_list[j] = 2

print(chk_list.count(1))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

ans = 0
n = int(input())
A = list(map(int,input().split()))
B = [0] * (10**6+3)
ans = 0
A.sort()
for i in range(n):
    if (i == 0 or A[i] != A[i-1]) and (i == n-1 or A[i] != A[i+1]) and B[A[i]] == 0:
        ans += 1
    if (i == 0 or A[i] != A[i-1]):
        m = A[i]
        while m < len(B):
            B[m] = 1
            m += A[i]
print(ans)

Submission status: Accepted

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

x = max(a)
dp = [0] * x
for ai in a:
    i = 1
    while i * ai <= x:
        dp[i * ai - 1] += 1
        i += 1

ans = 0
for ai in a:
    if dp[ai-1] <= 1:
        ans += 1

print(ans)

Submission status: Accepted

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

ans = 0

check = [True] * (10 ** 6 + 1)
for i in range(N):
    a = A[i]
    if not check[a]:
        continue
    if (i >= 1 and A[i] != A[i - 1]) or i == 0:
        tmp = a
        while tmp <= 10 ** 6:
            check[tmp] = False
            tmp += a
    else:
        continue
    if i + 1 < N and A[i] == A[i + 1]:
        continue
    # print (a)
    ans += 1

print (ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
max_A = A[-1] + 1
ans = [0]*max_A
for i in A:
  ans[i] += 1
  if ans[i] == 1:
    for j in range(i*2, max_A, i):
      ans[j] = 2
print(ans.count(1))

Submission status: Accepted

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict

# import fractions

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = sorted(il())

    cnt = collections.Counter(A)
    multiple = set()
    ret = 0
    maximum = max(A)
    for a in A:
        # 約数を既に使用済みの場合はcontinue
        if a in multiple:
            continue

        # 約数がなく、
        # 同じ数字が存在しない場合には
        # 条件に一致する整数
        if cnt[a] == 1:
            ret += 1

        i = 1
        # 整数の倍数を列挙
        while a * i <= maximum:
            multiple.add(a*i)
            i += 1
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding:utf-8
n = int(input())
a = list(map(int, input().split()))
m = max(a)
count = [0 for _ in range(m + 1)]
ans = 0

for i in a:
    if count[i] != 0:
        count[i] = 1
        continue
    for j in range(2 * i, m + 1, i):
        count[j] = 1
    count[i] = 2

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

print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

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

LIM = 10 ** 6 + 1
# LIM = 25

A.sort()
dp = [1] * LIM

for i in set(A):
    s = i * 2
    while s < LIM:
        dp[s] = 0
        s += i

ans = 0
# print(dp)
for a in A:
    # print("{} {}".format(dp[a], cA[a]))
    if dp[a] and cA[a] == 1:
        # print(a)
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
# dp = [0 for _ in range(N)]

# A.sort()

# for i in range(N):
#     if dp[i] < 2:
#         p = A[i]
#         for j in range(N):
#             if dp[j] < 2 and A[j]%p == 0 and A[j] >= p:
#                 dp[j] += 1
# cnt = 0
# for i in range(N):
#     if dp[i] == 1:
#         cnt += 1
M = 10**6  + 5
cnt = [0 for _ in range(M)]
for x in A:
    if cnt[x] != 0:
        cnt[x] = 2
        continue
    i = x
    while i < M:
        cnt[i] += 1
        i += x
ans = 0
for x in A:
    if cnt[x] == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def resolve():
    '''
    code here
    '''
    import collections
    N = int(input())
    A_list = [int(item) for item in input().split()]

    A_list.sort()


    dp = [0 for item in range(A_list[-1]+1)]
    for item in A_list:

        temp = item
        while temp <= A_list[-1]:
            dp[temp] += 1
            temp += item

    cnt = 0
    for item in A_list:
        if dp[item] == 1:
            cnt += 1
    print(cnt)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
amax = a[-1]
flags = [True] * amax

prev = -1

cnt = 0
for idx in range(n):
    i = a[idx]
    if prev == i: continue
    if flags[i-1]: 
        cnt += 1
        if idx < n-1:
            if i == a[idx+1]:
                cnt -= 1
    ax = i + i
    while ax <= amax:
        flags[ax-1] = False
        ax += i
    prev = i
print(cnt)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
dp=[True]*a[-1]
def hantei(i):
    ans = True
    if i!=n-1:
        if a[i]==a[i+1]: ans = False
    if i!=0:
        if a[i]==a[i-1]: ans=False
    return ans
for val in set(a):
    for i in range(2*val,a[-1]+1,val): dp[i-1]=False
ans=0
for i in range(n):
    if dp[a[i]-1] and hantei(i)==1: ans+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
U = 10 ** 6 + 1

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

C = Counter(A)
dp = [0] * U

ans = 0
for k in sorted(C.keys()):
    if dp[k]:
        continue
    if C[k] == 1:
        ans += 1
    for i in range(k, U, k):
        dp[i] = 1

print(ans)

Submission status: Accepted

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n = ii()
a = li()

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

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

single = []
for i in a:
    if cnt[i] == 1:
        single.append(i)

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

for i in unique:
    if st[i] >= 1:
        continue
    j = i*2
    while j <= 10**6:
        st[j] = 1
        j += i

ans = 0
for i in single:
    if st[i] == 0:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
from collections import Counter
c=Counter(a)
f=[1]*(10**6+1)
ans=0
for ai in a:  
  if c[ai]==1 and f[ai]==1:ans+=1
  if f[ai]==1:
    for i in range(ai,10**6+1,ai):
      f[i]=0
print(ans)

Submission status: Accepted

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

    A.sort()
    dict = {}
    for i in range(1,A[N-1]+1):
        dict[i] = 0

    if N == 1:
        return 1

    if A[0] == 1 and A[1] != 1:
        return 1
    elif A[0] == 1 and A[1] == 1:
        return 0

    temp = 1

    for num in A:
        while True:
            if num*temp <= A[N-1]:
                dict[num*temp] += 1
                temp += 1
            else:
                temp = 1
                break

    ans = 0
    for num2 in A:
        if dict[num2] <= 1:
            ans += 1

    return ans


print(main())

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys 
input = sys.stdin.readline

def slove():
    n = int(input())
    A = sorted(list(map(int,input().split())))
    a_max = A[-1]+1
    B = [0] * a_max
    for value in A:
        B[value] += 1
        for i in range(value*2,a_max,value):
            B[i] += 2
    #print(B)
    print(B.count(1))

if __name__ == "__main__":
    slove()

"""
import sys
input = sys.stdin.readline

def slove():
    n = int(input())
    A = list(map(int,input().split()))
    A = sorted(A)
    ans = 0
    flag = False
    while len(A) != 0:
        ans += 1
        tmp = A.pop(0)
        #print(A)
        k = 0
        for i in range(len(A)):
            if A[i-k] % tmp == 0:
                if A[i-k] == tmp:
                    flag = True
                A.remove(A[i-k])
                k += 1
        if flag:
            ans -= 1
            flag = False
        
    print(ans)


if __name__ == "__main__":
    slove()
"""

Submission status: Accepted

Solution code:
from collections import Counter

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

# 同じ値が複数存在するかチェックする用のカウンタ
counter = Counter(A)

# D[a] = True: Aにaより小さいaの約数が存在する
A_max = max(A)
dp = {a: False for a in A}

for a in A:
    # xが数列Aに含まれているとき、aより大きいaの倍数tについて、dp[a * t]をTrueに変更する
    if counter[a] > 0:
        t = 2
        while a * t <= A_max:
            dp[a * t] = True
            t += 1

ans = 0
for a in A:
    if counter[a] == 1 and dp[a] is False:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
def main():
  N=input()
  A=sorted(map(int,input().split()))
  M=A[-1]+1
  B=[True]*M
  c=0
  x=0
  for i in A:
    if B[i]:
      if i!=c:
        for j in range(i*2,M,i):
          B[j]=False
        x+=1
        c=i
      else:
        B[i]=False
        x-=1
  print(x)
main()

Submission status: Accepted

Solution code:
import sys
import heapq
def input(): return sys.stdin.readline().strip()


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

    """
    エラトステネスの篩は脳裏に浮かんだが、
    計算量がO(NloglogN)になる理屈を分かってなかったのを丁度突かれてしまった。
    1,2,3,...に対してそれぞれの倍数が1~Nにどれだけ含まれるかのチェックは
        N + N//2 + N//3 + ... = N (1 + 1/2 + 1/3 + ...) = NlogN
    になるのがミソ。
    さらに1~Nのリストに倍数チェックをつける際に、ある数xの倍数をすべて見るとして
    xのところに既にチェックがあればその先のチェックもすでに終わっているので計算量はさらに減らせる。 
    """

    sieve = [0] * (10**6 + 1)
    for a in A:
        if sieve[a] == 2: continue # 重複がある場合
        if sieve[a] == 1:
            sieve[a] += 1
            continue
        if sieve[a] == 0:
            num = a
            while num <= 10**6:
                sieve[num] += 1
                num += a
    ans = 0
    for a in A:
        if sieve[a] == 1: ans += 1
    print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
Alist = list(map(int,input().split(" ")))
Alist.sort()
Amax = Alist[-1]
dp = [1]*(Amax+1)
count = 0
for i in range(len(Alist)-1):
    p = Alist[i]
    if dp[p] == 1:
        for j in range(Amax//p+1):
            dp[p*j] = 0
        if Alist[i] != Alist[i+1]:
            count+=1
if dp[Amax] == 1:
    count += 1
print(count)

Submission status: Accepted

Solution code:
n = int(input())
a  = list(map(int, input().split()))
a.sort()
dp = [0]*a[n-1]
ans = 0
temp2 = 0
for i in range(n):
  if temp2 == a[i]:
    ans -= 1
    temp2=0
  if dp[a[i]-1] == 0:
    ans += 1
    temp = a[i]
    temp2 = a[i]
    while temp <= a[n-1]:
      dp[temp-1] = 1
      temp = temp+a[i]
  #print(dp)    
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a_max = max(a)
lst = [0] * (a_max + 1)
cnt = 0
for i in a:
    if lst[i] > 1:  # 配列中のカウントが2以上なら以降の処理を省略
        continue
    for j in range(a_max // i + 1):  # Aiの倍数にインクリメント(配列の上限はa[-1])
        lst[i * j] += 1
    # lst[1::i] += 1
for i in a:
    if lst[i] == 1:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import numpy as np

n = int(input())
a = list(map(int, input().split()))
a_max = max(a)
lst = [0] * (a_max + 1)
cnt = 0
# if len(a) <= 1:
#     print(0)
# else:
for i in a:
    if lst[i] > 1:  # 配列中のカウントが2以上なら以降の処理を省略
        continue
    for j in range(a_max // i + 1):  # Aiの倍数にインクリメント(配列の上限はa[-1])
        lst[i * j] += 1
    # lst[1::i] += 1
for i in a:
    if lst[i] == 1:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
A = list(map(int,input().split()))
A.sort()
c = Counter(A)

if c[1]==1:
    print(1)
elif c[1] > 1:
    print(0)
else:
    mx = 10**6+10
    ok = [True]*mx
    ans = 0
    for a in A:
        if ok[a]:
            if c[a] == 1:
                ans += 1
            for i in range(mx):
                if i*a >= mx:
                    break
                ok[i*a] = False
        else:
            continue
    print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

N,*A = map(int, open(0).read().split())
As = sorted(A)
Ac = Counter(A)
m = max(A)
dp = [True] * (m+1)
ans = 0
for x in As:
    if dp[x] == True:
        for i in range(1,m//x+1):
            dp[x*i] = False
        if Ac[x] == 1:
            ans += 1
    else:
        continue
print(ans)

Submission status: Accepted

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

AM=max(A)+1
B=[0]*AM
#Aから要素を取り出す
for i in A:
  #要素 i ごとに、倍数に1を足して行く。この数が、A内の他の要素で割り切れる回数を示すことになる。
  
  for j in range(i,AM,i):
    B[j]+=1
x=0
for i in A:
  if B[i]==1:
    x+=1
    
print(x)

Submission status: Accepted

Solution code:
n = int(input())
A = sorted(list(map(int, input().split())))
from collections import Counter
c = Counter(A)

dp = [1]*(max(A)+1)
#print(dp)
for i in c.keys():
    j = i*2
    while j<len(dp):
        dp[j] = 0
        j += i
        #print(j, end=',')
ans = 0
for i in c.keys():
    if c[i] == 1:
        if dp[i] == 1:
            ans += 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    _ = int(input())
    A = list(map(int, input().split()))

    A.sort()
    a_max = A[-1]
    dp = [0] * (a_max + 1)

    for a in A:
        if dp[a] != 0:
            dp[a] = 2
            continue

        i = a
        while i < a_max + 1:
            dp[i] += 1
            i += a

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

    print(r)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# import collections


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

    A.sort()

    # sames = 0
    # C = collections.Counter(A)
    # for v in C.values():
    #     if v > 1:
    #         sames += 1

    a_max = A[-1]
    dp = [0] * (a_max + 1)
    # dp = [True] * a_max
    # A = set(A)

    for a in A:
        if dp[a] != 0:
            dp[a] = 2
            continue

        i = a
        while i < a_max + 1:
            dp[i] += 1
            i += a

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

    print(r)

    #     if dp[a - 1]:
    #         tmp_a = a * 2
    #         while tmp_a < a_max + 1:
    #             dp[tmp_a - 1] = False
    #             tmp_a += a

    # r = 0
    # for a in A:
    #     if dp[a - 1]:
    #         r += 1

    # print(r - sames)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

def main():
    MOD = 10**9+7
    n = int(input())
    A = list(map(int,input().split()))

    A.sort()
    T = A[-1]+1

    dp = [True] * T

    d = defaultdict(int)

    for a in A:
        d[a] += 1
        if dp[a]:
            for j in range(2*a,T,a):
                dp[j] = False

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

    print(ans)

main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
  N=input()
  A=sorted(map(int,input().split()))
  M=A[-1]+1
  B=[0]*M
  for i in A:
    B[i]+=1
    if B[i]==1:
      for j in range(i*2,M,i):
        B[j]=2
  print(B.count(1))
main()

Submission status: Accepted

Solution code:
T = 10 ** 6 + 20
n = int(input())
a = [int(i) for i in input().split()]
table = [True for _ in range(T)]
a.sort()
ans = 0
for i in range(n):
    if table[a[i]]:
        for j in range(a[i], T, a[i]):
            table[j] = False
        if i + 1 < n:
            if a[i + 1] != a[i]:
                ans += 1
        elif i + 1 == n:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
table = [True for _ in range(2 * (10 ** 6))]
a.sort()
ans = 0
for i in range(n):
    if table[a[i]]:
        for j in range(a[i], 2 * (10 ** 6), a[i]):
            table[j] = False
        if i + 1 < n:
            if a[i + 1] != a[i]:
                ans += 1
        elif i + 1 == n:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
# abc170_d.py
N = int(input())
A = list(map(int,input().split()))
A.sort()
cnt = [0]*(10**6+1)
for i in A:
    if cnt[i]<1:
        multiple = 2
        while i*multiple <= 10**6:
            cnt[multiple*i]+=1
            multiple+=1
    cnt[i]+=1
ans = 0
for i in A:
    if cnt[i]==1:
        ans+=1
print(ans)

Submission status: Accepted

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

Dv = [0]*(A[-1]+1)
Ct = [0]*(A[-1]+1)

for a in A:
  Dv[a] += 1
  Ct[a] += 1
  
for a in A:
  if Dv[a] >= 2:
    Dv[a] = 1
    Ct[a] = 0

for i in range(1,A[-1]+1):
  if Dv[i] == 1:
    for j in range(2,A[-1]+1): 
      if j * i > A[-1]:
        break
      Dv[j*i] = 0
      Ct[j*i] = 0

Ct[0] = 0
ans = sum(Ct)

print(ans)

Submission status: Accepted

Solution code:
import math
from collections import deque
from collections import defaultdict
import itertools as it

#自作関数群
def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	if len(res)==0:
		res = [n]
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):#階乗
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):#コンビネーション
	if n<r:
		return 0
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
def combmod(n,r,mod):
	return (fact(n)/fact(n-r)*pow(fact(r),mod-2,mod))%mod
def printQueue(q):
	r=copyQueue(q)
	ans=[0]*r.qsize()
	for i in range(r.qsize()-1,-1,-1):
		ans[i] = r.get()
	print(ans)
class UnionFind():
	def __init__(self, n):
		self.n = n
		self.parents = [-1]*n

	def find(self, x): # root
		if self.parents[x]<0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self,x,y):
		x = self.find(x)
		y = self.find(y)

		if x==y:
			return

		if self.parents[x]>self.parents[y]:
			x,y = y,x

		self.parents[x]+=self.parents[y]
		self.parents[y]=x

	def size(self,x):
		return -1*self.parents[self.find(x)]

	def same(self,x,y):
		return self.find(x)==self.find(y)

	def members(self,x): # much time
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i)==root]

	def roots(self):
		return [i for i,x in enumerate(self.parents) if x<0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()} # 1~n
def bitArr(n):#ビット全探索
	x = 1
	zero = "0"*n
	ans = []
	ans.append([0]*n)
	for i in range(2**n-1):
		ans.append(list(map(lambda x:int(x),list((zero+bin(x)[2:])[-1*n:]))))
		x+=1
	return ans;
def arrsSum(a1,a2):
	for i in range(len(a1)):
		a1[i]+=a2[i]
	return a1
def maxValue(a,b,v):
	v2 = v
	for i in range(v2,-1,-1):
		for j in range(v2//a+1): #j:aの個数
			k = i-a*j
			if k%b==0:
				return i
	return -1
def copyQueue(q):
	nq = queue.Queue()
	n = q.qsize()
	for i in range(n):
		x = q.get()
		q.put(x)
		nq.put(x)
	return nq
def get_sieve_of_eratosthenes(n):
	data = [2]
	#data = [0,0,0]
	for i in range(3,n+1,2):
		data.append(i)
		data.append(0)
	for i in range(len(data)):
		interval = data[i]
		if interval!=0:
			for j in range(i+interval,n-1,interval):
				data[j] = 0
	ans = [x for x in data if x!=0]
	#ans = data[:]
	return ans

n = readInt()
a = readInts()
a.sort()

max_a = a[-1]
ans = [0]*(max_a+1)

for i in a:
	ans[i]+=1
for i in set(a):
	if ans[i]:
		for j in range(i*2,len(ans),i):
			ans[j]=0

print(ans.count(1))

Submission status: Accepted

Solution code:
import math
from collections import deque
from collections import defaultdict
import itertools as it

#自作関数群
def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	if len(res)==0:
		res = [n]
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):#階乗
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):#コンビネーション
	if n<r:
		return 0
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
def combmod(n,r,mod):
	return (fact(n)/fact(n-r)*pow(fact(r),mod-2,mod))%mod
def printQueue(q):
	r=copyQueue(q)
	ans=[0]*r.qsize()
	for i in range(r.qsize()-1,-1,-1):
		ans[i] = r.get()
	print(ans)
class UnionFind():
	def __init__(self, n):
		self.n = n
		self.parents = [-1]*n

	def find(self, x): # root
		if self.parents[x]<0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self,x,y):
		x = self.find(x)
		y = self.find(y)

		if x==y:
			return

		if self.parents[x]>self.parents[y]:
			x,y = y,x

		self.parents[x]+=self.parents[y]
		self.parents[y]=x

	def size(self,x):
		return -1*self.parents[self.find(x)]

	def same(self,x,y):
		return self.find(x)==self.find(y)

	def members(self,x): # much time
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i)==root]

	def roots(self):
		return [i for i,x in enumerate(self.parents) if x<0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()} # 1~n
def bitArr(n):#ビット全探索
	x = 1
	zero = "0"*n
	ans = []
	ans.append([0]*n)
	for i in range(2**n-1):
		ans.append(list(map(lambda x:int(x),list((zero+bin(x)[2:])[-1*n:]))))
		x+=1
	return ans;
def arrsSum(a1,a2):
	for i in range(len(a1)):
		a1[i]+=a2[i]
	return a1
def maxValue(a,b,v):
	v2 = v
	for i in range(v2,-1,-1):
		for j in range(v2//a+1): #j:aの個数
			k = i-a*j
			if k%b==0:
				return i
	return -1
def copyQueue(q):
	nq = queue.Queue()
	n = q.qsize()
	for i in range(n):
		x = q.get()
		q.put(x)
		nq.put(x)
	return nq
def get_sieve_of_eratosthenes(n):
	data = [2]
	#data = [0,0,0]
	for i in range(3,n+1,2):
		data.append(i)
		data.append(0)
	for i in range(len(data)):
		interval = data[i]
		if interval!=0:
			for j in range(i+interval,n-1,interval):
				data[j] = 0
	ans = [x for x in data if x!=0]
	#ans = data[:]
	return ans

n = readInt()
a = readInts()
a.sort()

#max_a = 10**6
max_a = a[-1]
ans = [0]*(max_a+1)

for i in a:
	if ans[i]!=2:
		ans[i]+=1
for i in set(a):
	if ans[i]:
		for j in range(i*2,len(ans),i):
			ans[j]=0

print(ans.count(1))