Problem:


Score : 400 points

Problem Statement

Given is a number sequence A of length N.

Find the number of integers i \left(1 \leq i \leq N\right) with the following property:

For every integer j \left(1 \leq j \leq N\right) such that i \neq j , A_j does not divide A_i.

Constraints

All values in input are integers.

1 \leq N \leq 2 \times 10^5

1 \leq A_i \leq 10^6

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answer.

Sample Input 1

5
24 11 8 3 16

Sample Output 1

3

The integers with the property are 2, 3, and 4.

Sample Input 2

4
5 5 5 5

Sample Output 2

0

Note that there can be multiple equal numbers.

Sample Input 3

10
33 18 45 28 8 19 89 86 2 4

Sample Output 3

5



Sample input:
5
24 11 8 3 16


Sample output:
3

Submission status: Accepted

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
D = set() #重複
S = set() #初出
for i in range(N):
    if A[i] in S:
        D.add(A[i])
    else:
        S.add(A[i])
#print(D,S)
M = max(S)
#print(M)
X = [1 for i in range(M+1)] #i番目が数字iに対応、条件を満たせば1、満たさなければ0にする。
#print(X)
for a in S:
    if a in D:
        X[a]=0 #aが重複していれば、aは条件を満たす数字ではない。
    for i in range(2*a,M+1,a):
        X[i]=0 #aはおｋ、2a以上のaの倍数は条件を満たさない。
        
ans = 0
for i in range(N):
    if X[A[i]]==1: #数字A(i)に対応するX[i]の箇所を参照して、条件を満たしていれば+1する
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
nums = [int(e) for e in input().split()]
import numpy as np

ans= np.zeros(max(nums)+1)

for i in nums:
    if ans[i] >1:
        continue
    else:
        ans[i::i] +=1

cnt = 0
for i in nums:
    if ans[i] ==1:
        cnt +=1

print(cnt)

Submission status: Accepted

Solution code:
import numpy as np
import sys
def input(): return sys.stdin.readline().strip()

n = int(input())
As = list(map(int, input().split()))
ans = n
val = 10 ** 6
table = np.array([0] * (val + 1))
for a in As:
    if table[a] > 1:
        continue
    table[::a] += 1
for a in As:
    ans -= (table[a] > 1)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
a.append(0)
b = {}
c = 0
for i in range(n):
    if a[i] not in b:
        for j in range(1, 10**6//a[i]+1):
            b[a[i]*j] = 1
        if a[i] != a[i+1]:
            c += 1
print(c)

Submission status: Accepted

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

for i in A:
    if cnt[i] != 0:
        cnt[i] = 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:
'''
方針
    1 ～ 10^6(Aの最大値) までの全ての数について、割り切れる数をカウント
    カウント == 1 ならば、他の数では割り切れないので、そのような数の個数が答え

工夫
    そのままの実装では、最悪ケース : 1 1 1 1 ... で、TLEする
    対策として、
        1. Aを昇順ソートする
        2. A[i]がA[i-1]と同じならば、2倍以上の倍数についてはスキップ
    とする
'''

import numpy as np

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    d = np.zeros(A[-1]+1, dtype=np.uint64)  # 約数カウント。配列長さは、Aの最大値+1 で十分
    for i in range(N):
        a = A[i]
        a1 = A[i-1]
        if a != a1:     # 初出の数なら
            d[a::a] += 1    # aからaごとに+1する (範囲内の全ての倍数に、約数カウント+1)
        else:           # 重複なら
            d[a] += 1       # 自身のカウントを上げるだけで十分 (2倍以上はスキップ)
    print(np.count_nonzero(d[A] == 1))  # Aのうち、約数カウントが1となったものの個数が答え

main()

Submission status: Accepted

Solution code:
_,*a = map(int, open(0).read().split())
a.sort()
m = -~a[-1]
c = [0]*m
for i in a:
    c[i] += 1
    if c[i] > 1:
        continue
    for j in range(i * 2, m, i):
        c[j] = 2
print(sum(c[i]==1for i in a))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

def get_primes(n):
    ps = [2]
    for i in range(3, n, 2):
        for p in ps:
            if i%p == 0:
                break
        else:
            ps.append(i)
    return ps


Yes = 'Yes'
No = 'No'


import numpy as np
def main():
    N=ii()
    A=lmis()
    A.sort()
    d = np.zeros(A[-1]+1, dtype=np.uint8)
    for i in range(N):
        a = A[i]
        pa = A[i-1]
        if a != pa:
            d[a::a] += 1
        else:
            d[a] += 1
    print(sum(d[a]==1 for a in A))

main()

Submission status: Accepted

Solution code:
# %%time
# from collections import Counter

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

# A=list(range(2,10**6))

# counter = Counter(A)

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

for i in A:
    if dp[i]!=0:
        dp[i]+=1
        continue
    for j in range(1*i,max+1,i):
        dp[j]+=1
        
ans=[]
for a_idx,a in enumerate(A):
    if dp[a] == 1:
        ans.append(a)
        
print(len(ans))

Submission status: Accepted

Solution code:
import collections

n=int(input())
arr=list(map(int,input().split()))
arr=sorted(arr)
s=set()
cnt=collections.Counter(arr)

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

print(ans)

Submission status: Accepted

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

for i in range(n):
  c[a[i]] -= 1
  for j in range(a[i],(kmax+1),a[i]):
    c[j] += 2

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

A = [i for i in map(int, input().split())]
A.sort()
Amax = A[-1]

dp = [1]*(Amax+1)
ans = 0


for i in range(len(A)-1):
    p = A[i]
    if dp[p] == 1:
        for q in range(Amax//p+1):
            dp[p*q] = 0
        if A[i] != A[i+1]:
            ans += 1
if dp[Amax] == 1:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
List = list(map(int, input().split()))
res = 0
List.sort()
K = List[N-1]+1
Flag = [1]*K
for i in range(N):
  if Flag[List[i]] ==1:
    res +=1
    for j in range(List[i],K,List[i]):
      Flag[j] = 0
    if i != N-1 and List[i] == List[i+1]:
      res += -1
print(res)

Submission status: Accepted

Solution code:
from sys import stdin

import numpy as np

U = 10 ** 6 + 10


def main():
    readline = stdin.readline
    N = int(readline())
    a = list(map(int, readline().split()))
    ret = 0
    exist_counts = [0] * U
    for x in a:
        if exist_counts[x]:
            exist_counts[x] = 2
            continue
        idx = x
        while idx < U:
            exist_counts[idx] += 1
            idx += x
    for x in a:
        ret += exist_counts[x] == 1
    print(ret)
main()

Submission status: Accepted

Solution code:
from collections import Counter


n = int(input())
a = list(map(int, input().split()))
c = Counter(a) # Count num and construct dictionary
c = sorted(c.items(), key=lambda x:x[0]) # align key
ans = 0
isOK = [True] * (10**6+1)

for k, v in c:
    if not isOK[k]:
        continue

    if v > 1:
        for i in range(k, len(isOK), k):
            isOK[i] = False
        continue

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

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
Alist = [int(x) for x in input().split()]
M = max(Alist)
A0 = ['NotUse']
Abool = A0 + [0 for x in range(M)]
Alist.sort()
ans = 0

for i in Alist:
    for j in range(i,M+1,i):
        if Abool[j] >= 2:
            None
        else:
            Abool[j] += 1
    
for i in Alist:
    if Abool[i] == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:

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

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

from collections import Counter
cnt = Counter(a)

if a[0]==1:
    if cnt[1]==1:
        print(1)
    else:
        print(0)
    exit()

limit = a[-1]
is_prime = [0] * (limit + 1)

for aa in a:
    is_prime[aa]=1

for i in range(2, limit + 1):

    if is_prime[i]==0:
        continue
    for j in range(i * 2, limit + 1, i):
        is_prime[j] = 0

ans=0

for i in range(1,limit+1):
    if is_prime[i] and cnt[i] < 2:
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
l = list(map(int,input().split()))
l.sort();

ans = [0]*(l[n-1]+1)
p=0

while(p<n):
     
    for i in range(l[p],l[n-1]+1,l[p]):
        ans[i]+=1
    p+=1
   
    

c=0
#print(ans)
for i in l:
    if(ans[i]==1):
        c+=1
print(c)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
if a[0] == 1:
    if n > 1:
        if a[1] == 1:
            print(0)
            exit()
    print(1)
    exit()

p = [False for i in range(a[-1]+1)]
kaburi = set()
for i in range(n):
    if p[a[i]]:
        kaburi.add(a[i])
    p[a[i]] = True

for i in range(2,a[-1]+1):
    if not p[i]:
        continue
    for j in range(i*2,a[-1]+1,i):
        p[j] = False
ans = 0
for i in range(a[-1]+1):
    if p[i] and not i in kaburi:
        ans += 1
print(ans)

Submission status: Accepted

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

a.sort()
amax=a[-1]
boo = [0]*(amax+1)
from collections import Counter
c=Counter(a)

for aa in a:
    if boo[aa]==0:
        if c[aa]>=2:
            for i in range(aa,amax+1,aa):
                boo[i]=1
        else:
            for i in range(aa*2,amax+1,aa):
                boo[i]=1

print( n-sum(boo[aa] for aa in a))

Submission status: Accepted

Solution code:
"""
    Satwik_Tiwari ;) .
    16 june , 2020  - Tuesday
"""

#===============================================================================================
#importing some useful libraries.
from __future__ import division, print_function

from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase


import bisect
from heapq import *
from math import *
from collections import deque
from collections import Counter as counter  # Counter(list)  return a dict with {key: count}
from itertools import combinations as comb # if a = [1,2,3] then print(list(comb(a,2))) -----> [(1, 2), (1, 3), (2, 3)]
from itertools import permutations as permutate
from bisect import bisect_left as bl
#If the element is already present in the list,
# the left most position where element has to be inserted is returned.
from bisect import bisect_right as br
from bisect import bisect
#If the element is already present in the list,
# the right most position where element has to be inserted is returned

#==============================================================================================

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")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

# inp = lambda: sys.stdin.readline().rstrip("\r\n")

#===============================================================================================
#some shortcuts

mod = 1000000007
def inp(): return sys.stdin.readline().rstrip("\r\n") #for fast input
def out(var): sys.stdout.write(str(var))  #for fast output, always take string
def lis(): return list(map(int, inp().split()))
def stringlis(): return list(map(str, inp().split()))
def sep(): return map(int, inp().split())
def strsep(): return map(str, inp().split())
def graph(vertex): return [[] for i in range(0,vertex+1)]
def zerolist(n): return [0]*n
def nextline(): out("\n")  #as stdout.write always print sring.
def testcase(t):
    for p in range(t):
        solve()
def printlist(a) :
    for p in range(0,len(a)):
        out(str(a[p]) + ' ')
def lcm(a,b): return (a*b)//gcd(a,b)
def power(a,b):
    ans = 1
    while(b>0):
        if(b%2==1):
            ans*=a
        a*=a
        b//=2
    return ans
def ncr(n,r): return factorial(n)//(factorial(r)*factorial(max(n-r,1)))
def isPrime(n) : # Check Prime Number or not
    if (n <= 1) : return False
    if (n <= 3) : return True
    if (n % 2 == 0 or n % 3 == 0) : return False
    i = 5
    while(i * i <= n) :
        if (n % i == 0 or n % (i + 2) == 0) :
            return False
        i = i + 6
    return True

#===============================================================================================
# code here ;))

def solve():
    n = int(inp())
    a = lis()
    # if(a.count(1) > 0):
    #     print(0)
    #     return
    m = max(a)
    cnt = [0]*(m+1)

    for i in range(0,n):
        num = a[i]
        for j in range(num,m+1,num):
            cnt[j] +=1
        # print(num,cnt)
    ans= 0
    for i in range(n):
        if(cnt[a[i]] == 1):
            # print(a[i])
            ans +=1
    print(ans)





testcase(1)
# testcase(int(inp()))

Submission status: Accepted

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

# 解説の通りに実装
num_max = 10 ** 6 + 5  # 制限の上限で配列を用意しておく（わざわざmax()の計算しない）
exist_counts = [0] * num_max
for num in nums:
  # すでにcountされてる場合、重複であることだけ残して抜ける
  if exist_counts[num]:
    exist_counts[num] = 2
    continue
  # はじめてのcountであれば、自分自身とその倍数にチェックをつける
  idx = num
  while idx < num_max:
    exist_counts[idx] += 1
    idx += num

# 各numについて、count=1ならば条件を満たしたということ
count = 0
for num in nums:
  if exist_counts[num] == 1:
    count += 1
print(count)

Submission status: Accepted

Solution code:
N=int(input())
A=sorted(list(map(int,input().split())))
dp=[True for i in range(A[-1])]
ans=0
i=0
j=-1
while i<N:
  if i+1<N:
    while A[i]==A[i+1]:
      i+=1
      if i+1==N:
        break
  if dp[A[i]-1] and i-j==1:
    ans+=1
  for k in range(2*A[i],A[-1]+1,A[i]):
    dp[k-1]=False
  j=i
  i+=1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    MAX = A[-1]
    dp = [1] * (MAX + 5)
    ANS = 0
    for i in range(N):
        if dp[A[i]] == 0:
            continue
        for j in range(MAX+1):
            if A[i]*j > MAX:
                break
            dp[A[i]*j] = 0
        dp[A[i]] = 0
        if i < N-1 and A[i] == A[i+1]:
            continue
        ANS += 1
    print(ANS)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
number = int(input())
# values = [i+2 for i in range(2*10**5)]
values = list(map(int, input().split()))

maxV = 10**6+1
dp = [0]*(maxV)

for a in values:
    i = 1
    if dp[a] > 0:
        dp[a] = dp[a] + 1
        continue
    while i * a < maxV:
        i_a = i * a
        dp[i_a] = dp[i_a] + 1
        i += 1

count = 0
for a in values:
    if dp[a] == 1:
        count+=1

print(count)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = list(map(int, input().split())) 
ans = set(A)
for k, v in Counter(A).items():
    if v != 1:
        ans.discard(k)
    temp = {k*i for i in range(2,10**6//k + 1)}
    ans -= ans&temp
print(len(ans))

Submission status: Accepted

Solution code:
#maspyさんを参考に
import sys
#import numpy as np
#from numba import njit
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# この最適化がよくわからん。Numpyループなら行けるらしい
# 400msくらいは最低でもかかるけど、N=10^5でも2でも変わらんと言う
#@njit('(i4[::1],)', cache=True)
def solve(A):
  # エラトステネス古いって値側のバリエーションとして配列をとるんや
  # maxA = 10**6って言うのがポイントっぽいなあ。。
    count = np.zeros(10**6 + 10, np.int32)
    for x in A:
        if count[x] > 1:
            continue
        count[::x] += 1
    ret = 0
    for x in A:
        ret += count[x] == 1
    return ret

def solve2(A):
  count = [0 for _ in range(10**6 + 10)]
  for x in A:
    if count[x] > 1:
      continue
    for a in range(0,len(count),x):
      count[a] += 1
  ret = 0
  for x in A:
    ret += (1 if count[x] == 1 else 0)
  #print(count[:24])
  return ret
  
# このコードわからなかった。一行目のNをSKIPしたリストになっている。。
#A = np.array(read().split(), np.int32)[1:]
N = int(input())
A = list(map(int, input().split()))
# この手法だとソート不要なのか？？だから早いのか？？
print(solve2(sorted(A)))

Submission status: Accepted

Solution code:
#maspyさんを参考に
import sys
#import numpy as np
#from numba import njit
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# この最適化がよくわからん。Numpyループなら行けるらしい
# 400msくらいは最低でもかかるけど、N=10^5でも2でも変わらんと言う
#@njit('(i4[::1],)', cache=True)
def solve(A):
  # エラトステネス古いって値側のバリエーションとして配列をとるんや
  # maxA = 10**6って言うのがポイントっぽいなあ。。
    count = np.zeros(10**6 + 10, np.int32)
    for x in A:
        if count[x] > 1:
            continue
        count[::x] += 1
    ret = 0
    for x in A:
        ret += count[x] == 1
    return ret

def solve2(A):
  count = [0 for _ in range(10**6 + 10)]
  for x in A:
    if count[x] > 1:
      continue
    for a in range(0,len(count),x):
      count[a] += 1
  ret = 0
  for x in A:
    ret += (1 if count[x] == 1 else 0)
  #print(count[:24])
  return ret
  
# このコードわからなかった。一行目のNをSKIPしたリストになっている。。
#A = np.array(read().split(), np.int32)[1:]
N = int(input())
A = list(map(int, input().split()))
# この手法だとソート不要なのか？？だから早いのか？？
print(solve2(A))

Submission status: Accepted

Solution code:
import sys
import numpy as np
#from numba import njit
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
#@njit('(i4[::1],)', cache=True)
def solve(A):
    count = np.zeros(10**6 + 10, np.int32)
    for x in A:
        if count[x] > 1:
            continue
        count[::x] += 1
    ret = 0
    for x in A:
        ret += count[x] == 1
    return ret

A = np.array(read().split(), np.int32)[1:]
 
print(solve(A))

Submission status: Accepted

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

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

max_a = max(a)
c = {a_tmp: 0 for a_tmp in a}
for a_tmp in a:
    c[a_tmp] += 1

d = {a_tmp: 0 for a_tmp in a}
for a_tmp in a:
    if c[a_tmp] > 0:
        t = 2
        while a_tmp*t <= max_a:
            d[a_tmp*t] = 1
            t += 1
ans = 0
for a_tmp in a:
    if c[a_tmp] == 1 and d[a_tmp] == 0:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import groupby

readline = sys.stdin.buffer.readline
readline()
b = list(map(int, readline().split()))

b.sort()
# print(b)

x = len(b)
c = [(k, len(tuple(L))) for k, L in groupby(b)]
# print(c)
m = c[-1][0]
# print(m)
s = [True] * (m + 1)
# print(len(s))

a = 0
for i, le in c:
  if s[i]:
    if le <= 1:
      a += 1
    for v in range(i, m + 1, i):
      s[v] = False
# print(s)
print(a)

Submission status: Accepted

Solution code:
import numpy as np
import sys
input = sys.stdin.buffer.readline

N = int(input())
A = list(map(int, (input().split())))
A.sort()
cnt = np.zeros(10**6+10, dtype=np.int32)
for x in A:
    if cnt[x] != 0:
        cnt[x] = 2
        continue
    cnt[x::x] += 1
ans = 0
for x in A:
    if cnt[x] == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
A=int(input())
S=list(map(int,input().split()))
tmp=set()
aft=set()
for i in S:
   if i in aft:
      tmp.add(i)
   else:
      aft.add(i)
n=max(S)+1
DP=[1]*n
for i in aft:
   if i in tmp:
      DP[i]=0
   for j in range(2*i,n,i):
      DP[j]=0
ans=0
for i in S:
   ans+=DP[i]
print(ans)

Submission status: Accepted

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

A.sort()
mx = A[n-1]
dp = [0]*(mx+1)
for a in A:
    for j in range(a,mx+1,a):
        dp[j]+=1
        
sum = 0
for i in A:
    if dp[i]==1:
        sum+=1
print(sum)

Submission status: Accepted

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

a.sort()
a_set = set(a)
for i in range(n-1):
    if a[i] == a[i + 1]:
        if a[i] in a_set:
            a_set.remove(a[i])

ma = max(a)

dp = [True for _ in range(ma + 1)]
ans = 0
y = -1
for x in a:
    if x == y:
        continue
    y = x

    if x in a_set:
        ans += 1 if dp[x] else 0

    while y <= ma:
        dp[y] = False
        y += x

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

_ = int(input())
A = list(map(int, input().split()))
a_max = 10 ** 6

c = Counter(A)
b = list(set(A))
b.sort()

dp = [True] * (a_max + 1)
ans = 0
for a in b:
    if dp[a]:
        if c[a] == 1:
            ans += 1
        for i in range(2 * a, a_max + 1, a):
            dp[i] = False

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort()
max_a=A[-1]
dp=[True]*(max_a+1)
ans=0
for i in range(N):
  a=A[i]
  #print(a)
  if dp[a]==True: 
    if i==N-1:
      ans+=1
    elif a!=A[i+1]:
      ans+=1
    
    k=a
    while k<=max_a:
      dp[k]=False    
      k+=a
print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

div = [0] * 1000005

N = int(input())

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

for num in A:
    if div[num] == 0:
        for i in range(num, 1000004, num):
            div[i] += 1
    elif div[num] != 0:
        div[num] += 1        

ans = 0

for num in A:
    if div[num] == 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
nums = [i for i in map(int, input().split())]
nums = sorted(nums)
max = nums[-1]
dp = [1]*(max+1)
ans = 0

for i in range(len(nums)-1):
    p = nums[i]
    if dp[p] ==1:
        for q in range(max//p+1):
            dp[p*q]=0
        if nums[i] != nums[i+1]:
            ans+=1
if dp[max]==1:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
N = I()
A = readInts()
import collections
dic = collections.Counter(A)
A = set(A)
is_prime = [True] * (10**6+1)
for a in A:
    if is_prime[a]:
        for v in range(a*2,10**6+1,a):
            is_prime[v] = False
cnt = 0
for a in A:
    if is_prime[a]:
        cnt += 1
for k,v in dic.items():
    if v >= 2 and is_prime[k]:
        cnt -= 1
print(cnt)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

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

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

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




    
resolve()

Submission status: Accepted

Solution code:
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
from math import cos,sin,tan,sqrt
import cmath as cma
import copy as cp
import sys
import re
sys.setrecursionlimit(10**7)
EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf
MOD = 10**9 + 7

def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def adj(n): return [[] for _ in range(n)]

n = iinput()
a = iarr()
amax = max(a)

# ふるって生き残ったやつがTrue
dp = [1 for i in range(amax+1)]
for num in a:
    for i in range(2, amax//num + 1):
        tmp = num * i
        if dp[tmp]: dp[tmp] = 0

# カウンター
cnt = col.Counter(a)

# 生き残っていて、かつ、１回だけ登場するやつ
ans = 0
for key,val in cnt.items():
    if dp[key] and val==1: ans += 1

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
MAX = max(A)
dp = [True for _ in range(MAX+1)]

for a in set(A):
    for k in range(2*a,MAX+1,a):
        dp[k] = False
B = sorted(A)
for i in range(len(B)-1):
    if B[i] == B[i+1]:
        dp[B[i]] = False

print(sum(dp[a] for a in set(A)))

Submission status: Accepted

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

sortList = sorted(AList)
Amax = max(sortList)

dp = [0]*(Amax+1)

for n in sortList:
  dp[n] += 1
  if dp [n] == 1:
    for i in range(n*2, Amax+1, n):
      dp[i] += 2

print(dp.count(1))

Submission status: Accepted

Solution code:
#写経
#https://atcoder.jp/contests/abc170/submissions/14363499
import sys

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)
resolve()