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:
def main():
  n=int(input())
  a=sorted(map(int,input().split()))
  maxa=a[-1]
  tf=[True]*maxa
  r=0
  n-=1
  for i in range(n): # maxa以外の処理
    a_i=a[i]
    if tf[a_i-1] ==True: # これまでに素の場合のみ処理実行
      for j in range(a_i - 1,maxa,a_i):
        tf[j]=False
      if a_i < a[i+1]: # a[i]とa[i+1]が同値の場合を排除
        r+=1
  if tf[-1] == True: # maxaへの処理
     r+=1
  print(r)
main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
result=0
flug = 0
if(len(a) == 1):
    print(1)
else:
    a.sort()
    dp = [True] * a[-1]
    flug = 1
    for j in range(n):
        if(dp[a[j]-1] == True):
            if(a[j] == a[j-1]):
                if(flug == 0):
                    result-=1
                    flug = 1
            else:
                result+=1
                flug = 0
                k = a[j] * 2
                while(k-1 < len(dp)):
                    dp[k-1] = False
                    k+=a[j]
                
    print(result)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

bool_list = [True] * (10 ** 6)

duplicate_dic = defaultdict(int)
for a in A:
    duplicate_dic[a] += 1
    if duplicate_dic[a] > 1:
        bool_list[a - 1] = False

for a in A_sort:
    for i in range(2*a, 10 ** 6 + 1, a):
        bool_list[i - 1] = False

print(sum([1 for a in A_sort if bool_list[a - 1]]))

Submission status: Accepted

Solution code:
from collections import Counter

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

a.sort()
cnt = 0
nmax = a[-1]
table = [True] * (nmax+1)
c = Counter(a)

duplicate = []
for i in c.keys():
    if c[i] > 1:
        duplicate.append(i)
for i in a:
    if not table[i]:
        continue
    if not i in duplicate:
        cnt += 1
    for j in range(i*2, nmax+1, i):
        table[j] = False
print(cnt)

Submission status: Accepted

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

for i in range(n):
    if multiples[a[i]]==True:
        continue
    elif i!=n-1 and a[i]==a[i+1]:
        pass
    else:
        ans+=1
    for j in range(a[i],lim,a[i]):
        multiples[j]=True

print(ans)

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

ans = 0

for i in range(10**6+1):
    if dp[i] == 1:
        ans += 1
    if dp[i] != 0:
        for j in range(2*i, 10**6+1, i):
            if dp[j] != 0:
                dp[j] += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

duplicate_dic = defaultdict(int)
for a in A:
    duplicate_dic[a] += 1
    if duplicate_dic[a] > 1:
        bool_list[a] = False

for a in A_sort:
    for i in range(2*a, 10 ** 6 + 1, a):
        bool_list[i] = False

print(sum([1 for a in A_sort if bool_list[a]]))

Submission status: Accepted

Solution code:
import sys, collections
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N = I()
    A = LI()

    cnt = collections.Counter(A)
    A = list(set(A))
    A.sort()
    A_max = A[-1]
    divisible = [False] * (A_max + 1)

    for i in A:
        for j in range(2 * i, A_max+1, i):
            divisible[j] = True

    ans = 0
    for i in A:
        if not divisible[i] and cnt[i] == 1:
            ans += 1
        
    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

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

for a in A:
    LIST[a]+=1
ANS=0

for i in range(10**6+1):
    if LIST[i]==1:
        ANS+=1
    if LIST[i]!=0:
        for j in range(2*i,10**6+1,i):
            if LIST[j]!=0:
                LIST[j]+=1
print(ANS)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
M = max(A)
B = [0] * (M + 1)

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

for a in A:
    if B[a] > 0:
        i = 2
        b = a * i
        while b <= M:
            B[b] = 0
            i += 1
            b = a * i
for i in range(M + 1):
    if B[i] > 1:
        B[i] = 0
print(sum(B))

Submission status: Accepted

Solution code:
import sys, collections
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N = I()
    A = LI()

    cnt = collections.Counter(A)
    A = list(set(A))
    A.sort()
    A_max = A[-1]
    divisible = [False] * (A_max + 1)

    for i in A:
        for j in range(2 * i, A_max+1, i):
            divisible[j] = True

    ans = 0
    for i in A:
        tmp = 0
        if not divisible[i] and cnt[i] == 1:
            tmp += 1
        ans += tmp

        
    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
result=0
flug = 0
if(len(a) == 1):
    print(1)
else:
    a.sort()
    dp = [True] * a[-1]
    flug = 1
    for j in range(n):
        if(dp[a[j]-1] == True):
            if(a[j] == a[j-1]):
                if(flug == 0):
                    result-=1
                    flug = 1
            else:
                result+=1
                flug = 0
            k = a[j] * 2
            while(k-1 < len(dp)):
                dp[k-1] = False
                k+=a[j]
                
    print(result)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
ac = [0 for i in range(10**6+2)]



for i in a:
    ac[i] +=1
a = sorted(set(a))
count =0

for i in a:
    if ac[i]>0:
        if ac[i] == 1:
            count += 1
        for j in range(i,10**6+2,i):
            if not ac[j]==0:
                ac[j]=0


print(count)

Submission status: Accepted

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

for i in a:
    dp[i] += 1
    if dp[i] == 1:
        for j in range(i*2, m_a, i):
            dp[j] += 2

print(dp.count(1))

Submission status: Accepted

Solution code:
# 解説を見て解きました。

n = int(input())
a = sorted(list(map(int,input().split())))
# aの最大値+1(0を含むので)
m_a = a[-1]+1
# dp[i](aの最小値<=i<=aの最大値)が1の個数の合計が答え
dp = [0]*m_a

for i in a:
    # dp[i]の初期値は0なので1を足す
    dp[i] += 1
    # dp[i]が2以上の時は列挙する必要がないのでパス
    if dp[i] == 1:
        # aの最大値までのiの倍数を列挙
        for j in range(i*2, m_a, i):
            # 倍数をはじくためにdp[j]を2以上にする
            dp[j] += 2

print(dp.count(1))

Submission status: Accepted

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

N = int(input())

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

AList.sort()

dp = [0] *  (AList[-1] + 1)

for i in AList:
    dp[i] += 1
    
    if dp[i] == 1:
        for p in range(2 * i, len(dp), i):
            dp[p] += 2

print(dp.count(1))

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
maxA = max(A)
# C[a] = A内のaの個数
C = {a: 0 for a in A}
for a in A:
    C[a] += 1
# D[a]=1: Aにaより小さいaの約数が存在する
D = {a: 0 for a in A}
for a in A:
    if C[a] > 0:
        t = 2
        while a * t <= maxA:
            D[a * t] = 1
            t += 1
ans = 0
for a in A:
    if C[a] == 1 and D[a] == 0:
        ans += 1
print(ans)

Submission status: Accepted

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


def main():
    n = int(input())
    A = np.array([int(i) for i in input().split()])

    max_dp = np.max(A) + 1
    dp = np.zeros(max_dp, dtype="int32")

    for a in A:
        if dp[a] >= 2:
            continue
        fancy = np.arange(a, max_dp, a)
        dp[fancy] += 2
        dp[a] -= 1
    print(np.sum(dp == 1))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit
  
# @njit
# @njit(cache = True)
@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

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

Submission status: Accepted

Solution code:
def resolve():
	N = int(input())
	A = list(map(int, input().split()))
	a_max = max(A)+1
	B = {}
	for i in range(N):
		a = A[i]
		if a not in B.keys():
			for j in range(a, a_max, a):
				B[j] = False
			B[a] = True
		else:
			B[a] = False
	Y = list(B.values()).count(True)
	print(Y)
resolve()

Submission status: Accepted

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

import sys
import numpy as np
from collections import Counter

def II(): return int(input())
def MII(): return map(int, input().split())
def LII(): return list(map(int, input().split()))


def main():
    N = int(input())
    A = LII()
    A.sort() 
    
    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

    print(sum(filter(lambda x: x == 1, dp)))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

    m = A[-1]
    C = [False] * (m + 1)

    ans = 0
    for i in range(N):
        if C[A[i]] == False:
            if i == N - 1 or (i < N - 1 and not A[i] == A[i + 1]):
                ans += 1
        else:
            continue

        n = 1
        while True:
            nv = n * A[i]
            if nv > m:
                break
            else:
                C[nv] = True
            n += 1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
#furui = [False] * (10**6+1)
#ans = 0
#for i in range(n):
#    if i-1 >= 0 and a[i] == a[i-1]:
#        continue
#    if furui[a[i]] == False:
#        if (i + 1 < n and a[i] != a[i + 1]) or i==n-1:
#            ans += 1
#        now = a[i]
#        while now <= 10**6:
#            furui[now] = True
#            now += a[i]
#print(ans)
furui = [0] *(10**6+1)
for i in range(n):
    now = a[i]
    if furui[now] == 1:
        furui[now] = 2
    if furui[now] == 0:
        now_2 = now
        while now_2 <= 10**6:
            furui[now_2]  += 1
            now_2 += now
ans = 0
for i in a:
    if furui[i] == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = sorted(list(map(int, input().split()))) + [0]
 
memo = ['Y'] * (10**6+1)
mx = max(A) + 1 
count = 0
 
for i in range(N):
    if memo[A[i]] == 'N':
        continue
    for j in range(A[i], mx, A[i]):
        memo[j] = 'N'
    if A[i] == A[i+1]:
        continue
    
    count += 1
 
print(count)

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
A = list(map(int,input().split())) + [10**6+1]
A.sort()
B = np.zeros(10**6+1)
count = 0
for i in range(N):
  if B[A[i]] == 0:
    B[::A[i]] = 1
    if A[i] != A[i+1]:
      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 = []
appear = []

for i in range((10 ** 6) + 1):
  if cnt[i] == 1:
    unique.append(i)
  if cnt[i] >= 1:
    appear.append(i)
    
cnt = [0] * ((10 ** 6) + 1)

for elem in appear:
  for m in range(elem * 2, (10 ** 6) + 1, elem):
    cnt[m] = 1
    
ans = 0

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

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = sorted(map(int, input().split()), reverse=False)
m = max(A)+1
c = Counter(A)
s = list(set(A))
dp = [True] * m
for x in list(set(A)):
    t = x * 2
    while t < m:
        dp[t] = False
        t += x
ans = 0
for a in A:
    if c[a] == 1 and dp[a]:
        ans += 1
print(ans)

Submission status: Accepted

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

for a in A:
    B[a] = True

for i in range(len(A)-1):
    a = A[i]
    if B[a] == True:
        if A[i] == A[i+1]:
            B[a] = False
        for x in range(2*a, len(B), a):
            B[x] = False

print(sum(B))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
dp = [0]*(a[-1]+1)
k = 2
while k*a[0] <= a[-1]:
    dp[k*a[0]] += 1
    k += 1

for i in range(1,n):
    if a[i] == a[i-1]:
        dp[a[i]] += 1
    else:
        k = 2
        while k*a[i] <= a[-1]:
            dp[k*a[i]] += 1
            k += 1
ans = 0
for elem in a:
    if dp[elem] == 0:
        ans += 1
print(ans)

Submission status: Accepted

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

A_max = max(A)
dp = [True] * (A_max + 1)
count = 0
A_f = {a: 0 for a in A}
for a in A:
    A_f[a] += 1

for a in A:
    if dp[a]:
        for i in range(1, A_max + 1):
            if a * i > A_max:
                break
            dp[a * i] = False
        if A_f[a] == 1:
            count += 1

print(count)

Submission status: Accepted

Solution code:
from collections import defaultdict

def resolve():
	N = int(input())
	A = list(map(int, input().split()))
	a_max = max(A)+1
	B = defaultdict(int)
	for i in range(N):
		a = A[i]
		if B[a]>1:
			B[a] = 2
		else:
			for j in range(a, a_max, a):
				B[j] += 1
	Y = 0
	for a in A:
		if B[a]==1:
			Y+=1
	print(Y)
resolve()

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import collections

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N = Z()
    A = sorted(ZZ())
    cA = collections.Counter(A)
    MAX_A = 10 ** 6
    is_ok = [True] * (MAX_A + 1)

    if 1 in cA.keys():
        if cA[1] == 1: print(1)
        elif cA[1] >= 2: print(0)
        return

    for a in cA.keys():
        if not is_ok[a]: continue
        if cA[a] >= 2: is_ok[a] = False
        for i in range(2, MAX_A + 1):
            if a * i > MAX_A: break
            is_ok[a * i] = False

    ans = 0
    for a in cA.keys():
        if is_ok[a]: ans += 1

    print(ans)

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

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

MAX = 10 ** 6

A.sort()
s = set()
ans = N
for i in range(N):
    a = A[i]
    if a in s:
        ans -= 1
        continue
    if i < N - 1 and A[i + 1] == a:
        ans -= 1
    n = MAX // a
    for i in range(1, n + 1):
        s.add(a * i)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = sorted(map(int, input().split()), reverse=False)
m = max(A)+1
c = Counter(A)
s = list(set(A))
dp = [True] * m
for x in s:
    t = x * 2
    while t < m:
        dp[t] = False
        t += x
ans = 0
for a in A:
    if c[a] == 1 and dp[a]:
        ans += 1
print(ans)

Submission status: Accepted

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

l.sort()
maxnum=l[len(l)-1]
flag=[0]*(maxnum+1)

for num in l:
    flag[num]+=1
    if flag[num]>1:
        continue
    for j in range(num*2, maxnum+1, num):
        flag[j]+=1
#print(flag)
ans=0

for num in l:
    if flag[num]==1:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    max_a = max(a)

    dp = [True] * (max_a + 1)
    ans = 0

    for i in range(n):
        ai = a[i]
        if dp[ai]:
            if not (i < n - 1 and a[i] == a[i + 1]):
                ans += 1
            x = 1
            while ai * x < max_a + 1:
                dp[ai * x] = False
                x += 1

    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Accepted

Solution code:
import sys

N = int(input())
A = sorted(list(map(int, input().split())))
A = A + [0]
if N == 1:
    print(1)
    sys.exit()
max = A[-2]
memo = ['Yes'] * (10**6+1)
ans = 0
 
for i in range(N):
    if memo[A[i]] == 'No':
        continue
    for j in range(A[i], max+1,A[i]):
        memo[j] = 'No'
    if A[i] == A[i+1]:
        continue
    ans += 1
 
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
li = list(map(int,input().split()))
li.sort()
cnt = 0


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

for i in li:
    cnt_li[i-1] += 1
    if cnt_li[i-1] == 1:
        for j in range(2*i,10**6+1,i):
            cnt_li[j-1] += 1

for k in li:
    if cnt_li[k-1] == 1:
        cnt += 1

print(cnt)

Submission status: Accepted

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

#定数倍のやつに＋１する
M=max(ls)
A=[0]*(M+1)
for i in range(len(ls)):
  a=1
  while ls[i]*a<=M:
    b=ls[i]*a
    if A[b]<=1:
      A[b]+=1
    a+=1
    
ans=0     
for i in range(len(ls)):
  if A[ls[i]]==1:
    ans+=1
print(ans)

Submission status: Accepted

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

a.sort()
if a[0] == 1:
    if len(a) == 1 or a[1] != 1:
        print(1)
    else:
        print(0)
else:
    a_max = a[-1]
    seive = [True for _ in range(a_max + 1)]
    a += [-1]
    ret = 0
    add = 1
    for i in range(n):
        if a[i] != a[i+1]:
            if seive[a[i]]:
                ret += add
                j = 2 * a[i]
                while j <= a_max:
                    seive[j] = False
                    j += a[i]
            add = 1
        else:
            add = 0
    print(ret)

Submission status: Accepted

Solution code:
def main():
  n, *A = map(int, open(0).read().split())
  A.sort()
  m = A[-1]
  lst = [0] * (m + 1)
  prep = 0
  for i in A:
    if i == prep:
      lst[i] = 1
      continue
    lst[2 * i::i] = [1] * len(lst[2 * i::i])
    prep = i
  res = 0
  for i in A:
    if lst[i] == 0:
      res += 1
  print(res)

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import numpy as np
n,*a=map(int,open(0).read().split())
l=np.zeros(max(a)+1)
a.sort()
a+=[10**7]
r=0
for i,j in zip(a,a[1:]):
    if l[i]==0:
        l[::i]=1
        if i!=j:
            r+=1
print(r)

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit
  
# @njit('(i4[::1],)', cache=True)
# @njit
@njit(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

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

Submission status: Accepted

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

#定数倍のやつに＋１する
M=max(ls)
A=[0]*(M+1)
for i in range(N):
  a=M//ls[i]
  for j in range(1,a+1):
    if A[j*ls[i]]<=2:
      A[j*ls[i]]+=1
    
ans=0     
for i in range(len(ls)):
  if A[ls[i]]==1:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
n=int(input())
a=[int(j)for j in input().split()]+[10**7]
l=np.zeros(max(a)+1)
a.sort()
r=0
for i,j in zip(a,a[1:]):
    if l[i]==0:
        l[::i]=1
        if i!=j:
            r+=1
print(r)

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit
  
# @njit('(i4[::1],)', cache=True)
@njit
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

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

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit
  
# @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

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
furui = [False] * (10**6+1)
ans = 0
for i in range(n):
    if i-1 >= 0 and a[i] == a[i-1]:
        continue
    if furui[a[i]] == False:
        if (i + 1 < n and a[i] != a[i + 1]) or i==n-1:
            ans += 1
        now = a[i]
        while now <= 10**6:
            furui[now] = True
            now += a[i]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

import sys
sys.setrecursionlimit(300000)

def solve(N: int, A: "List[int]"):
    counts = {}
    for a in A:
        if not a in counts:
            counts[a] = 0
        counts[a] += 1

    M = max(A)
    s = set(A)
    ret = 0
    used = [False] * (M + 1)
    for i in range(1, M + 1):
        if used[i]:
            continue
        if not i in s:
            continue
        if counts[i] == 1:
            ret += 1
        j = 1
        while i * j <= M:
            used[i * j] = True
            j += 1
    print(ret)


def _hoge(N, A):
    for i, v in enumerate(A):
        if used[i]:
            continue
        if not (i < N - 1 and v == A[i + 1]):
            ret += 1
        for j in range(i + 1, N):
            if A[j] % v == 0:
                used[j] = True
    print(ret)


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]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

a.sort()
amax=max(a)
dp=[True]*(amax+1)

import collections
c = collections.Counter(a)

d=[]
for ck,cv in c.items():
    if cv>=2:
       d.append(ck) 
dset=set(d)
    
aa=set()
for ai in a:
    if dp[ai]:
        aa.add(ai)
        for aj in range(ai*2,amax+1,ai):
            dp[aj]=False

aa=aa-dset    
print(len(aa))

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
set(a)
ans=[0]*1000005
x=1
for i in a:
    if(ans[i]!=0):
        ans[i]=2
        continue
    for j in range(i,1000005,i):
        ans[j]=ans[j]+1
cnt=0
for i in range(0,n):
    if(ans[a[i]]==1):
        cnt=cnt+1
print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
 
A_list = [int(n) for n in input().split()]
 
import numpy as np
 
A_array = np.array(A_list)
sort_A = np.sort(A_array)

n_array = np.zeros(10**6)
  
for a in sort_A:
    
    if n_array[a - 1] >= 2:
        continue
        
    a_times = np.array(range(a, 10**6+1, a))
    
    n_array[(a_times -1).astype(int)] += 1

print((n_array[sort_A - 1] == 1).sum())

Submission status: Accepted

Solution code:
N = int(input())
A = sorted(list(map(int, input().split())))
max = A[-1]
memo = ['Yes'] * (10**6+1)
ans = 0
 
for i, A_i in enumerate(A):
    if memo[A_i] == 'No':
        continue
    for j in range(A_i, max+1, A_i):
        memo[j] = 'No'
    if i != N-1 and A_i == A[i+1]:
        continue
    ans += 1
 
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import collections

n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
c = collections.Counter(a)
data = sorted(list(set(a)))
max_ = max(a)+1
prime_bool = [True]*max_
prime_bool[0] = False

for i in range(len(data)):
  p = data[i]
  if prime_bool[p]:
    #print(p)
    k = 2
    while k*p < max_:
      prime_bool[k*p] = False
      k += 1

count = 0
for i in range(len(prime_bool)):
  if prime_bool[i]:
    if c[i] == 1:
      count += 1
print(count)
#print(prime_bool)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
OKlist = [0]*(10**6+100)
A.sort()
for i in range(len(A)-1):
    if A[i] == A[i+1] and OKlist[A[i]] == 0:
        OKlist[A[i]] += 2
        for j in range(1,10**6+10):
            if A[i]*j > 10**6:
                break
            else:
                OKlist[A[i]*j] += 1
    elif OKlist[A[i]] == 0:
        for j in range(1,10**6+10):
            if A[i]*j > 10**6:
                break
            else:
                OKlist[A[i]*j] += 1
    else:
        OKlist[A[i]] += 1
OKlist[max(A)] += 1
cnt = 0
for i in A:
    if OKlist[i] == 1:
        cnt += 1
        
        
print(cnt)

Submission status: Accepted

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

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

for i in range(n):
    if ok[a[i]] != 0:
        for g in range(a[i], M+1, a[i]):
            if g != a[i]:
                ok[g] = 0

print(ok.count(1))

Submission status: Accepted

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

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

for a in A:
  for i in range(a, A[-1]+1, a):
    cnt[i] += 1

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

print(ans)

Submission status: Accepted

Solution code:
import collections
N = int(input())
A = sorted([int(i) for i in input().split()])
C = collections.Counter(A)
tested = [True for i in range(10**7+1)]

ans = 0
for i in range(N):
    if tested[A[i]] is True:
        for j in range(A[i], 10**6+1, A[i]):
            tested[j] = False
        if C[A[i]] == 1:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
OKlist = [0]*(10**6+100)
A.sort()
for i in range(len(A)-1):
    if A[i] == A[i+1]:
        OKlist[A[i]] += 1
    else:
        for j in range(10**6+10):
            if A[i]*j > 10**6:
                break
            else:
                OKlist[A[i]*j] += 1
OKlist[max(A)] += 1
cnt = 0
for i in A:
    if OKlist[i] == 1:
        cnt += 1
        
print(cnt)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    maxA = max(A)
    # C[a] = A内のaの個数
    C = {a: 0 for a in A}
    for a in A:
        C[a] += 1
    # D[a]=1: Aにaより小さいaの約数が存在する
    D = {a: 0 for a in A}
    for a in A:
        if C[a] > 0:
            t = 2
            while a * t <= maxA:
                D[a * t] = 1
                t += 1
    ans = 0
    for a in A:
        if C[a] == 1 and D[a] == 0:
            ans += 1
    print(ans)
main()

Submission status: Accepted

Solution code:
import collections,sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N = I()
A = sorted(LI())
counter_A = collections.Counter(A)
sequence = [0]*(10**6+1)
ans = 0
for k,v in counter_A.items():
    if sequence[k]==1:
        continue
    if v==1:
        ans += 1
    for i in range(k,10**6+1,k):
        sequence[i] = 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
m = max(A)+2
cnt = [0] * m
for a in A:
    cnt[a] += 1
    if cnt[a] == 1:
        for i in range(a+a, m, a):
            cnt[i] += 1
ans = 0
for a in A:
    ans += (cnt[a] == 1)
print(ans)

Submission status: Accepted

Solution code:
import math
from collections import Counter

MAX = 10**6

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

table = [0] * (MAX + 1)
# Aの各要素の倍数を記録する（+1していく）
for a in A:
    # aがまだ記録されてない(table[a]==0)場合に、その倍数をtableに記録すればよい
    # 記録されている場合は、その倍数も既に記録されているので、
    # aが問題の条件を満たさないことを表す「2」以上の数字を記録して次のAの要素に移ればよい

    if table[a] != 0:
        table[a] = 2
        continue
    tmp = a
    while tmp <= MAX:
        table[tmp] += 1
        tmp += a
ans = 0
for a in A:
    if table[a] == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:

import math
from collections import defaultdict

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

D = defaultdict(int)

AM = A[-1]
dp = [True]*(AM)

for x in A:
  if dp[x-1]:
    temp = 2 * x
    while temp <= AM:
      dp[temp-1] = False
      temp += x

for x in A:
  if dp[x-1]:
    D[x] += 1

ans = len([i for i in D if D[i] == 1])

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
array = [int(x) for x in input().split()]
counter = Counter(array)
array = sorted(set(array))
judge = [False for x in range(1000001)]
num = set()
set_f = set()
for a in array:
    if judge[a]:continue
    tmp = a
    while tmp + a <= 1000000:
        tmp += a
        judge[tmp] = True
    # print(len(num))
    # set_f |= set(factorization(a))
    # print(factorization(a))
print(len([1 for x in array if not judge[x] and counter[x] == 1]))

Submission status: Accepted

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

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

M = 10 ** 6  + 5
dp = [0]*(M)

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

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

print(ret)