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:
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
"""
普通にやると、O(N^2)かかる
エラトステネスの篩でできないか？
まず、長さ10^6+1のflag配列を用意する。初期値は全部1。
Aに含まれる値以外は0にする。
で、エラトステネスの篩と同じことをする。
"""
A = Counter(A)
flags = [1]*(1000001)
for i in range(1000001):
    if i not in A:
        flags[i] = 0
ans = 0
for i in range(1000001):
    if flags[i] == 1:
        ans += 1
        for j in range(i*2,1000001,i):
            flags[j] = 0

for i in range(1000001):
    if flags[i] == 1:
        if A[i] > 1:
            ans -= 1

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
input = stdin.buffer.readline
setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi, radians, sin, cos

MOD = 10 ** 9 + 7
INF = 10 ** 18

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

cnt = [0] * (10 ** 6 + 1)
for a in A:
    cnt[a] += 1

if cnt[1] >= 2:
    print(0)
    exit()

if cnt[1] == 1:
    print(1)
    exit()

answer = 0
for i in range(2, 10 ** 6 + 1):
    if cnt[i] == 1:
        answer += 1
    if cnt[i] == 0:
        continue
    k = 2
    while i * k <= 10 ** 6:
        cnt[i * k] = 0
        k += 1

print(answer)

Submission status: Accepted

Solution code:
n=int(input())
A=[int(i) for i in input().split()]

A.sort()
A.append(-1)

dat={i:False for i in range(10**6+10)}

ans=0
for i in range(len(A)-1):
    if dat[A[i]]:
        pass
    else:
        if A[i]!=A[i+1]:
            ans+=1
        for i in range(A[i],10**6+10,A[i]):
            dat[i]=True

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
    N = int(input())
    number = [0] * 1000005
    A = list(map(int,input().split()))
    for a in A:
        number[a] += 1
    
    for n in range(1000005):
        if number[n] == 0:
            continue
        for k in range(n + n,1000005,n):
            if number[k] > 0:
                number[k] = -1
    ans = 0
    for a in A:
        if number[a] == 1:
            ans += 1
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

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

lim = pow(10, 6)+3
ans = 0
judge = [False]*(lim)
index = 0
for i in range(n):
  if judge[a[i]] == True:
    continue
  if i != n-1 and a[i] == a[i+1]:
    pass
  else:
    ans += 1
  for j in range(a[i], lim, a[i]):
    judge[j] = True
print(ans)

Submission status: Accepted

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

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

    primes = set(A)
    for ind,i in enumerate(A):
        primes.difference_update(range(i*2, n+1, i))
        if ind>=1:
            if A[ind]==A[ind-1]:
                primes -= {i}
    print(len(primes))



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
import math
def eratos(A):
    isprime = [True for i in range(10**6+1)]
    # isprime[0] = False
    # isprime[1] = False
    for i in set(A):
        if isprime[i]:
            j = i + i
        while j <= 10**6:
            isprime[j] = False
            j = j + i
    return isprime        

N = int(input())
A = list(map(int, input().split()))
countA = Counter(A)
is_prime = eratos(A)
ans = 0
for ai in A:
    # print(ai)
    if is_prime[ai] and countA[ai] < 2:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]

x = [0] * (10 ** 6 + 10)
y = [0] * (10 ** 6 + 10)
for a in A :
  x[a] = 1
  y[a] += 1
  
for i in range(10 ** 6 + 1) :
  if x[i] == 0 : continue
  j = i * 2
  while j <= 10 ** 6 :
    x[j] = 0
    j += i

ret = 0
for i in range(10 ** 6 + 1) :
  if x[i] == 1 and y[i] == 1 :
    ret += 1
    
print(ret)

Submission status: Accepted

Solution code:
from collections import Counter

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

A.sort()

ans = 0
tmp = [True for i in range(A[-1] + 1)]

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

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N = I()
A = LI()

d = defaultdict(int)
for i in range(N):
    d[A[i]] += 1

b = [False]*(10**6+1)
for k in d.keys():
    if d[k]:
        b[k] = True

for i in range(10**6+1):
    if b[i]:
        for j in range(2*i,10**6+1,i):
            b[j] = False

for k in d.keys():
    if d[k] != 1:
        b[k] = False

count = 0
for i in range(10**6+1):
    if b[i]:
        count += 1

print(count)

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:
import sys
input=sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
d=[True]*(10**6+1)
a.sort()
ans=0
D={}
for i in a:
    if not i in D:
        D[i]=1
    else:
        D[i]+=1
for i in a:
    if not d[i]:
        continue
    if D[i]!=1:
        k=1
        while i*k<=10**6:
            d[i*k]=False
            k+=1
        continue
    ans+=1
    k = 1
    while i * k <=10 ** 6:
        d[i * k] = False
        k += 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
lis = set()
A.sort()
ans = 0
for i in range(N):
    if not A[i] in lis:
        if i == N-1:
            ans += 1
        else:
            if A[i] == A[i+1]:
                cnt = 1
                while A[i] * cnt <= int(1e6):
                    lis.add(A[i] * cnt)
                    cnt += 1
            else:
                ans += 1
                cnt = 1
                while A[i] * cnt <= int(1e6):
                    lis.add(A[i] * cnt)
                    cnt += 1
print(ans)

Submission status: Accepted

Solution code:
class Ruiseki_lr:
    """左右からの畳み込みをそれぞれ計算する"""
    def __init__(self, array, op, e):
        self.op = op
        self.e = e

        n = len(array)
        self.left = [e] * (n + 1)
        self.right = [e] * (n + 1)
        for i in range(n):
            self.left[i + 1] = self.op(self.left[i], array[i])
        for i in reversed(range(n)):
            self.right[i] = self.op(self.right[i + 1], array[i])

    def get_left(self, p):
        """区間[0, p)の畳み込み結果を返す"""
        return self.left[p]

    def get_right(self, p):
        """区間[p, n)の畳み込み結果を返す"""
        return self.right[p]

    def fold(self, p):
        """p番目を除いた区間[0, n)の畳み込み結果を返す"""
        return self.op(self.left[p], self.right[p + 1])


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

memo = {}
for i in range(n):
    if a[i] not in memo:
        memo[a[i]] = []
    memo[a[i]].append(i)

ans = [True] * n
used = set([])
for i in range(n):
    if a[i] in used:
        continue
    used.add(a[i])
    num = a[i]
    if len(memo[num]) >= 2:
        for j in memo[num]:
            ans[j] = False
    num += a[i]
    while num <= 10 ** 6:
        if num in memo:
            for j in memo[num]:
                ans[j] = False
        num += a[i]
res = 0
for i in ans:
    if i:
        res += 1
print(res)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = list(map(int,input().split()))
a.sort()
b = Counter(a)
ma = a[-1]

check = [True] * (ma+1)

ans = 0
for i in range(n):
    if check[a[i]]:
        if b[a[i]] == 1:
            ans += 1
            
        for j in range(a[i],ma+1,a[i]):
            check[j] = False
            
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin

t = int(input())
nums = list(map(int, stdin.readline().split()))
nums.sort()


n = nums[-1]

is_prime = [1]*(n+1)
small = nums[0]

d = dict()
for elem in nums:
    if elem not in d:
        d[elem] = 0
    else:
        is_prime[elem] = 0


# 3 8 11 16 24
for num in nums:
    # if num*num>n:
    #     break

    # if is_prime[num] == 0:
    #     continue

    for mult in range(2*num, n+1, num):
        is_prime[mult] = 0


print(sum([is_prime[i] for i in nums]))
# primes = [i for i in range(n+1) if is_prime[i]]
# print(*primes)

Submission status: Accepted

Solution code:
def solve():
    MAX = 1000001
    N = int(input())
    arr = list(map(int, input().split(" ")))
    arr.sort()
    is_ans = [True]*MAX
    ans = 0

    dup = set()
    for a in arr :
        if a in dup and is_ans[a] :
            j = a
            while j < MAX :
                is_ans[j] = False
                j += a

        dup.add(a)

    for a in arr :
        if is_ans[a]:
            ans += 1
            j = a
            while j < MAX :
                is_ans[j] = False
                j += a

    return ans

print(solve())

Submission status: Accepted

Solution code:
N=int(input())
A=sorted(map(int,input().split()))
dp=[1]*10**6
for a in A:
    if dp[a-1]==1:
        dp[a-1]=2
        for i in range(a*2,10**6+1,a):
            dp[i-1]=0
    elif dp[a-1]==2:
        dp[a-1]=0
print(sum([1 for a in A if dp[a-1]]))

Submission status: Accepted

Solution code:
import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7

N = INT()
A = LIST()
MAX = max(A)

S = set(A)
ok = [1] * (MAX+1)
for a in S:
    for x in range(a+a, MAX+1, a):
        ok[x] = 0

C = Counter(A)
for k, v in C.items():
    if v >= 2:
        ok[k] = 0

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

Submission status: Accepted

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

x = [False]*(10**6+1)

a.sort()
for i in range(1, n):
    if a[i] == a[i-1]:
        if x[a[i]]:
            continue
        else:
            x[a[i]] = True
            for r in range(a[i], 10 ** 6 + 1, a[i]):
                x[r] = True
ans = 0
for v in a:
    if x[v]:
        continue
    ans += 1
    for i in range(v, 10**6+1, v):
        x[i] = True

print(ans)

Submission status: Accepted

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

pre_a = 0
for a in A:
    if a == pre_a:
        S.discard(a)
    if a in S:
        j = a * 2
        while j <= M:
            S.discard(j)
            j += a
    pre_a = a

print(len(S))

Submission status: Accepted

Solution code:
import sys
import numpy as np
from collections import Counter

sys.setrecursionlimit(10 ** 7)

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

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

VALID = np.ones((10 ** 6) + 10, dtype=np.bool)

A.sort()
C = Counter(A)

multi = []
for k, v in C.items():
    if v > 1:
        multi.append(k)

for x in multi:
    VALID[x::x] = False


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

print(ans)

Submission status: Accepted

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

a.sort()
kouho = set(i for i in range(1, 10**6+1))
ans = 0
for i in range(n):
    ai = a[i]
    tasu = True
    if i < n-1:
        if ai == a[i+1]:
            tasu = False
    if ai not in kouho:
        continue
    while ai <= 10**6:
        if ai in kouho:
            kouho.remove(ai)
        ai += a[i]
    if tasu:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n=map(int,input().split()) #nは10**5だから全探索はできない

a=list(map(int,input().split()))
a.sort()
checked=[0]*(a[-1]+1)
cnt=0



for j,aa in enumerate(a):
    if checked[aa]==0:
        i=1
        if j+1<len(a) and aa==a[j+1]:
            cnt+=0
        else:
            cnt+=1
        
        

        #print(aa)
        while aa*i<a[-1]+1:
            checked[aa*i]=1
            i+=1
#print(checked)
#print(a)
print(cnt)

Submission status: Accepted

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

res = 0

from collections import defaultdict
D = defaultdict(int)

for i in range(N):
    D[A[i]] += 1

P = [0 for _ in range(10**6 + 1)]

for i in range(N):
    if P[A[i]]:
        continue
    if D[A[i]] == 1:
        res += 1
    for j in range(A[i], 10**6 + 1, A[i]):
        P[j] = 1

print(res)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
A.sort()
M = 10**6+1
is_prime = [True] * (M)
is_prime[0] = False

freq = dict()
for a in A:
    if a not in freq:
        freq[a] = 1
    else:
        freq[a] += 1
if 1 in freq and freq[1]>1:
    print(0)
    exit()
for i in A:
    if not is_prime[i]:
        continue
    for cur in range(i*2, M, i):
        is_prime[cur] = False
ans = 0
for a in A:
    if is_prime[a] and freq[a]==1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
ma = max(a)
d = [0 for i in range(ma+1)]
c = 0
for i in a:
    if d[i] == 2 or d[i] == 1:
        d[i] = 1
        continue
    for j in range(2*i, ma+1, i):
        d[j] = 1
    d[i] = 2
for i in a:
    if d[i] != 1:
        #print(i)
        c += 1
print(c)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
mx = max(a)
table = [0] * (mx + 1)
for x in a: table[x] += 1
#print(table)
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    #divisors.sort()
    return divisors

res = set(a)
#print(res)
for i in range(1, mx + 1):
  if table[i] == 0: continue
  for j in range(i, mx + 1, i):
    if i == j:
      if table[j] > 1:
        res.discard(j)
      continue
    if table[j]: res.discard(j)
print(len(res))

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
from functools import lru_cache
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7 

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N = int(input())
    A = read_list()
    A.sort()

    F = [True] * (A[-1] + 1)
    for i in range(N - 1):
        if A[i] == A[i + 1]:
            F[A[i]] = False

    res = 0
    for a in A:
        if F[a]:
            res += 1
        for b in range(a, len(F), a):
            F[b] = False

    print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
ok = [1]*(10**6+1)
ans = 0
for i in range(n):
    if ok[a[i]]:
        if i < n-1:
            if a[i+1] != a[i]:
                ans += 1
        else:
            ans += 1
        for j in range(1,10**6//a[i]+1):
            ok[a[i]*j] = 0
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = sorted(list(map(int, input().split())))
M = 1000001
D = [False]*M
ans = 0
for i, a in enumerate(A):
    if D[a]: continue
    if i==N-1 or A[i+1]>a : ans += 1
    b = a
    while b<M:
        D[b] = True
        b += a

print(ans)

Submission status: Accepted

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

freq = Counter(A)
if freq[1] == 1:
    print(1)
elif freq[1] >= 2:
    print(0)
else:
    bad = set()
    for k, v in freq.items():
        if v >= 2:
            bad.add(k)

    mx = max(A)

    for x in freq.keys():
        for times in range(2, 10 ** 6 + 1):
            if x * times > mx:
                break
            if x * times in freq:
                bad.add(x * times)

    count = 0
    for x in A:
        if x not in bad:
            count += 1
    print(count)

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
A = sorted(map(int, input().split()))
MAX_A = 10 ** 6
checked = np.zeros(MAX_A + 1, dtype=bool)

for i, a in enumerate(A):
    if not checked[a]:
        if i >= 1 and A[i - 1] == A[i]:
            checked[a] = True
        k = 2
        while a * k <= MAX_A:
            checked[a * k] = True
            k += 1

cnt = 0
for a in A:
    if not checked[a]:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
A = list(map(int,input().split()))
A.sort()
Amax = A[-1]

A = np.array(A)

judge = np.zeros(Amax+1,int)
judge[A]=1

for i in range(n):
    if not judge[A[i]]: continue
    if i<n-1 and A[i]==A[i+1]:
        judge[A[i]] = 0
    judge[np.arange(2,Amax//A[i]+1) * A[i]] = 0

print(judge.sum())

Submission status: Accepted

Solution code:
import math
import heapq,bisect
import sys
from collections import deque,defaultdict
from fractions import Fraction
mod=10**9+7
mod1=998244353
# ------------------------------warmup----------------------------
import os
import sys
from io import BytesIO, IOBase

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
# -------------------game starts now----------------------------------------------------import math
class SegmentTree1:
    def __init__(self, data, default=9999999, func=lambda a, b: min(a , b)):
        """initialize the segment tree with data"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()

        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __delitem__(self, idx):
        self[idx] = self._default

    def __getitem__(self, idx):
        return self.data[idx + self._size]

    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1

    def __len__(self):
        return self._len

    def query(self, start, stop):
        if start == stop:
            return self.__getitem__(start)
        stop += 1
        start += self._size
        stop += self._size

        res = self._default
        while start < stop:
            if start & 1:
                res = self._func(res, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res = self._func(res, self.data[stop])
            start >>= 1
            stop >>= 1
        return res

    def __repr__(self):
        return "SegmentTree({0})".format(self.data)

# -------------------game starts now----------------------------------------------------import math
class SegmentTree:
    def __init__(self, data, default=0, func=lambda a, b: a + b):
        """initialize the segment tree with data"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()

        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __delitem__(self, idx):
        self[idx] = self._default

    def __getitem__(self, idx):
        return self.data[idx + self._size]

    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1

    def __len__(self):
        return self._len

    def query(self, start, stop):
        if start == stop:
            return self.__getitem__(start)
        stop += 1
        start += self._size
        stop += self._size

        res = self._default
        while start < stop:
            if start & 1:
                res = self._func(res, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res = self._func(res, self.data[stop])
            start >>= 1
            stop >>= 1
        return res

    def __repr__(self):
        return "SegmentTree({0})".format(self.data)
#-------------------------------iye ha chutiya zindegi-------------------------------------
class Factorial:
    def __init__(self, MOD):
        self.MOD = MOD
        self.factorials = [1, 1]
        self.invModulos = [0, 1]
        self.invFactorial_ = [1, 1]

    def calc(self, n):
        if n <= -1:
            print("Invalid argument to calculate n!")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        if n < len(self.factorials):
            return self.factorials[n]
        nextArr = [0] * (n + 1 - len(self.factorials))
        initialI = len(self.factorials)
        prev = self.factorials[-1]
        m = self.MOD
        for i in range(initialI, n + 1):
            prev = nextArr[i - initialI] = prev * i % m
        self.factorials += nextArr
        return self.factorials[n]

    def inv(self, n):
        if n <= -1:
            print("Invalid argument to calculate n^(-1)")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        p = self.MOD
        pi = n % p
        if pi < len(self.invModulos):
            return self.invModulos[pi]
        nextArr = [0] * (n + 1 - len(self.invModulos))
        initialI = len(self.invModulos)
        for i in range(initialI, min(p, n + 1)):
            next = -self.invModulos[p % i] * (p // i) % p
            self.invModulos.append(next)
        return self.invModulos[pi]

    def invFactorial(self, n):
        if n <= -1:
            print("Invalid argument to calculate (n^(-1))!")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        if n < len(self.invFactorial_):
            return self.invFactorial_[n]
        self.inv(n)  # To make sure already calculated n^-1
        nextArr = [0] * (n + 1 - len(self.invFactorial_))
        initialI = len(self.invFactorial_)
        prev = self.invFactorial_[-1]
        p = self.MOD
        for i in range(initialI, n + 1):
            prev = nextArr[i - initialI] = (prev * self.invModulos[i % p]) % p
        self.invFactorial_ += nextArr
        return self.invFactorial_[n]


class Combination:
    def __init__(self, MOD):
        self.MOD = MOD
        self.factorial = Factorial(MOD)

    def ncr(self, n, k):
        if k < 0 or n < k:
            return 0
        k = min(k, n - k)
        f = self.factorial
        return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
#--------------------------------------iye ha combinations ka zindegi---------------------------------
def powm(a, n, m):
    if a == 1 or n == 0:
        return 1
    if n % 2 == 0:
        s = powm(a, n // 2, m)
        return s * s % m
    else:
        return a * powm(a, n - 1, m) % m
#--------------------------------------iye ha power ka zindegi---------------------------------
def sort_list(list1, list2):
    zipped_pairs = zip(list2, list1)

    z = [x for _, x in sorted(zipped_pairs)]

    return z
#--------------------------------------------------product----------------------------------------
def product(l):
    por=1
    for i in range(len(l)):
        por*=l[i]
    return por
#--------------------------------------------------binary----------------------------------------
def binarySearchCount(arr, n, key):
    left = 0
    right = n - 1

    count = 0

    while (left <= right):
        mid = int((right + left) / 2)

        # Check if middle element is
        # less than or equal to key
        if (arr[mid] <= key):

            # At least (mid + 1) elements are there
            # whose values are less than
            # or equal to key
            count = mid + 1
            left = mid + 1

        # If key is smaller, ignore right half
        else:
            right = mid - 1

    return count
#--------------------------------------------------binary----------------------------------------
def countdig(n):
    c=0
    while(n>0):
        n//=10
        c+=1
    return c
def countGreater(arr, n, k):
    l = 0
    r = n - 1

    # Stores the index of the left most element
    # from the array which is greater than k
    leftGreater = n

    # Finds number of elements greater than k
    while (l <= r):
        m = int(l + (r - l) / 2)

        # If mid element is greater than
        # k update leftGreater and r
        if (arr[m] > k):
            leftGreater = m
            r = m - 1

        # If mid element is less than
        # or equal to k update l
        else:
            l = m + 1

    # Return the count of elements
    # greater than k
    return (n - leftGreater)
#--------------------------------------------------binary----------------------------------------
n=int(input())
l=list(map(int,input().split()))
l.sort()
c=dict()
for i in range(n):
    if l[i] in c:
        c[l[i]]+=1
    else:
        c.update({l[i]:1})
ma=l[-1]
d=defaultdict(int)
ans=[0]*n
for i in range(n):
    if d[l[i]]==0:
        ans[i]=1
        for j in range(l[i],ma+1,l[i]):
            d[j]=-1
        if c[l[i]]>1:
            ans[i]=0
#print(ans)
print(sum(ans))

Submission status: Accepted

Solution code:
from itertools import islice
def solve(A):
    memo = [0]*(10**6+1)

    for a in A:
        memo[a] += 1
    if memo[1] > 0:
        return 1 if memo[1] == 1 else 0

    res = 0
    for i,v in enumerate(islice(memo,2,None),start=2):
        if v > 0:
            res += 1 if v == 1 else 0
            j = i
            while j <= 10**6:
                memo[j] = 0
                j += i
    return res

if __name__ == '__main__':
    N = int(input())
    A = list(map(int,input().split()))
    print(solve(A))

Submission status: Accepted

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


def solve(N: int, A: "List[int]"):
    from collections import Counter
    M = max(A)
    C = Counter(A)
    table = [False] * (M + 1)
    for c in C:
        for j in range(c+c, M + 1, c):
            table[j] = True
    ans = 0
    for a in A:
        if table[a] or C[a] > 1:
            continue
        ans += 1
    return ans


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    print(solve(N, A))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()