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:
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy

if __name__ == "__main__":
    n = int(input())
    a = sorted(list(map(int,input().split())))
    M = 1000005
    m = max(a)
    dp = [0]*(m+1)
    for i in range(n):
        if dp[a[i]] != 0:
            dp[a[i]] = 2
            continue
        for j in range(a[i],m+1,a[i]):
            dp[j]+=1
    cnt = 0
    for i in range(n):
        if dp[a[i]] == 1:
            cnt+=1
    print(cnt)

Submission status: Accepted

Solution code:
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy

if __name__ == "__main__":
    n = int(input())
    a = sorted(list(map(int,input().split())))
    M = 1000005
    dp = [0]*(M)
    for i in range(n):
        if dp[a[i]] != 0:
            dp[a[i]] = 2
            continue
        for j in range(a[i],M,a[i]):
            dp[j]+=1
    cnt = 0
    for i in range(n):
        if dp[a[i]] == 1:
            cnt+=1
    print(cnt)

Submission status: Accepted

Solution code:
N = 1000001
a = [0]* N
_, s = open(0)
for x in s.split():
  a[int(x)] += 1
for i in range(1, N):
  if a[i]:
    for j in range(i + i, N, i):
      a[j] = 0
print(a.count(1))

Submission status: Accepted

Solution code:
N = 1000001
a = [0]* N
_, s = open(0)
for x in s.split():
  a[int(x)] += 1
for i in range(1, N):
  for j in range(i + i, N, i):
    if a[i]:
      a[j] = 0
print(a.count(1))

Submission status: Accepted

Solution code:
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
import math

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())
rlf = lambda: map(float, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def main():
	n = int(rl())
	A = list(rli())
	indices = defaultdict(lambda: [])
	Amax = NINF
	if 1 in indices:
		print(1 if len(indices[1]) == 1 else 0)
		return
	A.sort()	
	for i, num in enumerate(A):
		indices[num].append(i)
		Amax = max(Amax, num)
	set_false = set()
	dp = [1 for _ in range(n)]
	for i, num in enumerate(A):
		if i in set_false: continue
		if len(indices[num]) > 1:
			dp[i] = 0
		curr = num
		while curr <= Amax:
			for j in indices[curr]:
				if i == j: continue
				dp[j] = 0
				set_false.add(j)
			curr += num
	print(sum(dp))
	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = [int(v) for v in input().split()]
 
M = max(a)
d = [1 for i in range(M+1)]
for v in sorted(a):
    for j in range(2*v, M+1, v):
        d[j] = 0
ans = 0
c = Counter(a)
for i in a:
    if c[i]==1:
      ans += d[i]
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
arr = list(map(int, input().split()))
arr.sort()
ma = max(arr)
check = [True]*(ma+1)
cnt = [0]*(ma+1)
for i in arr:
    cnt[i] += 1
ans = 0
for i in arr:
    if not check[i]:
        continue
    for k in range(i,ma+1,i):
        check[k] = False
    if cnt[i] <= 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin,stdout
from collections import Counter
n=int(stdin.readline())
a=sorted(map(int,stdin.readline().split()))
d=Counter(a)
m1=max(a);ans=0
vis=[0]*(m1+1)
for v in a:
    if not vis[v]:
        if d[v]==1:ans+=1
        for mul in range(v,m1+1,v):
            vis[mul]=1
stdout.write(str(ans))

Submission status: Accepted

Solution code:
c=[0]*8**7
for a in[*open(0)][1].split():c[int(a)]+=1
i=r=0
for t in c:
 if t:c[::i]=[0]*-(-8**7//i)
 i+=1;r+=t==1
print(r)

Submission status: Accepted

Solution code:
c=[0]*8**7
for a in[*open(0)][1].split():c[int(a)]+=1
i=r=0
for t in c:
 r+=t==1
 if t:c[::i]=[0]*-(-8**7//i)
 i+=1
print(r)

Submission status: Accepted

Solution code:
m=8**7
c=[0]*m
for a in[*open(0)][1].split():c[int(a)]+=1
i=r=0
while~i+m:
 i+=1;r+=c[i]==1
 if c[i]:c[::i]=[0]*-(-m//i)
print(r)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
ans = 0
a.sort()
amax = a[-1]
dp = [1]*(amax+1)
for i in range(len(a)-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)

Submission status: Accepted

Solution code:
from collections import Counter
import math

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

a.sort()

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

is_prime[0] = False

maxA = max(a)

for i in set(a):
    for j in range(2 * i, maxA+1, i):
        is_prime[j] = False

result = 0
c = Counter(a)

for e in set(a):
        if is_prime[e] and c[e] == 1:
    #        print('e = {}'.format(e))
             result += 1

print(result)

Submission status: Accepted

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

m=1000000
c=[0]*(m+1)

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

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

Submission status: Accepted

Solution code:
_,*l=map(int,open(0).read().split())
a=[0]*6**8
for i in l:
  if a[i]<1:
    for j in range(i*2,6**8,i): a[j]=2
  a[i]+=1
print(a.count(1))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

from itertools import count
from collections import Counter

def test():
    n = int(input())
    a = sorted([int(i) for i in input().split()])
    mxn = a[-1]
    c = Counter(a)
    a = sorted(list(set(a)))
    r = dict()
    for i in a:
        for j in count(1):
            if i * j > mxn: break
            r[i * j] = r.get(i * j, 0) + 1
    print(len([k for k in a if r[k] == 1 and c[k] == 1]))


test()

Submission status: Accepted

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

dic = {}
dup = set()
for a in A:
    if a in dic:
        dic[a] += 1
        dup.add(a)
    else:
        dic[a] = 1

A_max = max(A)
A_set = set(dic.keys())

cnt = 0
for a in A:
    if a not in A_set:
        continue

    cnt1 = 2
    x = a * cnt1
    while x <= A_max:
        if x in A_set:
            A_set.remove(x)

        cnt1 += 1
        x = a * cnt1

A_set = A_set - dup

print(len(A_set))

Submission status: Accepted

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

Submission status: Accepted

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

dic = {}
dup = set()
for a in A:
    if a in dic:
        dic[a] += 1
        dup.add(a)
    else:
        dic[a] = 1

A_max = max(A)
A.sort()
A_set = set(dic.keys())

cnt = 0
for a in A:
    if a not in A_set:
        continue

    cnt1 = 2
    x = a * cnt1

    while x <= A_max:
        if x in A_set:
            A_set.remove(x)

        cnt1 += 1
        x = a * cnt1


A_set = A_set - dup

print(len(A_set))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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 i in range(elem*2,(10**6)+1,elem):
        cnt[i]+=1

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

print(ans)

Submission status: Accepted

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

D = [0]*(10**6+1)
for i in A:
    # ダブってる値は2以上に
    D[i] += 1

U = []
for i in range(10**6+1):
    # ダブってる値は2以上に
    if D[i] == 1:
        U.append(i)

A = list(set(A))

T = [0]*(10**6+1)
for i in A:
    # iの2以上の倍数の値は1に
    for j in range(2*i, 10**6+1, i):
        T[j] = 1

# Tが0かつDが1の数を数える
ans = 0
for i in U:
    if T[i] == 0:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
from collections import Counter
import bisect
N = int(input())
A = list(map(int,input().split()))
cnt = Counter(A)
A.sort()
ans = 0
MX = 10**6
P = [0] * (MX+1)
for a in A:
    if P[a]==0:
        for i in range(MX+1):
            x = a*i
            if x > MX:
                break
            P[x] = 1
        if cnt[a]==1:
            ans+=1
print (ans)

Submission status: Accepted

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

dp = [0] * (mx+1)
for i in a:
    if dp[i] == 1:
        continue
    j = 2
    while i * j <= mx:
        dp[i*j] = 1
        j += 1

cnt = 0
for i in set(a):
    if dp[i] == 0 and c[i] == 1:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = [int(v) for v in input().split()]

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

ans = 0
c = Counter(A)
for a in A:
    if c[a] > 1:continue
    ans += l[a]
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

N, *A = map(int, open(0).read().split())

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

dp = Counter()
for a in A:
    dp[a] += 1
    if dp[a] == 1:
        dp.update({k : 2 for k in range(2 * a, lim, a)})

print(len([0 for k, v in dp.items() if v == 1]))

Submission status: Accepted

Solution code:

2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

	

from collections import Counter
import bisect
N = int(input())
A = list(map(int,input().split()))
cnt = Counter(A)
A.sort()
ans = 0
MX = 10**6
P = [0] * (MX+1)
for a in A:
    if P[a]==0:
        for i in range(MX+1):
            x = a*i
            if x > MX:
                break
            P[x] = 1
        if cnt[a]==1:
            ans+=1
print (ans)

Submission status: Accepted

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

    A_dict = {}
    for a in A:
        if a in A_dict.keys():
            A_dict[a] += 1
        else:
            A_dict[a] = 1

    A_list = sorted(A_dict.keys())
    limit = A_list[-1]

    sieve = {i: True for i in A_dict.keys()}

    for a in A_list:
        if not sieve[a]:
            continue
        for i in range(2*a, limit+1, a):
            if i in sieve:
                sieve[i] = False

    print(sum([1 for i in sieve.keys() if sieve[i] and (A_dict[i]==1)]))
main()

Submission status: Accepted

Solution code:
N, *A = map(int, open(0).read().split())

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

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

print(dp.count(1))

Submission status: Accepted

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

M = 10**6+5

count = [0]*M

for x in range(n):
    if count[a[x]] != 0:
        count[a[x]] = 2
        continue

    for i in range(a[x], M, a[x]):
        count[i] += 1

ans = 0
for x in range(n):
    if count[a[x]] == 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = sorted(int(a) for a in input().split())

# エラトステネスの篩
max_A = A[-1]
search_list = [True for _ in range(max_A)]

count = 0
for i, a in enumerate(A):
    if not search_list[a - 1]:
        continue
    for j in range(a, max_A + 1, a):
        search_list[j - 1] = False
    if i < N - 1 and A[i + 1] == a:
        continue
    count += 1

print(count)

Submission status: Accepted

Solution code:
from collections import Counter

N, *A = map(int, open(0).read().split())

C = Counter(A)
B = sorted(C.items(), key=lambda x: x[0])

lim = B[-1][0] + 1

memo = set()
ans = 0
for k, v in B:
    if k in memo:
        continue
    memo |= set(range(k, lim, k))
    ans += (v == 1)

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

# new = [key for key, val in Counter(a).most_common() if val == 1]
prime = [1] * 1000010

for i in set(a):
    # if prime[i]:
    for j in range(i + i, 1000001, i):
        prime[j] = 0

c = Counter(a)
ans = 0
for i in a:
    if prime[i] and c[i] == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = sorted(list(map(int, input().split())))
M = A[-1]
b = [True]*(M + 1)

count = 0
for i, a in enumerate(A):
    if not b[a]:
        continue
    for j in range(a, M+1, a):
        b[j] = False
    if i < N-1 and A[i+1] == a:
        continue
    count += 1

print(count)

Submission status: Accepted

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

l=[0]*(1000005)
for i in range(n):
    if l[a[i]]==1:
        l[a[i]]+=1

    if l[a[i]]==0:
        for j in range(1000000//a[i]+1):
            l[a[i]*j]+=1
    
cnt=0
for i in range(n):
    if l[a[i]]==1:
        cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
prime = [True] * (10 ** 6 + 10)

b = sorted(set(a))

for i in b:
    num = i * 2
    while True:
        if num >= 10 ** 6 + 1:
            break
        prime[num] = False
        num += i

ans = 0
for s in a:
    if prime[s] == True and c[s] == 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

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

c=Counter(a)

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

print(cnt)

Submission status: Accepted

Solution code:
#青の人の解答（hir35）

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

#それぞれの数字が何回ずつ出現したかをカウント
c = Counter(a)

#リストpに10＾6+1個のTrueを格納
p = [True] * (10 ** 6 + 1)

#list(set())で重複したものを取り除いてからリストにできる
s = list(set(a))

#sの要素一つ一つを見ていく
for x in s:
    t = x * 2
    #tが10^6以下ならば，p[t]にFalseを代入
    #つまり，x(aに格納されている数)の倍数がfalseに
    while t <= 10 ** 6:
        p[t] = False
        t += x
ans = 0

for x in a:
    #もしその数が一つしかなくて，倍数がないならans+1
    if c[x] == 1 and p[x] == True:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
a = list(map(int, input().split()))
m = 1000001

count = 0
cnt = [0] * m
for i in range(n):
  if cnt[a[i]] == 0:
    for j in range(a[i], m, a[i]):
      cnt[j] += 1
  else:
    cnt[a[i]] = 2
for i in range(n):
  if cnt[a[i]] == 1:
    count += 1
print(count)

Submission status: Accepted

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

a_sorted = sorted(a)
divisible_list = [0] * (max(a)+1)

for i in range(len(a)):
    # 過去にすでに同じ数字への加算があったら飛ばす
    if divisible_list[a[i]] > 2:
        continue
    for j in range(0, len(divisible_list), a[i]):
        divisible_list[j] += 1

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

Submission status: Accepted

Solution code:
import numpy as np


N = int(input())
A = list(map(int, input().split())) + [10**7]

A.sort()
e = np.zeros(10**6 + 1)
ans = 0
for i in range(N):
    if e[A[i]] == 0:
        e[::A[i]] = 1 # スライスで倍数indexを一気に変更できる。すごい。
        # 同じ値が重複していないか判定
        if A[i] != A[i+1]:
            ans += 1
print(ans)

Submission status: Accepted

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

a_sorted = sorted(a)
divisible_list = [0] * (max(a)+1)

for i in range(len(a)):
    for j in range(0, len(divisible_list), a[i]):
        divisible_list[j] += 1

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

Submission status: Accepted

Solution code:
n = int(input())
ls = sorted(list(map(int, input().split())))
dp = [0] * (ls[-1] + 1)
for i in ls:
    dp[i] += 1
    if dp[i] == 1:
        for j in range(i*2, ls[-1] + 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()
M = A[-1]
b = [True] * (M + 1)

count = 0
for i, a in enumerate(A):
  if not b[a]:
    continue
  for j in range(a, M+1, a):
    b[j] = False
  if i < N-1 and A[i+1] == a:
    continue
  count += 1

print(count)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
a = list(map(int, input().split()))
m = 1000005

count = 0
cnt = [0] * m
for i in range(n):
  if cnt[a[i]] == 0:
    for j in range(a[i], m, a[i]):
      cnt[j] += 1
  else:
    cnt[a[i]] = 2
for i in range(n):
  if cnt[a[i]] == 1:
    count += 1
print(count)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

import numpy

def main():
  n = int(input())
  la = sorted(list(map(int, input().split())))
  a_max = max(la)
  dp = numpy.ones(a_max + 1)
  counts = numpy.zeros(a_max + 1)
  for a in la:
    counts[a] += 1
    if counts[a] < 2:
      dp[2*a::a] = 0
  print(len([a for a in la if dp[a]==1 and counts[a] == 1]))

if __name__=='__main__':
  main()

Submission status: Accepted

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

ma = max(A)
Er = [0 for _ in range(ma + 5)]

for i in range(N):
    temp = A[i]
    if Er[temp] != 2:
        a = 0
        while(1):
            a += 1
            tt = a * temp
            if tt >= ma + 5:
                break
            Er[tt] += 1
        
ans = 0
for i in range(N):
    temp = A[i]
    if Er[temp] == 1:  ans += 1
        
print(ans)

Submission status: Accepted

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

ma = max(A)
Er = [0 for _ in range(ma + 5)]
is_c = [0 for _ in range(ma + 5)]

for i in range(N):
    temp = A[i]
    if Er[temp] != 2:
        a = 0
        while(1):
            a += 1
            tt = a * temp
            if tt >= ma + 5:
                break
            Er[tt] += 1
        
ans = 0
for i in range(N):
    temp = A[i]
    is_c[temp] += 1
    if is_c[temp] == 2:
        continue  
    if Er[temp] == 1:  ans += 1
        
print(ans)

Submission status: Accepted

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

dq = [0] * (nums[-1] + 1)

for num in nums:
    dq[num] += 1
    if dq[num] == 1:
        for i in range(num*2, nums[-1]+1, num):
            dq[i] += 2

print(dq.count(1))

Submission status: Accepted

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

A = sorted(A)
maxi = 10**6+1
dp = [0] * maxi

for i in range(N):
    tmp = A[i]
    if dp[tmp] != 0:
        dp[tmp] = 2
        continue
    else:
        for j in range(tmp, maxi, tmp):
            dp[j] += 1

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

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin

def main():
    n=int(input())
    As=list(map(int, stdin.readline().split()))
    As.sort()
    check=[0]*(10**6+10)
    for a in As:
        count=1
        while a*count < 10**6+2 and a*count < As[-1]+1:
            if check[a*count]<2:
                check[a*count]+=1
            count+=1
    ans=0
    for a in As:
        if check[a]==1:
            ans+=1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

from collections import Counter

n = readint()
a = sorted(readints())

c = Counter(a)
ans = 0
b = [1]*(max(c)+1)
l = max(c)

for x in c:
    if c[x]==1 and b[x]==1:
        ans += 1
    for i in range(1,l//x+1):
        b[x*i] = 0

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
dp = [True] * (A[-1]+1)

for i,num in enumerate(A):
    if i < N-1 and A[i+1] == num:
        dp[num] = False
    else:
        for j in range(2*num, A[-1]+1, num):
            dp[j] = False

print(len([i for i in A if dp[i]]))

Submission status: Accepted

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

A.sort()

M = 1000005
cnt = [0] * M

for i in range(N):
	if cnt[A[i]] != 0:
		cnt[A[i]] = 2
		continue
	for j in range(A[i],M,A[i]):
		cnt[j] += 1


ans = 0

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

print(ans)

Submission status: Accepted

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

limit = 10**6 + 2
A += [limit]
dp = [True] * (limit)

ans = 0
for i in range(n):
  a = A[i]
  if dp[a] and a != A[i+1]:
    ans += 1
  
  if dp[a] == False:
    continue
  for t in range(a,limit,a):    
    dp[t] = False
    t += a

print(ans)

Submission status: Accepted

Solution code:
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

import math

MAX=10**6+1

n=ni()
a=nl()

s = [0]*(MAX)

for ai in a:
  if s[ai]!=0:
    s[ai]=2
    continue
  for i in range(ai,MAX,ai):
    s[i]+=1

cnt=0
for ai in a:
  if s[ai]==1:
    cnt+=1

print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
dp = [True] * (A[-1]+1)

for i,num in enumerate(A):
    if i < N-1 and A[i+1] == num:
        dp[num] = False
    for j in range(2*num, A[-1]+1, num):
        dp[j] = False

print(len([i for i in A if dp[i]]))

Submission status: Accepted

Solution code:
n = int(input())
L = list(map(int,input().split()))
dp = [0]*((10**6)+1000)
for i in L:
    dp[i] +=1

one = []
for i in range(10**6+1000):
    if dp[i] == 1:
        one.append(i)

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

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

Submission status: Accepted

Solution code:
from collections import Counter

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

A.sort()
C = Counter(A)
for a in A:
    if C[a] == 0: continue
    if C[a] > 1:
        C[a] = 0
    for ab in range(2 * a, A[-1] + 1, a):
        C[ab] = 0

print(sum(C.values()))

Submission status: Accepted

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

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

for i in range(N):
    num = A[i]
    if l[num] != 0:
        l[num] = 2
        continue
    for j in range(num, 10**6+1, num):
        l[j] += 1
ans = 0
for i in range(N):
    num = A[i]
    if l[num] == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    dp = [False] * (A[-1] + 1)
    r = 0

    for i, a in enumerate(A):
        if dp[a]:
            continue
        dp[a::a] = [True] * len(dp[a::a])
        if i < N - 1 and A[i + 1] == a:
            continue
        r += 1
    return r


print(main())

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
check = [0] * 1000001
res = 0
for i in range(N):
    if check[A[i]]:
        continue
    if i == N-1 or A[i] != A[i+1]:
        res += 1
    for j in range(A[i], 1000001, A[i]):
        check[j] = 1
print(res)

Submission status: Accepted

Solution code:
from collections import Counter

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

Submission status: Accepted

Solution code:
import sys
import collections
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():
    n = I()
    mylist = list(MI())
    max_a = max(mylist)
    exclude_set = set()
    tlist = [False] * (max_a+1)
    for a in mylist:
        if tlist[a]:
            exclude_set.add(a)
        else:
            tlist[a] = True
    ans = 0
    
    for i in range(1, max_a//2 + 1):
        if not tlist[i]:
            continue
        else:
            for j in range(2*i, max_a+1, i):
                tlist[j]=False
    for i in range(len(tlist)):
        if tlist[i] and not i in exclude_set:
            ans += 1
    print(ans)
                
    

if __name__ == '__main__':
    main()

Submission status: Accepted

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

    A.sort()

    l=[True for _ in range(A[-1]+1)]
    
    cnt=0
    for n in range(N-1):
        if l[A[n]]==True:
            if A[n]==A[n+1]:
                l[A[n]]=False
            else:
                l[A[n]]=False
                cnt+=1
            i=1
            while i*A[n]<=A[-1]:
                l[A[n]*i]=False
                i+=1
    if l[A[N-1]]==True:
        cnt+=1
        l[A[N-1]]=False
    return cnt

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

Submission status: Accepted

Solution code:
import sys

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

def main():

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

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = 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()))

x = max(a)
dp = [0] * (x+1)
for ai in a:
    i = 1
    if dp[ai] <= 2:
        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:
# 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] = 2
        continue
    for j in range(i, m + 1, i):
        count[j] += 1


for i in a:
    if count[i] == 1:
        # print(i)
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter

MAX_A = 10**6 + 5

N = int(sys.stdin.readline())
A = [int(x) for x in sys.stdin.readline().split()]
# A.sort(reverse=True)

dp = [True] * MAX_A
Ac = Counter(A)

for k, v in Ac.items():
    if v > 1:
        dp[k] = False
    for n in range(2*k, MAX_A, k):
        dp[n] = False

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

print(ans)

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
    if dp[ai] <= 2:
        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:
"""
考え方のポイント
・自分以外では割り切れないような数の個数を求める
　→ 数列の各項に対して〇（割り切れない）×がついていって、〇の個数を数える
・[2, 2]みたいな入力は、他の数で割り切れるようになるので、同じ数が入っていると絶対に×になる。

まずは入力が全部異なる前提で進める。
範囲内の整数からなる全て配列dを用意する。
→ 入力の数列を約数としてもつ数にチェックをしていく（Anに2が含まれていれば、2の倍数全てにチェック（+1)する）
→ チェック後にd[i]をみたとき、d[i]の約数がan中に何個存在するかが示されていることになる。（2∈Aiならd[5](=6)の値は必ず1以上になってる)
"""
N = int(input())
An = [int(i) for i in input().split()]
An.sort()
max_val = 10**6+1
d = [0] * max_val


# O(N) = O(2*10^5)
# d[i]のうち、配列の値の位置を+1しとく。
for i in An:
    d[i] += 1
    # O(MlogM) = 6*10^6
    # 始めてその倍数がきたときだけ
    if(d[i] == 1):
        # [2, 2]などの重複がない場合（既にカウントされているものではない場合)
        # 倍数の位置にも2としておいて以降はみないようにする
        for val in range(i*2, max_val, i):
            d[val] = 2

print(d.count(1))

Submission status: Accepted

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

A.sort()
dp = [True for _ in range(A[-1]+1)]

for i in range(n-1):#同じものがいたらその番号をfalseにする
    if A[i] == A[i+1]:
        dp[A[i]] = False

res = 0
for a in A:
    if dp[a]:
        res += 1
    for b in range(a,len(dp),a):#aの倍数を削除する
        dp[b] = False
print(res)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
M = 10**6 + 2
cnt = [0 for _ in range(M)]
A.sort()

for i in A:
    if cnt[i] != 0: # cnt[i]がそれまでに出てきた数値で割り切れていたとき
        cnt[i] = 2 # cnt[i]の倍数はどうせすでに1か2になっているので考慮しなくていい
        continue
    j = i
    while j < M:
        cnt[j] += 1
        j += i
ans = 0
for i in A:
    if cnt[i] == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10

    N = II()
    A = LMIIS()
    ans = 0
    count = defaultdict(int)
    for a in A:
        count[a] += 1
    A = list(set(A))
    A.sort()

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

    sup = max(A)+1
    Not_Divisible = [True] * sup
    Not_Divisible[0] = False


    for a in A:
        if Not_Divisible[a]:
            for i in range(a*2,sup,a):
                Not_Divisible[i] = False

    ans = 0
    for a in A:
        if Not_Divisible[a] and count[a] == 1:
            ans += 1

    print(ans)
            


    
main()