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())
if n==1:
    print(1)
else:
    oklist=[True for i in range(1000001)]
    l=[int(i) for i in input().split()]
    l.sort()
    res=0
    for i in range(n):
        if oklist[l[i]]:
            if i==n-1 or (i<n-1 and l[i]!=l[i+1]):
                res+=1
            for j in range(1,1000001):
                if l[i]*j<=1000000:
                    oklist[l[i]*j]=False
                else:
                  break
    print(res)

Submission status: Accepted

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
from decimal import Decimal
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

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

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

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

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

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

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

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

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

# ここから書き始める
n = int(input())
a = sorted(list(map(int, input().split())))
m = max(a)
dp = [0 for i in range(m + 1)]
for i in a:
    cnt = 1
    while i * cnt <= m:
        dp[i * cnt] += 1
        cnt += 1
ans = 0
# print("dp =", dp)
for i in range(n):
    if i > 0 and a[i] == a[i - 1]:
        continue
    if dp[a[i]] <= 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def main():
    max_num = 10**6
    N = int(input())
    A = list(map(int, input().split()))
    M = {}
    for a in A:
        if a not in M:
            M[a] = 0
        M[a] += 1
    B = sorted(set(A))
    S = [0]*(max_num + 1)
    ans = 0

    for b in B:
        if S[b] != 0:
            continue
        if M[b] == 1:
            ans += 1
        v = b
        while v <= max_num:
            S[v] = 1
            v += b
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter

def main():
    n = int(input())
    a = sorted([int(i) for i in input().split()])
    table = [True for i in range(max(a))]
    res = 0
    amax = max(a)

    for i in a:
        if table[i-1] is False:
            continue
        for j in range(i*2, amax+1, i):
            table[j-1] = False

    c = Counter(a)
    for i in set(a):
        if table[i-1]:
            if c[i] == 1:
                res += 1
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter

def main():
    n = int(input())
    a = sorted([int(i) for i in input().split()])
    table = [True for i in range(max(a))]
    res = 0
    amax = max(a)

    for i in a:
        if (amax/2) + 1 < i:
            break
        if table[i-1] is False:
            continue
        for j in range(i*2, amax+1, i):
            table[j-1] = False

    c = Counter(a)
    for i in set(a):
        if table[i-1]:
            if c[i] == 1:
                res += 1
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections

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

c=[0 for _ in range(M+1)]

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

answer = 0

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


print(answer)

Submission status: Accepted

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

amax = a[-1]
dp = [True] * (amax+1)
ans = 0
for x in range(len(a)-1):
   i = a[x]
   if dp[i] == True:
      for j in range(amax//i+1):
         dp[i*j] = False
      if a[x] != a[x+1]:
         ans += 1
if dp[amax] == 1:
   ans += 1
print(ans)

Submission status: Accepted

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

cnt = [0] * 1000001

for i in A:
  if cnt[i] == 1:
    continue 
  if cnt[i] == 2:
    cnt[i] = 1
    continue
  cnt[i] = 2
  for j in range( (i+i),1000001,i):
    cnt[j] = 1
#
ans = 0
for i in range(1000001):
  if cnt[i] == 2:
    ans += 1
#
print(ans)

Submission status: Accepted

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

max_a = max(a)
l = [0] * max_a

for i in range(n):
  j = 1
  while a[i] * j - 1 < max_a:
    l[a[i] * j - 1] += 1
    j += 1

count = 0

for i in range(n):
  if l[a[i] - 1] == 1:
    count += 1

print(count)

Submission status: Accepted

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

A.sort()

l = [0] * (A[N - 1] + 1)

for i in A:
        j = i 
        while j <= A[N - 1]: 
                l[j] += 1
                j += i 

cnt = 0 
for k in A:
        if l[k] == 1:
                cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
def main():
  n=int(input())
  a=sorted(map(int,input().split()))
  maxa=a[-1]+1
  tf=[False]*maxa
  r=0
  n-=1
  for i in range(n):
    a_i=a[i]
    if tf[a_i] ==False:
      for j in range(a_i,maxa,a_i):
        tf[j]=True
      if a_i < a[i+1]:
        #print(a_i)
        r+=1
  if tf[-1] ==False:
    r+=1
  print(r)
main()

Submission status: Accepted

Solution code:
#15:34
n = int(input())
a = list(map(int,input().split()))
a.sort()
b = [0 for _ in range(10**6+1)]
ans = 0
for i in range(n):
  if b[a[i]]:
    continue
  now = int(a[i])
  ans += 1
  while True:
    try:
      b[now] = 1
      now += a[i]
    except:
      break
  if i != n-1:
    if a[i+1] == a[i]:
      ans -= 1
print(ans)

Submission status: Accepted

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

l = [0]*(a[-1] + 1)

for i in range(n):
  l[a[i]] += 1

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

print(ans)

Submission status: Accepted

Solution code:
import collections

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

dp = collections.defaultdict(lambda: True)

for i in range(N):
    if i < N - 1 and A[i] == A[i + 1]:
        dp[A[i]] = False
    k = 2
    while True:
        if A[i] * k > A[-1]:
            break
        else:
            dp[A[i] * k] = False
            k += 1

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

Submission status: Accepted

Solution code:
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)
  
  for i in range(N):
    a = A[i]
    a1 = A[i-1]
    if a != a1:
      d[a::a] += 1
    else:
      d[a] += 1
  print(np.count_nonzero(d[A] == 1))
  
main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

for a in A:
    dp[a] += 1

for i in range(1, len(dp)):
    if dp[i]:
        for j in range(i+i, len(dp), i):
            dp[j] = 0
print(dp.count(1))

Submission status: Accepted

Solution code:
# D - Not Divisible
N = int(input())
a = list(map(int, input().split()))
a.sort()
MAX = a[-1]
l = [0]*(MAX+1)
for i in range(N):
    l[a[i]] += 1
    
answer = 0
for i in range(N):
    if l[a[i]] == 1:
        answer += 1
    for g in range(a[i], MAX+1, a[i]):
        l[g] = 10
print(answer)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
MAX = a[-1]
l = [0]*(MAX+1)
for i in range(n):
    l[a[i]] += 1

ans = 0
for i in range(n):
    if l[a[i]] == 1:
        ans += 1
    for g in range(a[i], MAX+1, a[i]):
        l[g] = 10

print(ans)

Submission status: Accepted

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

a.sort()
Max = a[-1]
memo = [1] * (Max+1)
count = 0

# i<n-1
for i in range(n-1):
    t = a[i]
    if memo[t] == 1:
        if a[i] != a[i+1]:
            count += 1
        for j in [t*k for k in range(1, Max//t+1)]:
            memo[j] = 0
# i=n-1
if memo[a[n-1]] == 1:
    count += 1

print(count)

""" #Time over
a.sort(reverse=True)

count = 0
# i<n-1
for i in range(n-1):
    if a[i] != a[i+1] and a[i] != a[i-1]:
        for j in range(n-1, i, -1):
            if a[i] % a[j] == 0:
                break
            if j == i+1:
                count += 1

# i==n-1
if a[n-2] != a[n-1]:
    count += 1

if n != 1:
    print(count)
elif n == 1:
    print(1)
"""

Submission status: Accepted

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

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

for a in A:
    dp[a] += 1

for i in range(1, len(dp)):
    if dp[i]:
        for j in range(i+i, len(dp), i):
            dp[j] = 0
print(dp.count(1))

Submission status: Accepted

Solution code:
import sys
from collections import Counter
N = int(input())
As = list(map(int,input().split()))
ct = Counter(As)
As =sorted(As)
max_dp = As[-1] +1
dp = [True] * max_dp
for key,count in ct.items():
	if count > 1:
		dp[key] = False
		i = 2
		while key*i < max_dp:
			dp[key*i] = False
			i+=1
for A in As:
	if dp[A] == True:
		i = 2
		while A*i < max_dp:
			dp[A*i] = False
			i+=1

ans = 0
# print(len(dp))
for A in As:
	# print(A)
	if dp[A]:
		ans+=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)         #Aの最大値までのエラトステネスの篩を作る。
ans = 0
for i in range(len(A)-1):
  p = A[i]
  if dp[p] == 1:          #A[i]がA[j]の倍数でないかをエラトステネスの篩でチェック
    for q in range(Amax//p+1):
      dp[p*q] = 0         #A[i]の倍数をすべて0にする
    if A[i] != A[i+1]: 
      ans += 1            #A[i]が重複していなければカウント
if dp[Amax] == 1:         #重複チェック時にレンジオーバーするためAmaxだけ別で判定 
  ans += 1
print(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:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


N = int(input())
A = list(map(int, input().split()))
M = 10**6 + 5
cnt = [0] * M

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

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque, Counter
#import bisect
#import heapq
#import math
#from itertools import accumulate
#from itertools import permutations as perm
#from itertools import combinations as comb
#from itertools import combinations_with_replacement as combr
#from fractions import gcd
#import numpy as np

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18

def main():
    N = int(stdin.readline().rstrip())
    #A, B, C = map(int, stdin.readline().rstrip().split())
    A = list(map(int, stdin.readline().rstrip().split()))
    A.sort()
    C = Counter(A)
    cannot = set()
    L= max(A)
    ans = 0
    for a in A:
        if a in cannot: continue
        if C[a] == 1:
            ans += 1
        ind = 1
        while a*ind <= L:
            cannot.add(a*ind)
            ind += 1

    print(ans)

main()

Submission status: Accepted

Solution code:
import sys
import numpy as np


def solve(sequence):

    sequence.sort()

    max_v = sequence[-1]

    dp = [True] * (max_v + 1)

    previous = -1
    for v in sequence:
        if v == previous:
            dp[v] = False
            continue

        previous = v

        if not dp[v]:
            continue

        for iv in range(2 * v, max_v+1, v):
            dp[iv] = False

    count = 0
    for v in sequence:
        if dp[v]:
            count += 1

    return count


# if sys.argv[-1] == 'ONLINE_JUDGE':
#     from numba.pycc import CC
#     cc = CC('my_module')
#     cc.export('main', '(i8[::1])')(solve)
#     cc.compile()
#     exit()
#
#
# from my_module import solve


def main():
    _ = input()
    sequence = np.array(input().split(), np.int64)
    print(solve(sequence))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
An = list(map(int, input().split()))
An.sort()
max_n = max(An)
dp = [0] * (max_n + 1)
for i in range(N):
    if dp[An[i]] != 0:
        dp[An[i]] = 2
        continue
    for j in range(1, max_n//An[i] + 1):
        dp[An[i]*j] += 1
ans = 0
for a in An:
    if dp[a] == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# import sys
# readline = sys.stdin.readline
# generator = (readline().strip() for _ in range(N))

# import numpy as np
# from itertools import permutations
# from itertools import combinations
# from itertools import combinations_with_replacement

# import heapq
# from collections import deque

# N, M = map(int, input().split())
# sequence = list(map(int, input().split()))
# queries = (input() for _ in range(N))


def solve():
    N = int(input())
    sequence = list(map(int, input().split()))

    sequence.sort()

    max_v = sequence[-1]

    dp = [True] * (max_v + 1)

    previous = -1
    for v in sequence:
        if v == previous:
            dp[v] = False
            continue

        previous = v

        if not dp[v]:
            continue

        for iv in range(2 * v, max_v+1, v):
            dp[iv] = False

    count = 0
    for v in sequence:
        if dp[v]:
            count += 1

    return count


def main():
    print(solve())


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
n = int(sys.stdin.readline().rstrip("\n"))
a = [int(s) for s in sys.stdin.readline().rstrip("\n").split()]
a_max = max(a)
c = {num: 0 for num in a}
for num in a:
    c[num] += 1
d = {num: 0 for num in a}
for num in a:
    t = 2
    while num * t <= a_max:
        d[num*t] = 1
        t += 1
ans = 0
for num in a:
    if c[num] == 1 and d[num] == 0:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
max_a = max(a)
cnt_d = [0] * (max_a + 1)

for ai in a:
    for multi in range(ai, max_a + 1, ai):
        cnt_d[multi] += 1

print(sum(cnt_d[ai] == 1 for ai in a))

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
from bisect import bisect_right, bisect_left

N = int(input())
A = list(map(int, input().split()))
C = Counter(A)
a = sorted(C.keys())
dp = [1]*(a[-1]+1)
for x in a:
    if C[x] > 1:
        dp[x] = 0
    y = x+x
    while y <= a[-1]:
        dp[y] = 0
        y += x
ans = 0
for x in a:
    ans += dp[x]
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
As = list(map(int,input().split()))
# print(As)
c = Counter(As)

# エラトステネスの篩
is_ans = [True] * (10**6 + 1)
s = list(set(As))
for x in s:
  t = x * 2
  while t <= 10**6:
    is_ans[t] = False
    t += x

cnt = 0
for x in s:
  if c[x] == 1 and is_ans[x] == True:
    cnt += 1

print(cnt)

Submission status: Accepted

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

a_max = max(a_lst)
index_lst = [0]*(a_max + 1)

for ai in a_lst:
    for multi in range(ai, a_max+1, ai):
        index_lst[multi] += 1

ans = 0
for ai in a_lst:
    if index_lst[ai] == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from numba import njit, int32
import numpy as np


@njit(int32(int32[:], int32[:], int32[:]))
def main(A, B, C):
    ans = 0

    for a in A:
        B[a] += 1

    for a in C:
        v = 2*a
        while v <= 10**6:
            B[v] += 1
            v += a

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

    return ans


if __name__ == '__main__':
    N = int(input())
    A = [int(i) for i in input().split()]
    B = [0]*(10**6+1)
    ans = main(np.array(A, dtype=np.int32),
               np.array(B, dtype=np.int32),
               np.array([a for a in set(A)], dtype=np.int32))
    print(ans)

Submission status: Accepted

Solution code:
from numba import njit, int32
import numpy as np


@njit(int32(int32[:], int32[:]))
def main(A, B):
    ans = 0

    for a in A:
        B[a] += 1

    for a in set(A):
        v = 2*a
        while v <= 10**6:
            B[v] += 1
            v += a

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

    return ans


if __name__ == '__main__':
    N = int(input())
    A = [int(i) for i in input().split()]
    B = [0]*(10**6+1)
    ans = main(np.array(A, dtype=np.int32), np.array(B, dtype=np.int32))
    print(ans)

Submission status: Accepted

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

a_max = max(A)
B=[0]*(a_max + 1)

for ai in A:
    for multi in range(ai, a_max+1, ai):
        B[multi] += 1

ans = 0
for ai in A:
    if B[ai] == 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from numba import njit
import numpy as np


@njit
def main(A, B):
    for a in A:
        B[a] += 1

    for a in set(A):
        v = 2*a
        while v <= 10**6:
            B[v] += 1
            v += a

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

    print(ans)


if __name__ == '__main__':
    N = int(input())
    A = [int(i) for i in input().split()]
    B = [0]*(10**6+1)
    main(np.array(A), np.array(B))

Submission status: Accepted

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

a_max = max(a)
cnt = [0] * (max(a) + 1)
ans = 0

for ai in a:
    for multi in range(ai, a_max + 1, ai):
        cnt[multi] += 1

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

print(ans)

Submission status: Accepted

Solution code:
import sys
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
INF = 1000000000000

n = I()
a = LI()

a.sort()
m = a[n-1]
flg = [False]*(m+1)

count = 0
for x in range(n):
    v = a[x]
    if(not flg[v]):
        i = v
        while(i <= m):
            flg[i] = True
            i += v
        if(x == n-1 or v != a[x+1]):
            count += 1

print(count)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    B = [0]*(10**6+1)
    for a in A:
        B[a] += 1

    for a in set(A):
        v = 2*a
        while v <= 10**6:
            B[v] += 1
            v += a

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
checker = [1 for _i in range(10**6+1)]
a.sort()
a.append(-1)
result = 0
for i in range(n):
    if a[i] == a[i-1]:
        continue
    if a[i] == a[i+1]:
        checker[a[i]] = 0
    result += checker[a[i]]
    checker[a[i]] = 0
    x = 2
    while a[i]*x <= 10**6:
        checker[a[i]*x] = 0
        x += 1
print(result)

Submission status: Accepted

Solution code:
#coding:utf-8

N = int(input())

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

M = max(A)

L1 = [False] * (M+1)
L2 = [0] * (M+1)

for i in A:
    if L2[i] == 1:
        L1[i] = True
    
    d = i * 2
    L2[i] = 1
    
    while d <= M:
        L1[d] = True
        d += i

count = 0

for i in A:
    if not L1[i]:
        count += 1

print("{}".format(count))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
counter = 0
Amax = A[-1]
A.append(0)
dp = [True for i in range(Amax)]

for i in range(len(A)-1):
    p = A[i]
    if dp[p-1]:
        for j in range(Amax//p):
            if dp[p*(j+1)-1]:
                dp[p*(j+1)-1] = False
        if p != A[i+1]:
            counter += 1
    else:
        continue

print(counter)

Submission status: Accepted

Solution code:
from collections import Counter

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

M = 10**6

table = [1] * (M + 1)

B = Counter(a)
Key = list(B.keys())

count = 0
for x in Key:
    if B[x] == 1 and table[x] == 1:
        count += 1

    for i in range(M):
        if i * x > M:
            break
        else:
            table[i * x] = 0

print(count)

Submission status: Accepted

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

n = int(input())

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

c = [0] * (10**6+1)
for i in a:
    c[i] += 1

uni = []
a = list(set(a))

for i in a:
    if c[i] == 1:
        uni.append(i)

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

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

cnt = 0
for i in uni:
    if b[i] == 0:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
n = int(input())

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

c = [0] * (10**6+1)
for i in a:
    c[i] += 1

uni = []
a = list(set(a))

for i in a:
    if c[i] == 1:
        uni.append(i)

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

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

cnt = 0
for i in uni:
    if b[i] == 0:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
A = sorted(list(map(int, input().split())))
A_c = Counter(A)
A_max = A[-1]

dp = [True] * (A_max + 1)
counter = 0
for i in range(len(A) - 1):
    p = A[i]
    if dp[p] == False:
        continue
    else:
        for q in range(A_max // p + 1):
            dp[p * q] = False
        if p != A[i+1]:
            counter += 1
if dp[A_max] == True:
    counter += 1
print(counter)

Submission status: Accepted

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

b = [0] * (max(a) + 1)
# b[i] = (aの要素がiであるような数)
for i in range(n):
    b[a[i]] += 1

ans = 0
for i in range(1, len(b)):
    if b[i] > 0:
        if b[i] == 1:
            ans += 1
        # print(i, ans)
        for j in range(len(b)):
            if i * j >= len(b):
                break
            b[i * j] = 0

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
import bisect
n = int(input()) #リストの要素数
a = list(map(int, input().split())) #リストの要素
cnt = Counter(a) #aの要素数についての辞書
a.sort()#aを小さい順にソート
ans = 0
mx = 10 ** 6
p = [0] * (mx + 1)
for i in a:
    if p[i] == 0:
        for j in range(mx + 1):
            x = i * j
            if x > mx:
                break
            p[x] = 1 #pの中でaの要素iの倍数として表現できるものに１
        if cnt[i] == 1:
            ans += 1 #pの中で任意のiの倍数として表現できず、かつ１つのみ存在するものをカウント
print(ans)

Submission status: Accepted

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

d = {}
for a in A:
    d.setdefault(a, 0)
    d[a] += 1
#print(d)

A = sorted(set(A))
#print(A)
t = [True] * (10 ** 6 + 1)
for a in A:
    if d[a] != 1:
        t[a] = False
    for i in range(a + a, 10 ** 6 + 1, a):
        t[i] = False
print(sum(1 for a in A if t[a]))

Submission status: Accepted

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

    ma = max(A)
    N = [0] * (10 ** 6 + 1)
    for a in A:
        for i in range(a, ma + 1, a):
            N[i] += 1

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = sorted([int(i) for i in input().split()])
max_a = max(a)
cnt_d = [0] * (max_a + 1)

for ai in a:
    for multi in range(ai, max_a + 1, ai):
        cnt_d[multi] += 1

print(sum(cnt_d[ai] == 1 for ai in a))

Submission status: Accepted

Solution code:
n = int(input())
a = sorted([int(i) for i in input().split()])
max_a = max(a)
cnt_d = [0] * (max_a + 1)

for ai in a:
    for multi in range(ai, max_a + 1, ai):
        cnt_d[multi] += 1

cnt_nd = 0
for ai in a:
    if cnt_d[ai] == 1:
        cnt_nd += 1
print(cnt_nd)

Submission status: Accepted

Solution code:
from collections import Counter

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

prime = [0 for i in range(ma)]

for a in A:
    for j in range(a, ma+1, a):
        prime[j-1] += 1

cnt = 0
for i in A:
    if(prime[i-1] == 1):
        cnt += 1
       
print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
arr = sorted(list(map(int, input().split())))
count_arr = [0]*arr[-1]

ans = 0
for i in arr:
    for j in range(1,(arr[-1]//i)+1):
        count_arr[(i*j)-1] += 1
for i in arr:
    if count_arr[i-1] == 1:
        ans +=1

print(ans)

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:
n=int(input())
p=sorted(list(map(int,input().split())))
s=set()
m = 10**6+1
a=[True for _ in range(m)]
prev = 0
for x in p:
    if prev == x:
        s.discard(x)
        continue
    if a[x]:
        s.add(x)
    i = 2
    y = i*x
    while y<m:
        a[y] = False
        i+=1
        y = i*x
    prev=x

print(len(s))

Submission status: Accepted

Solution code:
n = int(input())
l = [int(x) for x in input().split()]
D = set() #Duplication
S = set() #all
for x in l:
    if x in S:
        D.add(x)
    else:
        S.add(x)

M = max(S)
limit = M+1
mp = [0]*(limit)

cnt = 0
S = sorted(S)
for x in S:
    for y in range(x,limit,x):
        mp[y] += 1
    if(x in D):
        continue
    if(mp[x]==1):
        cnt += 1
        
print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
l = [int(x) for x in input().split()]
D = set() #Duplication
S = set() #all
for x in l:
    if x in S:
        D.add(x)
    else:
        S.add(x)

limit = 10**6+1
mp = [0]*(limit)

cnt = 0
S = sorted(S)
for x in S:
    for y in range(x,limit,x):
        mp[y] += 1
    if(x in D):
        continue
    if(mp[x]==1):
        cnt += 1
        
print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
l = [int(x) for x in input().split()]
l.sort()
set_l = set(l)
set_l = sorted(set_l)
limit = 10**6+1
mp = [0]*(limit)
pre = None
for i in range(n):
    num = l[i]
    if(pre==num):
        mp[num] += 1
    pre = num

for x in set_l:
    for y in range(x,limit,x):
        mp[y] += 1
        

cnt = 0
for num in set_l:
    if(mp[num]==1):
        cnt += 1
print(cnt)