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: Runtime Error

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

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

if max(B) == N:
	print(0)
else:
	for a in A:
		pass

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

Solution code:
find / -name pip

Submission status: Runtime Error

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

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

if max(B) == N:
	print(0)
else:
	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 b in B:
		if B[b] > 1:
			B[b] = 0
	print(sum(B))

Submission status: Runtime Error

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

    A.sort()
    max_dp = A[-1]
    A = np.append(A, 10 ** 6 + 2)

    dp = np.ones(max_dp + 1, dtype=bool)

    if A[0] != A[1]:
        ans = 1

    ans = 0
    for i in range(n):
        if A[i] == A[i + 1] or not dp[A[i]]:
            continue
        # print(f"{i = }, {max_dp = }\n{dp = }")
        a = A[i]
        fancy = np.arange(a, max_dp + 2, a)
        dp[fancy] &= False

        ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

    A.sort()
    max_dp = A[-1]
    A = np.append(A, 10 ** 6 + 2)

    dp = np.ones(max_dp + 1, dtype=bool)

    if A[0] == A[1]:
        ans = 1

    ans = 0
    for i in range(n):
        if A[i] == A[i + 1] or not dp[A[i]]:
            continue
        # print(f"{i = }, {max_dp = }\n{dp = }")
        a = A[i]
        fancy = np.arange(a, max_dp + 2, a)
        dp[fancy] &= False

        ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

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

if sum(B) == N:
	print(0)
else:
	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 b in B:
		if b > 1:
			B[b] = 0
	print(sum(B))

Submission status: Runtime Error

Solution code:
import sys

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

if N == 1:
    print(1)
    sys.exit()
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 A_i == A[i+1]:
        continue
    ans += 1
 
print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter
M=10**7
_,*l=map(int,open(0).read().split())
d=[1]*(M)
C=Counter(sorted(l)
s=0
for a,b in C.items():
    if b != 1:d[a]=0
    elif d[a]:s+=1
    for j in range(a,M,a):d[j]=0
print(s)

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
set(a)
ans=[0]*1000000
x=1
for i in a:
    if(ans[i]!=0):
        ans[i]=2
        continue
    for j in range(i,1000000,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: Runtime Error

Solution code:
from collections import Counter
M=10**7
_,*l=map(int,open(0).read().split())
d=[1]*(sorted(M))
C=Counter(l)
s=0
for a,b in C.items():
    if b != 1:d[a]=0
    elif d[a]:s+=1
    for j in range(a,M,a):d[j]=0
print(s)

Submission status: Runtime Error

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

#重複したやつ除く
ls_A.sort()
ls=[]
for i in range(N):
  if i==0:
    if ls_A[0]!=ls_A[1]:
      ls.append(ls_A[0])
  elif i==N-1:
    if ls_A[N-1]!=ls_A[N-2]:
      ls.append(ls_A[N-1]) 
  else:
    if ls_A[i]!=ls_A[i-1] and ls_A[i]!=ls_A[i+1]:
      ls.append(ls_A[i])       

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

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

Solution code:
_,*p=map(int,open(0).read().split())
i=0
p.sort()
while(len(p)!=0):
  t=p[0]
  p=[m if m!=t else 0 for m in p[1:] if m%t!=0 or m==t ]
  if 0 in p:
    p=[i for i in p if i!=0]
  else:i+=1
print(len(q))

Submission status: Runtime Error

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: Runtime Error

Solution code:
import numpy as np
n = int(input())
a = np.sort(np.array(list(map(int, input().split()))))
max_num = np.max(a)+1
dp = np.array([True]*(max_num))

if np.all(a==a[0]):
    print(0)
else:
    for i in range(1,max_num):
        if dp[i] and i in a:
            for j in np.arange(i*2, max_num, i):
                dp[j] = False
        if np.count_nonzero(a==i) >1:
            dp[i] = False
    print(np.count_nonzero(dp[np.a] == True))

Submission status: Runtime Error

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    n = I()
    mylist = sorted(list(MI()))
    max_num = mylist[n-1] // 2
    start = mylist[0]
    input_list = [0] * n
    index = 0

    while len(mylist) >= 1:
        temp = mylist.pop(0)
        if not(temp in mylist):
            index += 1
        for j in set(mylist):
            if j % temp == 0:
                while j in mylist:
                    mylist.remove(j)
        if mylist[0] > max_num:
            break
    print(index+len(mylist)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n=int(input())
l=list(int(input().split(" ")))
count=0
for i in range(n):
  for j in range(n):
    if(i!=j and l[j]%l[i]!=0):
      count+=1
print(count)

Submission status: Runtime Error

Solution code:
def merge_sort(array):
    if len(array) == 1:
        return array
    left_array = merge_sort(array[:len(array) // 2])
    right_array = merge_sort(array[len(array) // 2:])
    sorted_array = []
    while left_array and right_array:
        #print(left_array, right_array)
        if left_array[0] < right_array[0]:
            sorted_array.append(left_array.pop(0))
        else:
            sorted_array.append(right_array.pop(0))
    sorted_array.extend(right_array)
    sorted_array.extend(left_array)
    return sorted_array


def main():
    n = int(input())
    a = list(map(int, input().split()))
    
    a = merge_sort(a)
    #print(a)
    a_max = a[n-1]
    is_prime = [True] * (2 * 10**5 +1)
    is_prime[0] = False
    #is_prime[1] = False
    count = [0] * (2 * 10**5 +1)
    
    a_pre = 0
    for i in range(n):
        if a[i]==a_pre:
            count[a[i]-1] = 0
            a_pre = a[i]
            continue
        if is_prime[a[i]-1]:
            count[a[i]-1] = 1
            for j in range(a[i]*2, a_max+1, a[i]):
                is_prime[j-1] = False
        a_pre = a[i]
    
    print(sum(count))
    

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n=int(input())
l=list(int(input().split(" ")))
count=0
for i in range(n):
  for j in range(n):
    if(i!=j and l[j]%l[i]==0):
      count+=1
print(count)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
B = [0] * 2 * 10 ** 5
M = A[-1]

for a in A:
	B[a] = 1

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

Submission status: Runtime Error

Solution code:
if __name__ == "__main__":
    n = int(input())
    l_a = list(map(int, input().split()))
    s_a = list(set(l_a))

    s_a.sort()

    dub_a = [0]*max(s_a)

    for i in l_a:
        dub_a[i-1] += 1

    dp = [1]*max(s_a)

    for i in s_a:
        if 2*i > len(dp)+1:
            pass
        elif dp[2*i-1] == 0:
            pass
        else:
            for j in range(2*i-1, len(dp), i):
                dp[j] = 0


    count = 0
    for i in l_a:
        if dp[i-1]==1 and dub_a[i-1]==1:
            count += 1
    print(count)

Submission status: Runtime Error

Solution code:
if __name__ == '__main__':
    n = int(input().strip())
    a = list(map(int, input().strip().split()))

    a.sort()
    penalty = 0

    num = 0

    if a[0] == 1:
        if a[1] == 1:
            print(0)
        else:
            print(1)
    else:
        while len(a) > num and not len(a) == 0:
            if not len(a) == num + 1 and a[num] == a[num + 1]:
                while not len(a) == num + 1 and a[num] == a[num + 1]:
                    a.pop(num)
                penalty += 1

            i = num + 1
            while len(a) > i:
                if a[i] % a[num] == 0:
                    a.pop(i)
                else:
                    i += 1
            num += 1
        print(len(a) - penalty)

Submission status: Runtime Error

Solution code:
import sys

N = int(input())

A = list(map(int, input().split()))
A = [x for x in set(A) if A.count(x) == 1]
if len(A) <= 1:
    print(len(A))
    sys.exit()

A = np.array(sorted(A))
B = np.array([A[0]])
 
for i in range(len(A)-1):
    if np.all(A[i+1] % B != 0):
        B = np.append(B, A[i+1])
print(len(B))

Submission status: Runtime Error

Solution code:
if __name__ == "__main__":
    n = int(input())
    l_a = list(map(int, input().split()))
    s_a = list(set(l_a))

    s_a.sort()

    dub_a = [0]*max(s_a)

    for i in l_a:
        dub_a[i-1] += 1

    dp = [1]*max(s_a)

    for i in s_a:
        if 2*i > len(dp)-1:
            pass
        elif dp[2*i-1] == 0:
            pass
        else:
            for j in range(2*i-1, len(dp)+1, i):
                dp[j] = 0


    count = 0
    for i in l_a:
        if dp[i-1]==1 and dub_a[i-1]==1:
            count += 1
    print(count)

Submission status: Runtime Error

Solution code:
import bisect,collections,copy,heapq,itertools,math,numpy,string
import sys
sys.setrecursionlimit(10**7)

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

def main():
    N = I()
    A = numpy.array(LI())

    b = A*numpy.invert(numpy.eye(N,dtype=bool)) # 対角要素を0にする
    b = b[b!=0].reshape(-1,N) # 対角要素削除
    print(N-numpy.any(numpy.mod(A,b)==0,axis=0).sum()) # N- 他要素で割り切れるAiの数

main()

Submission status: Runtime Error

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

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

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

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

print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
c = {}
#for i in range(n):
 # c[a[i]] = c.get(a[i], 0) + 1

prime_bool = [True]*(max(a)+1)
prime_bool[0] = False
count = 0
for p in sorted(a):
  if prime_bool[p]:
    if c[p] == 1:
      count += 1
    #print(p)
    for j in range(2*p, max(a)+1, p):
      prime_bool[j] = False

print(count)

Submission status: Runtime Error

Solution code:
def merge_sort(array):
    if len(array) == 1:
        return array
    left_array = merge_sort(array[:len(array) // 2])
    right_array = merge_sort(array[len(array) // 2:])
    sorted_array = []
    while left_array and right_array:
        #print(left_array, right_array)
        if left_array[0] < right_array[0]:
            sorted_array.append(left_array.pop(0))
        else:
            sorted_array.append(right_array.pop(0))
    sorted_array.extend(right_array)
    sorted_array.extend(left_array)
    return sorted_array


def main():
    n = int(input())
    a = list(map(int, input().split()))
    
    a = merge_sort(a)
    #print(a)
    a_max = a[n-1]
    is_prime = [True] * 2 * 10**5
    is_prime[0] = False
    #is_prime[1] = False
    count = [0] * 2 * 10**5
    
    a_pre = 0
    for i in range(n):
        if a[i]==a_pre:
            count[a[i]-1] = 0
            a_pre = a[i]
            continue
        if is_prime[a[i]-1]:
            count[a[i]-1] = 1
        for j in range(a[i]*2, a_max+1, a[i]):
            is_prime[j-1] = False
        a_pre = a[i]
    
    print(sum(count))
    

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())))
#print(a)
for i in range(n):
  #print(i)
  for j in range(n-1-i):
    if a[i+j+1] % a[i] ==0:
      #print(i+j)
      del a[i+j]
      n=n-1
print(len(a))

Submission status: Runtime Error

Solution code:

n = int(input())
a = list(map(int, input().split()))
d = {}
for i in range(n):
  d[a[i]] = d.get(a[i], 0) + 1
data = sorted(list(set(a)))
prime_bool = [True]*(max(a)+1)
prime_bool[0] = False
count = 0
for i in range(len(data)):
  p = data[i]
  if prime_bool[p]:
    if c[p] == 1:
      count += 1
    #print(p)
    for j in range(2*p, max(a)+1, p):
      prime_bool[j] = False

print(count)

Submission status: Runtime Error

Solution code:


n = int(input())
a = list(map(int, input().split()))
d = {}
for i in range(n):
  d.get(a[i], 0) += 1
data = sorted(list(set(a)))
prime_bool = [True]*(max(a)+1)
prime_bool[0] = False
count = 0
for i in range(len(data)):
  p = data[i]
  if prime_bool[p]:
    if c[p] == 1:
      count += 1
    #print(p)
    for j in range(2*p, max(a)+1, p):
      prime_bool[j] = False

print(count)

Submission status: Runtime Error

Solution code:
import sys

N = int(input())

if N == 1:
    print(1)
    sys.exit()
    
A = sorted(set(map(int, input().split())))

if len(A) == 1:
    print(0)
    sys.exit()
    
max = A[-1]
memo = ['Y'] * (10**6+1)
ans = 0
 
for i, A_i in enumerate(A):
    if memo[A_i] == 'N':
        continue
    for j in range(A_i, max+1, A_i):
        memo[j] = 'N'
    if i != N-1 and A_i == A[i+1]:
        continue
    ans += 1
    
print(ans)

Submission status: Runtime Error

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

M = 10**6 + 1
flag = [True]*M

for a in A:
    if flag[a+a] == False:
        continue
    for i in range(M)[a+a::a]:
        flag[i] = False

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

print(ans)

Submission status: Runtime Error

Solution code:
n = map(int, input().split())
a = sorted(list(map(int, input().split())))
for i in range(n):
  for j in range(n-i):
    if a[i+j] % a[i] ==0:
      del a[i+j]
print(len(a))

Submission status: Runtime Error

Solution code:
#import numpy as np

N = int(input())
A = list(map(int, input().split()))
A.sort()#わるほう

#kouho = sorted([x for x in set(A) if A.count(x) == 1])
#maxA = 10**5

#target = kouho[:]
maxA = 10**5
work=[0]*(maxA+1)

for i in range(len(A)):
    if work[A[i]]<=1:
        maxN = int(maxA/A[i])
        for n in range(1,maxN+1):
            buf = A[i]*n
            #remove_list.append(buf)
            work[buf]+=1
                #print(A[i]*n)

#target = kouho[:]
#kouho = list(set(kouho) - set(remove_list))

sm=0
for s in A:
    if work[s]==1: sm+=1
print(sm)

#print(len(kouho))

Submission status: Runtime Error

Solution code:
import numpy as np

N = int(input())
A = [int(x) for x in input().split(" ")]
Amax = max(A)
dp = np.ones(Amax, dtype=bool)
appear = np.zeros(Amax, dtype=int)
for a in A:
  appear[a-1] += 1

for i in range(1, len(dp)+1):
  if not dp[i-1]:
    continue
  if appear[i-1] != 0:
    j = 2
    while j * i <= Amax:
      dp[j * i - 1] = False
      j += 1

count = 0
for a in A:
  if appear[a-1] > 1:
    continue
  else:
    count += dp[a-1]
print(count -  len(dup_set))

Submission status: Runtime Error

Solution code:
#import numpy as np

N = int(input())
A = list(map(int, input().split()))
A.sort()#わるほう

#kouho = sorted([x for x in set(A) if A.count(x) == 1])
#maxA = 10**5

#target = kouho[:]
maxA = 10**5
work=[0]*(maxA+1)

for i in range(len(A)):
    maxN = int(maxA/A[i])
    for n in range(1,maxN+1):
        buf = A[i]*n
        #remove_list.append(buf)
        work[buf]+=1
            #print(A[i]*n)

#target = kouho[:]
#kouho = list(set(kouho) - set(remove_list))

sm=0
for s in A:
    if work[s]==1: sm+=1
print(sm)

#print(len(kouho))

Submission status: Runtime Error

Solution code:
import numpy as np
n = int(input())
a = list(map(int, input().split()))
a.sort()
for i in range(n-1):
    de = []
    for j in range(i+1,n):
        if a[j]%a[i]==0:
            de.append(j)
        if j<=n-1:
            if j==n-1 and a[j] == a[j-1]:
                de.append(j)
            elif a[j]==a[j-1] and (a[j]!=a[j+1]):
                de.append(j)
    de.sort()
    de = np.array(de)
    for j in range(len(de)):
        a.pop(de[j])
        de-=1
        n-=1
print(n)

Submission status: Runtime Error

Solution code:
#import numpy as np
import time

N = int(input())
A = list(map(int, input().split()))
A.sort()#わるほう
remove_list = []

#kouho = sorted([x for x in set(A) if A.count(x) == 1])
#maxA = 10**5

#target = kouho[:]
maxA = 10**5
work=[0]*(maxA+1)

for i in range(len(A)):
    maxN = int(maxA/A[i])
    for n in range(1,maxN+1):
        buf = A[i]*n
        #remove_list.append(buf)
        work[buf]+=1
            #print(A[i]*n)

#target = kouho[:]
#kouho = list(set(kouho) - set(remove_list))

sm=0
for s in A:
    if work[s]==1: sm+=1
print(sm)

#print(len(kouho))

Submission status: Runtime Error

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

# ダブってる数
rm = 0
for i in A:
    if A.count(i) != 1:
        rm += 1

# 解説動画にあったやり方
T = [0]*(10**6+1)
for i in A:
    j = 1
    while(i*j <= 10**6):
        T[i*j] += 1
        j += 1

ans = -len(rmlst)
for i in A:
    if T[i] == 1:
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

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

U = 10**6 + 10

def main(A, primes):
    B = np.zeros(U + 1, np.int64)
    for x in A:
        B[x] += 1
    for p in primes:
        for i in range(U // p + 1):
            B[p * i] += B[i]
    ret = 0
    for x in A:
        ret += B[x] == 1
    return ret

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

def prime_table(N):
    is_prime = np.zeros(N, np.int64)
    is_prime[2:3] = 1
    is_prime[3::2] = 1
    for p in range(3, N, 2):
        if p * p >= N:
            break
        if is_prime[p]:
            is_prime[p * p::p + p] = 0
    return is_prime, np.where(is_prime)[0]

A = np.array(read().split(), np.int64)[1:]
_, primes = prime_table(U)

print(solve(A, primes))

Submission status: Runtime Error

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

def MakeDivisors(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]

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

def AddV2(v,w):
    return [v[0]+w[0],v[1]+w[1]]

dir4 = [[1,0],[0,1],[-1,0],[0,-1]]


def clamp(x,y,z):
    return max(y,min(z,x))

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            
#
def Zaatsu(a):
    a.sort()
    now = a[0][0]
    od = 0
    for i in range(n):
        if(now==a[i][0]):
            a[i][0]=od
        else:
            now = a[i][0]
            od+=1
            a[i][0] = od
    
    a.sort(key = lambda x : x[1])
    return a

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

def rl(x):
    return range(len(x))

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

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

#31-

n = int(input())

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

a.sort()

#print(a)
li = [0 for i in range(10**6+1)]
ans = 0
co = 0

taboo = [0]*n


import sympy



for i in a:
    #print(i)
    if(taboo[co]==1):
        co+=1
        continue
    #t = MakeDivisors(i)
    t = sympy.divisors(i)
    #print(li[:30])
    #print(i,t,ans)
    ok=1

    if(co!=0):
        if(a[co-1]==i):
            ok=0
    if(co!=n-1):
        if(a[co+1]==i):
            ok=0
    for j in t:
        if(li[j]==1):
            ok=0
    ans+=ok
    #print(i,ok,ans)
    li[i]=1
    co+=1
print(ans)

Submission status: Runtime Error

Solution code:
#import numpy as np
import time

N = int(input())
A = list(map(int, input().split()))
A.sort()#わるほう
remove_list = []

kouho = sorted([x for x in set(A) if A.count(x) == 1])
#maxA = 10**5

#target = kouho[:]
if kouho != []:
    maxA = kouho[-1]
    work=[0]*(maxA+1)

for i in range(len(A)):
    if kouho == []:
        break
    maxN = int(maxA/A[i])
    for n in range(1,maxN+1):
        buf = A[i]*n
        #remove_list.append(buf)
        work[buf]+=1
            #print(A[i]*n)

#target = kouho[:]
#kouho = list(set(kouho) - set(remove_list))

if kouho == []:
    print(0)
else:
    sm=0
    for s in A:
        if work[s]==1: sm+=1
    print(sm)

#print(len(kouho))

Submission status: Runtime Error

Solution code:
import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
from numba import njit,i8


@njit(i8[:](i8,i8,i8[:]))
def sieve(N,A,dp):
    for i in range(N):
        now = A[i]
        M = A[-1] // now
        for j in range(2,M+1):
            dp[now*j-1] = False
    return dp


@njit(i8(i8,i8,i8[:]))
def cnt(N,A,dp):
    skip = 0
    res = 0
    for i in range(N):
        now = A[i]
        if skip == now:
            continue
        if i != N - 1:
            if now == A[i+1]:
                skip = now
                continue
        if dp[now-1]:
            res += 1
    return res


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

    A = sorted(A)
    A = np.array(A)

    dp = np.array([True for i in range(A[-1])])
    # print(dp)
    dp = sieve(N,A,dp)
    # print(dp)

    res = cnt(N,A,dp)

    print(res)



main()

Submission status: Runtime Error

Solution code:
def bubble_sort(input_list):
    total_number = len(input_list)
    flag = True
    finished = 0

    while flag:
        flag = False
        for i in range(total_number-1-finished):
            if input_list[i] > input_list[i+1]:
                input_list[i], input_list[i+1] = input_list[i+1], input_list[i]
                flag = True
        finished += 1
        
    return(input_list)


def main():
    n = int(input())
    a = list(map(int, input().split()))
    
    a = bubble_sort(a)
    #print(a)
    a_max = a[n-1]
    is_prime = [True] * 2 * 10**5
    is_prime[0] = False
    #is_prime[1] = False
    count = [0] * 2 * 10**5
    
    a_pre = 0
    for i in range(n):
        if a[i]==a_pre:
            count[a[i]-1] = 0
            continue
        if is_prime[a[i]-1]:
            count[a[i]-1] = 1
        for j in range(a[i]*2, a_max+1, a[i]):
            is_prime[j-1] = False
        a_pre = a[i]
    
    print(sum(count))
    

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#import numpy as np
import time

N = int(input())
A = list(map(int, input().split()))
A.sort()#わるほう
remove_list = []

kouho = sorted([x for x in set(A) if A.count(x) == 1])
#maxA = 10**5

#target = kouho[:]
if kouho != []:
    maxA = kouho[-1]
    work=[0]*(maxA+1)

for i in range(len(A)):
    if kouho == []:
        break
    maxN = int(maxA/A[i])
    for n in range(1,maxN+1):
        buf = A[i]*n
        #remove_list.append(buf)
        work[buf]+=1
            #print(A[i]*n)

#target = kouho[:]
#kouho = list(set(kouho) - set(remove_list))

sm=0
for s in A:
    if work[s]==1: sm+=1
print(sm)

#print(len(kouho))

Submission status: Runtime Error

Solution code:

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

a.sort()

max_a = a[-1]
is_available = [True] * (max_a + 1)

ans = 0

for i, x in enumerate(a[:-1]):
    if not a[i+1] == x and is_available[x]:
        ans += 1
    for b in range(x, m + 1, x):
        is_available[b] = False

if is_available[a[-1]]:
    ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
cnt = [0 for _ in range(10**6+5)]
ans = 0
if a[0] == 1:
    if a[1] != 1:
        print(1)
    else:
        print(0)
    exit()
for x in a:
    for i in range(x, 10**6+5, x):
        cnt[i] += 1
for x in a:
    if cnt[x] == 1:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
import random
from decimal import Decimal
import itertools
import re
import bisect
from collections import deque, Counter
from functools import lru_cache

sys.setrecursionlimit(10**9)
INF = 10**13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
def SERIES(n): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ')
def GRID(h,w): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ').reshape(h,-1)[:,:w]
def GRIDfromString(h,w): return np.frombuffer(sys.stdin.buffer.read(), 'S1').reshape(h,-1)[:,:w]
MOD = 1000000007

def main():
	n = I()
	A = np.array(LI())
	A.sort()
	prime_list = set()
	a_max = A[-1]
	dp = [1]*a_max
	if A[0] != A[1]:
		a = A[0]
		prime_list.add(a)
		i = 2
		while a*i <= a_max:
			dp[a*i-1] = 0
			i += 1
	dp[A[0]-1] = 0
	for a in A[1:]:
		if dp[a-1] == 1:
			dp[a-1] = 0
			prime_list.add(a)
			i = 2
			while a*i <= a_max:
				dp[a*i-1] = 0
				i += 1
	print(len(prime_list))






if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
import heapq

ri = lambda: int(sys.stdin.readline())
rl = lambda: list(map(int, sys.stdin.readline().split()))

def heapsort(iterable):
  h = []
  for value in iterable:
    heapq.heappush(h, value)
  l = []
  for _ in range(len(h)):
    l.append(heapq.heappop(h))
  return l
def func():
    n = ri()
    li = rl()
    dic = {}
    for w in li:
        if w in dic:
            dic[w] += 1
        else:
            dic[w] = 1
    li1 = []
    li2 = []
    for k, v in dic.items():
        if v > 1:
            li1.append(k)
        else:
            li2.append(k)
    li1 = heapsort(li1)
    li2 = heapsort(li2)
    le1 = len(li1)
    le2 = len(li2)
    cnt = 0
    for i in range(le2):
        li2i = li2[i]
        for j in range(i):
            li2j = li2[j]
            tmp = li2i*0.5
            if li2j > tmp:
                for k in range(le1):
                    li1k = li1[k]
                    if li1k > tmp:
                        cnt += 1
                        break
                    if li2i % li1k == 0:
                        break
                else:
                    cnt += 1
                break
            if li2i % li2j == 0:
                break
        else:
            for k in range(le1):
                li1k = li1[k]
                if li1k > tmp:
                    cnt += 1
                    break
                if li2i % li1k == 0:
                    break
            else:
                cnt += 1
    print(cnt)
func()