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 numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left, bisect_right #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

N = int(input())
A = list(map(int, input().split()))
A.sort()
C = Counter(A)
S = set(A)

maxA = A[-1]
chk = [0] * (maxA+1)
for s in S:
    for i in range(s, maxA+1, s):
        chk[i] += 1

res = [s for s in S if chk[s] == 1 and C[s] == 1]
# print(res)
print(len(res))

Submission status: Accepted

Solution code:
N = int(input())
*A, = map(int, input().split())
# N = 5
# A = list([24, 11, 8, 3, 16])

M = max(A) + 1
cnt =[0 for _ in range(M)]

for i in A:
    for j in range(i, M, i):
        cnt[j] += 1

ans = 0
for k in A:
    if cnt[k] == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

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

# ===CODE===

eps = 10 ** (-9)


def main():
    n = ni()
    a = na()

    seta = set(a)
    cnta = collections.Counter(a)
    lista = list(seta)
    lista.sort()

    table = [True for _ in range(10 ** 6 + 1)]
    ans = 0

    for ai in lista:
        if table[ai]:
            if cnta[ai] == 1:
                ans += 1
            for i in range(ai, 10 ** 6 + 1, ai):
                table[i] = False

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections
N=int(input())
A=list(map(int,input().split()))
A=sorted(A)
c=collections.Counter(A)
if __name__=="__main__":
    if 1 in A:
        if c[1]==1:
            print(1)
        else:
            print(0)
    else:
        A=[]
        dp=[True for _ in range(10**6+10)]
        for key,value in c.items():
            if value==1:
                A.append(key)
            else:
                if dp[key]:
                    i=2
                    while i*key<=10**6:
                        dp[i*key]=False
                        i+=1 
        if len(A)==0:
            print(0)
        else:
            for a in A:
                if dp[a]:
                    i=2
                    while i*a<=10**6:
                        dp[i*a]=False
                        i+=1 
            ans=0
            for a in A:
                if dp[a]:
                    ans+=1
            print(ans)

Submission status: Accepted

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

A = set(A)
MAX_A = 10 ** 6
X = [0] * (MAX_A + 1)
for a in A:
    for i in range(a, MAX_A + 1, a):
        X[i] += 1

ans = len([a for a in A if (X[a] == 1) and (C[a] == 1)])
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
lineup = sorted([int(x) for x in input().split()])
duplicate={}
for i in lineup:
    if i in duplicate:
        duplicate[i]+=1
    else:
        duplicate[i]=1
b=max(lineup)+1
sieve=[1]*(b)
counter=0
for i in range(N):
    if sieve[lineup[i]]:
        if duplicate[lineup[i]]==1:
            counter+=1
        for j in range(lineup[i],b,lineup[i]):
            sieve[j]=0
        
print(counter)

Submission status: Accepted

Solution code:
N=int(input())
lineup=sorted([int(x) for x in input().split()])
duplicate={}
for i in lineup:
	if i in duplicate:
		duplicate[i]+=1
	else:
		duplicate[i]=1
b=max(lineup)+1
sieve=[1]*(b)
counter=0
for i in range(N):
	for j in range(lineup[i]*2,b,lineup[i]):
		sieve[j]=0
	if duplicate[lineup[i]]==1 and sieve[lineup[i]]==1:
		counter+=1
print(counter)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    L = [0] * (10**6+1)
    for a in A:
        L[a] += 1
    ans = 0
    Ng = [False] * (10**6+1)
    for a, cnt in enumerate(L):
        if cnt:
            for i in range(a*2, 10**6+1, a):
                Ng[i] = True
    for a, (cnt, ng) in enumerate(zip(L, Ng)):
        if cnt == 1 and not ng:
            ans += 1
    print(ans)

main()

Submission status: Accepted

Solution code:
import collections

n = int(input())
a = list(map(int,input().split()))
cnt = collections.Counter(a)
#print(cnt)
a.sort()
dp = [1]*(max(a)+1)

sum = 0
for i in range(n):
    for j in range(a[i]*2,len(dp),a[i]):
            dp[j] = 0
    if dp[a[i]] == 1 and cnt[a[i]]==1:
        sum += 1

print(sum)

Submission status: Accepted

Solution code:
n,*a=map(int,open(0).read().split())
a.sort()
num=[True for i in range(a[-1]+1)]
for i in range(n):
  if num[a[i]]:
    for j in range(a[-1]//a[i]+1):
      if j<2:
        continue
      num[a[i]*j]=False
    if i==n-1:
      pass
    elif a[i]==a[i+1]:
      num[a[i]]=False
    else:
      pass
  else:
    continue
ans=0
for i in range(n):
  if num[a[i]]:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
# ex. 24 11 8 3 16
A.sort()
# ex. 3 8 11 16 24
cnt = 0
# Aの最大値が24なら25個用意する感じ
# indexと考える値を一致させて分かりやすくしている
# Trueで初期化
# 最後のインデックスはA[-1]
dp = [True] * (A[-1] + 1)

# エラトステネスの篩っぽいやつ
for i in range(N):
    if dp[A[i]] == True:
        # dp[A[i]], dp[2*A[i]], dp[3*A[i]],...をFalseにする
        for j in range(A[i], A[-1] + 1, A[i]):
            dp[j] = False

        if i < N - 1:
            # 次も同じ数字が存在するなら数えない、なぜならお互いに割れてしまって題意を満たさないから
            # 次以降に出てくる同じ数字は既にFalseになっているのでもう走査する事はない
            if A[i] != A[i + 1]:
                cnt += 1
        # i=N-1の時は次がないので無条件でcntを増やす
        # elseの方が良さそうだが明示的にするためにelifを使った
        elif i == N - 1:
            cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
# ex. 24 11 8 3 16
A.sort()
# ex. 3 8 11 16 24
cnt = 0
# Aの最大値が24なら25個用意する感じ
# indexと考える値を一致させて分かりやすくしている
# Trueで初期化
# 最後のインデックスはA[-1]
dp = [True] * (A[-1] + 1)

# エラトステネスの篩っぽいやつ
for i in range(N):
    if dp[A[i]] == True:
        # dp[A[i]], dp[2*A[i]], dp[3*A[i]],...をFalseにする
        for j in range(A[i], A[-1] + 1, A[i]):
            dp[j] = False

        if i < N - 1:
            # 次も同じ数字が存在するなら数えない、最後でcntを増やす
            # 前との比較で考えても良さそう、その場合はN-1ではなく0を例外処理？
            if A[i] != A[i + 1]:
                cnt += 1
        # i=N-1の時は次がないので無条件でcntを増やす
        # elseの方が良さそうだが明示的にするためにelifを使った
        elif i == N - 1:
            cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = sorted(map(int, input().split()))
c = Counter(a)
s = set()
for i in range(n):
    if a[i] in s:
        continue
    elif c[a[i]] >= 2:
        s.add(a[i])
    for j in range(2,10**6//a[i]+1):
        s.add(a[i]*j)
print(sum(not (ai in s) for ai in a))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
ls = [1] * (10 ** 6 + 1)
cnt = [0] * (10 ** 6 + 1)
for i in range(n):
    cnt[a[i]] += 1
    if cnt[a[i]] == 1:
        if ls[a[i]] == 1:
            for j in range(a[i] * 2, 10 ** 6 + 1, a[i]):
                ls[j] = 0
ans = 0
for i in range(n):
    if ls[a[i]] == 1 and cnt[a[i]] == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = sorted([int(x) for x in input().split()])
freq = Counter(a)
A = max(a)
good = [True]*(A+1)
ans = 0
for x in freq:
	for k in range(2*x,A+1,x):
		good[k] = False
	if good[x] and freq[x]==1:
		ans += 1
print(ans)

Submission status: Accepted

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

for i in range(N-1):
  if dp[A[i]] == True:
    for j in range(A[i], A[-1]+1,A[i]):
      dp[j] = False
    if A[i] != A[i+1]:
      cnt+=1
if dp[A[-1]] == True:
  cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
N, *A = map(int, open(0).read().split())
A.sort()
dp = [True]*3*int(1e6)
x = -1
for a in A:
  if a == -1: continue
  x = a
  while x <= A[-1]:
    x += a
    dp[x] = False
  x = a

res = 0
for i, a in enumerate(A):
  if i > 0 and a == A[i-1]: continue
  if i < N-1 and a == A[i+1]: continue
  if dp[a]: res += 1
print(res)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = sorted(list(map(int,input().split())))
    dp = [0 for i in range(a[-1]+1)]
    lbl = []
    for i in range(n):
        if dp[a[i]]==2:
            lbl.append(a[i])
            continue
        if dp[a[i]]==1:
            continue
        else:
            for j in range(1,a[-1]//a[i]+1):
                dp[a[i]*j] = 1
            dp[a[i]] = 2
    for i in range(len(lbl)):
        dp[lbl[i]] = 0
    ans = 0
    for i in range(len(dp)):
        if dp[i] == 2:
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
memo = [0] * (10**6 + 1)
f = defaultdict(int)
for i in a:
    if f[i] > 1:
        continue
    f[i] += 1
    for j in range(i, 10**6+1, i):
        memo[j] += 1

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

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = sorted(map(int, input().split()))
c = Counter(a)
s = set()
for i in range(n):
    if a[i] in s:
        continue
    elif c[a[i]] >= 2:
        s.add(a[i])
    for j in range(2,10**6//a[i]+1):
        s.add(a[i]*j)
print(sum([not (ai in s) for ai in a]))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
max_num = a[-1] + 1
cnt = [0] * (max_num)
a.sort()
ans = 0


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

a = set(a)

for k in a:
    for l in range(k * 2, (max_num), k):
        cnt[l] += 1

for m in a:
    if cnt[m] == 1:
        ans += 1
    


print(ans)

Submission status: Accepted

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


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

a = set(a)

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

for m in a:
    if cnt[m] == 1:
        ans += 1
    


print(ans)

Submission status: Accepted

Solution code:
# review
def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    ans = 0
    OK = [True for i in range(10**6+1)]
    CNT = [0 for i in range(10**6+1)]
    for x in A:
        CNT[x] += 1
        if CNT[x] == 1:
            for i in range(2, 10**6+1):
                if i*x > 10**6:
                    break
                OK[i*x] = False
    for x in A:
        if CNT[x] == 1 and OK[x]:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
A = list(map(int,input().split()))
mx = max(A)
C = Counter(A)
D = {a:True for a in A}
for a in A:
    if C[a]>1: D[a]=False
    for i in range(a*2, mx+1, a):
        D[i]=False
print(sum([D[a] for a in A]))

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


#隣接リスト 1-order
def make_adjlist_d(n, edges):
    res = [[] for _ in range(n + 1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
        res[edge[1]].append(edge[0])
    return res


def make_adjlist_nond(n, edges):
    res = [[] for _ in range(n + 1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
    return res


#nCr
def cmb(n, r):
    return math.factorial(n) // math.factorial(r) // math.factorial(n - r)


def main():
    N = NI()
    A = NLI()
    A = sorted(A)

    ma = A[-1]
    hurui = [0] * (ma + 10)
    for a in A:
        if hurui[a] == 0:
            hurui[a] = 1
        else:
            hurui[a] = 10

    for a in A:
        if hurui[a] == 0:
            continue

        for i in range(a*2, ma+10, a):
            hurui[i] = 0

    print(hurui.count(1))



if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

max_len_A = 10**6+1
data = [0]*max_len_A
A = list(set(A))

for a in A:
    if data[a]==0:
        for j in range(a+a, max_len_A, a):
            data[j]+=1


ans = len([a for a in A if data[a]==0 and count[a]==1])
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter

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

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

s = set()
cnt = Counter(a)

for i in range(n):
    if a[i] in s:
        continue
    if cnt[a[i]] >= 2:
        s.add(a[i])
    for j in range(2,10**6//a[i]+1):
        s.add(a[i]*j)

ans = 0
for i in range(n):
    if a[i] in s:
        continue
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
#import time

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

    As.sort()
    amax = max(As) + 1
    lis = [True] * amax
    ans = 0

    for i in range(N-1):
        if lis[As[i]]:
            for j in range(As[i], amax, As[i]):
                lis[j] = False
            if As[i] < As[i+1]:
                ans += 1
    if lis[-1]:
        ans += 1

    return ans

if __name__ == '__main__':
    #start = time.time()
    print(main())
    #elapsed_time = time.time() - start
    #print("経過時間:{}".format(elapsed_time * 1000) + "[msec]")

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
Ad = {}
for a in A:
    Ad[a] = Ad.get(a, 0) + 1
A, maxA, ans = sorted(Ad.keys()), max(Ad.keys()), 0

for a in A:
    if Ad[a] == 1:
        ans += 1
    if Ad[a] >= 1:
        if a == 1:
            break
        m = 2
        while a * m <= maxA:
            if a * m in Ad:
                Ad[a * m] = 0
            m += 1

print(ans)

Submission status: Accepted

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

c.sort()
a = c[N-1]
list_c = [0]*(a+1)
for i in c:
  mal = 2
  b = i
  while i<=a:
    list_c[i]+=1
    i = b*mal
    mal+=1
count = 0
for i in c:
  if list_c[i]==1:
    count+=1
print(count)

Submission status: Accepted

Solution code:
n = int(input())
aas = sorted(list(map(int, input().split())))
aas_len = len(aas)
if aas_len == 1:
    print(1)
    exit()
aas_max = aas[-1]
arr = [1]*(aas_max+1)
for i in range(aas_len):
    if arr[aas[i]] == 0:
        continue
    if arr[aas[i]] == 1:
        arr[aas[i]] = 2
    else:
        arr[aas[i]] = 0
        continue
    idx = aas[i]*2
    while idx <= aas_max:
        arr[idx] = 0
        idx += aas[i]
res = 0
for i in aas:
    if arr[i] != 0:
        res += 1
print(res)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


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


def main():
    N = II()
    A = LI()
    A.sort()
    MAX = 10**6+1
    All = [0] * MAX

    setA = set(A)
    for i in A:
        k = i
        All[k] += 1
        k += i
        if All[i] >= 2:
            continue
        while k < MAX:
            All[k] += 1
            k += i

    ans = 0
    for i in range(1, MAX):
        if All[i] == 1 and i in setA:
            ans += 1

    print(ans)

    # oj t -c "pypy3 main.py"
    # acc s main.py -- --guess-python-interpreter pypy
main()

Submission status: Accepted

Solution code:
import numpy as np

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

vals, cnts = np.unique(A, return_counts=True)

if len(vals) == 1:
    print(0 if cnts[0] > 1 else 1)
elif vals[0] == 1:
    print(0 if cnts[0] > 1 else 1)
else:
    sat = np.ones(vals.max() + 1, dtype=int)
    for x in vals:
        sat[2 * x::x] = 0
    ans = ((sat[vals] == 1) & (cnts == 1)).sum().item()
    print(ans)

# 1
# 1
# 5
# 2 2 2 3 3
# 5
# 2 2 2 4 4
# 5
# 1 1 1 1 2

Submission status: Accepted

Solution code:
import numpy as np

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

vals, cnts = np.unique(A, return_counts=True)

if len(vals) == 1:
    print(0 if cnts[0] > 1 else 1)
elif vals[0] == 1:
    print(0 if cnts[0] > 1 else 1)
else:
    sat = np.ones(vals.max() + 1, dtype=bool)
    for x in vals:
        sat[2 * x::x] = False
    ans = (sat[vals] & (cnts == 1)).sum().item()
    print(ans)

# 1
# 1
# 5
# 2 2 2 3 3
# 5
# 2 2 2 4 4
# 5
# 1 1 1 1 2

Submission status: Accepted

Solution code:
import numpy as np

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

vals, cnts = np.unique(A, return_counts=True)

if len(vals) == 1:
    print(0 if cnts[0] > 1 else 1)
elif vals[0] == 1:
    print(0 if cnts[0] > 1 else 1)
else:
    sat = np.ones(vals.max() + 1, dtype=int)
    for x in vals:
        sat[2 * x::x] = 0
    ans = ((sat[vals] == 1) & (cnts == 1)).sum().item()
    print(ans)

# 5
# 2 2 2 3 3
# 5
# 2 2 2 4 4
# 5
# 1 1 1 1 2

Submission status: Accepted

Solution code:
import numpy as np
from collections import Counter


def solve(string):
    n, *a = map(int, string.split())
    table = np.array([True] * (10**6 + 1))
    ma = max(a)
    for _a in a:
        if table[_a]:
            table[2*_a:ma + 1:_a]=False
    i = np.array([k for k,v in Counter(a).items() if v==1],dtype=np.int)
    return str(table[i].sum())


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Accepted

Solution code:
from collections import Counter


def solve(string):
    n, *a = map(int, string.split())
    table = [True] * (10**6 + 1)
    ma = max(a)
    for _a in a:
        if table[_a]:
            for i in range(2 * _a, ma + 1, _a):
                table[i] = False
    return str(sum(table[k] for k, v in Counter(a).items() if v == 1))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Accepted

Solution code:
import numpy as np
from collections import Counter


def solve(string):
    n, *a = map(int, string.split())
    table = np.array([True] * (10**6 + 1))
    for _a in a:
        if table[_a]:
            table[2*_a::_a]=False
    i = np.array([k for k,v in Counter(a).items() if v==1],dtype=np.int)
    return str(table[i].sum())


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
input=sys.stdin.readline

def main():
  n = int(input())
  a = list(map(int, input().split(' ')))
  a.sort()
  a_max = a[-1]
  b = 0
  db = [0] * a_max
  for i in range(1, n-1):
    if a[i] != a[i+1] and a[i] != a[i-1]:
      db[a[i]-1] = 1
  if n == 1 or a[0] != a[1]:
    db[a[0]-1] = 1
  if n > 1 and a[-1] != a[-2]:
    db[-1] = 1
  for i in a:
    t = 2
    while(i * t <= a_max):
      db[i*t-1] = 0
      t += 1
  print(sum(db))
  

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


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


def main():
    N = II()
    A = LI()
    A.sort()
    MAX = A[-1]+1
    All = [0 for i in range(MAX)]

    setA = set(A)
    for i in A:
        k = i
        All[k] += 1
        k += i
        if All[i] == 2:
            continue
        while k < MAX and i in setA:
            All[k] += 1
            k += i

    ans = 0
    for i in range(1, MAX):
        if All[i] == 1 and i in setA:
            ans += 1

    print(ans)

    # oj t -c "pypy3 main.py"
    # acc s main.py -- --guess-python-interpreter pypy
main()

Submission status: Accepted

Solution code:
import numpy as np
n=int(input())
a=list(map(int,input().split()))+[10**6+1]
a=sorted(a)
flag=np.array([0 for i in range(10**6+1)])
ans=0
for i in range(n):
    if flag[a[i]]==0:
        flag[::a[i]]=1
        if a[i]!=a[i+1]:
            ans+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict

n = int(input())
a = list(map(int, input().split()))
dic = Counter(a)
memo1 = set()
memo2 = set()

MAX = 10 ** 6 + 1
for i in a:
  if i in memo1:
    continue
  if i in dic:
    if dic[i] > 1:
      memo2.add(i)
  for j in range(i*2, MAX, i):
    if j in dic:
      memo2.add(j)
  memo1.add(i)
ans = len(memo1) - len(memo2)
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter

import numba as nb
import numpy as np

input = sys.stdin.readline


@nb.njit("i8(i8[:],i8[:])", cache=True)
def solve(keys, values):
    MAX_A = 10 ** 6
    divisible = [False] * (MAX_A + 1)
    ans = 0
    for k, v in zip(keys, values):
        if v == 1 and not divisible[k]:
            ans += 1
        for i in range(k, MAX_A + 1, k):
            divisible[i] = True
    return ans


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

    A.sort()
    c = Counter(A)
    keys = np.array(tuple(c.keys()), dtype=np.int64)
    values = np.array(tuple(c.values()), dtype=np.int64)

    ans = solve(keys, values)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import Counter

import numba as nb
import numpy as np

input = sys.stdin.readline


@nb.njit("i8(i8[:],i8[:])")
def solve(keys, values):
    MAX_A = 10 ** 6
    divisible = [False] * (MAX_A + 1)
    ans = 0
    for k, v in zip(keys, values):
        if v == 1 and not divisible[k]:
            ans += 1
        for i in range(k, MAX_A + 1, k):
            divisible[i] = True
    return ans


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

    A.sort()
    c = Counter(A)
    keys = np.array(tuple(c.keys()), dtype=np.int64)
    values = np.array(tuple(c.values()), dtype=np.int64)

    ans = solve(keys, values)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import Counter

import numba as nb
import numpy as np

input = sys.stdin.readline
MAX_A = 10 ** 6


@nb.njit("i8(i8[:],i8[:])")
def solve(keys, values):
    divisible = [False] * (MAX_A + 1)
    ans = 0
    for k, v in zip(keys, values):
        if v == 1 and not divisible[k]:
            ans += 1
        for i in range(k, MAX_A + 1, k):
            divisible[i] = True
    return ans


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

    A.sort()
    c = Counter(A)
    keys = np.array(tuple(c.keys()), dtype=np.int64)
    values = np.array(tuple(c.values()), dtype=np.int64)

    ans = solve(keys, values)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import Counter

input = sys.stdin.readline
MAX_A = 10 ** 6


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

    A.sort()
    divisible = [False] * (MAX_A + 1)
    ans = 0
    for k, v in Counter(A).items():
        if v == 1 and not divisible[k]:
            ans += 1
        for i in range(k, MAX_A + 1, k):
            divisible[i] = True

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

a.sort()
amx=max(a)+1
l=[True]*amx
ans=0

for i in range(n-1):
    if l[a[i]]:
        for j in range(a[i],amx,a[i]):
            l[j]=False
        if a[i]<a[i+1]:
            ans+=1

if l[-1]:
    ans+=1

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from collections import Counter
n = int(input())
aa = list(map(int, input().split()))
ngs = np.zeros((10**6)+1, dtype=int)

for a in set(aa):
    ngs[2*a::a] = 1
    
dic = Counter(aa)
times = np.array(list(dic.keys()))[np.array(list(dic.values())) > 1]

for i in times:
    ngs[i] = 1
cnt = 0
for a in aa:
    cnt += 1-ngs[a]
print((cnt))

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

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


#############
# Main Code #
#############

N = getN()
A = getList()
L = max(A)

dp = [1] * (L + 1)
dp[0] = 0
num_list = [0] * (L + 1)

for i in A:
    if num_list[i] == 0:
        for j in range(i * 2, L + 1, i):
            dp[j] = 0
    num_list[i] += 1

ans = 0
for i in range(L + 1):
    if num_list[i] == 1 and dp[i] == 1:
        ans += 1
print(ans)

Submission status: Accepted

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

for i in range(n-1):
  a_i = a[i]
  if div[a_i]:
    for j in range(a_i,am,a_i):
      div[j] = 0
    if a_i < a[i+1]:
      ans += 1
if div[-1]:ans += 1
print(ans)

Submission status: Accepted

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

for i in sorted(a):
  if 1 <= dp[i]:
    dp[i] += 1
    continue

  for j in range(1, ma//i + 1):
    dp[j * i] += 1

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
_, *a = map(int, open(0).read().split())
a.sort()
p = [0] * a[-1]
for i in a:
    for j in range(1, a[-1] // i + 1):
        p[j * i - 1] += j
print(sum(i == 1 for i in p))

Submission status: Accepted

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

a.sort()

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

ans = [1] * (a[n-1]+1)

for i in range(n):
    if i >= 1 and a[i] == a[i-1]:
        ans[a[i]] = 0

    else:
        j = 2
        while j*a[i] <= a[n-1]:
            ans[j*a[i]] = 0
            j += 1


sum = 0

for i in range(n):
    sum += ans[a[i]]


print(sum)

Submission status: Accepted

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())
    N = next(it)
    A = [next(it) for i in range(N)]

    if N == 1:
        print(1)
        return

    ax = max(A)+1
    dp = [0]*ax
    for ai in A:
        da = dp[ai]
        if da > 1:
            continue
        dp[ai] += 1
        if da == 0:
            for aj in range(2*ai, ax, ai):
                dp[aj] = 2
    ans = 0
    for ai in A:
        if dp[ai] == 1:
            ans += 1
    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

max_per = max(As)
ansList = [0 for _ in range(max_per + 10)]

for A in As:
    checkList = [i for i in range(A, max_per+1, A)]
    #print(checkList,As)

    for check in checkList:
        ansList[check] += 1

ans = 0

for A in As:
    if(ansList[A] == 1):
        ans += 1

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
x = int(input())
p = sorted(list(map(int,input().split())))
d = [True]*(p[-1]+1)
e = [False]*(p[-1]+1)
for i in p:
    if e[i]:
        d[i] = False
        continue
    else:
        e[i] = True
    idx = 2*i
    while idx < len(d):
        d[idx] = False
        idx += i

cnt = 0
for i in p:
    cnt += int(d[i])    
print(cnt)

Submission status: Accepted

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