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:
from math import sqrt
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
C = set(A)
B = dict(Counter(A))

n = 10**6
prime = {i for i in range(2, n)}
for i in range(2, n):
    if i in prime:
        for j in range(i*2, n, i):
            if j in prime:
                prime.remove(j)
ans = 0
for i in range(N):
    if B[A[i]] > 1:
        pass
    else:
        if A[i] in prime: 
            ans+=1 
            continue
        flag = True
        for j in range(1, A[i]+1):
            if A[i] % j == 0:
                if A[i]//j in C:
                    if A[i]//j < A[i]:
                        flag = False
                        break
                if j in C:
                    if j < A[i]:
                        flag = False
                        break
            if j**2 > A[i]:
                flag = False
        ans += flag(int)
print(ans)

Submission status: Runtime Error

Solution code:
import bisect as bc
 
N = int(input())
A = list(map(int,input().split()))
A.sort()
 
dp = [True for _ in range(A[-1]+1)]
 
for i in range(N):
    ai = A[i]
    for j in range(2,A[-1]+1):
        if ai*j > A[-1]:
            break
        dp[ai*j] = False
 
ans = 0
for i in range(N):
    if dp[A[i]]:
        if bc.bisect_right(A,A[i]) - bc.bisect_left(A,A[i]) == 1:
            ans += 1
            finish[A[i]] = False
 
print(ans)

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline()

n=int(input())
A=list(map(int,input().split()))
cnt=[0]*(10**6)
ans=0
for a in A:
  if cnt[a]!=0:
    cnt[a]=2
    continue
  x=a
  while x<10**6:
    cnt[x]+=1
    x+=a
for a in A:
  if cnt[a]==1:
    ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import time
#from collections import deque, Counter, defaultdict
#from fractions import gcd
import bisect
#import heapq
import math
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
inf = 10**18
MOD = 1000000007
ri = lambda : int(input())
rs = lambda : input().strip()
rl = lambda : list(map(int, input().split()))
n = rl()
a=rl()
a.sort()
b=[0]*(10**6)
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]

for i in a:
    f=True
    if b[i]==-1:
        b[i]=1
        continue
    for j in make_divisors(i):
        if b[j]==-1:
            f=False
            break
    if f:
        b[i]=-1
cnt=0
for i in b:
    if i==-1:
        cnt+=1
print(cnt)

Submission status: Runtime Error

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

kazu=[0]*(10*6+1)
for i in a_uni:
  for j in range(1,len(a_uni), i):
    kazu[j] += 1

count = 0
for i in a_uni:
  if kazu[i] == 1:
    count += 1
print(count)

Submission status: Runtime Error

Solution code:
N = int(input())
a = list(map(int,input().split()))
a2 = sorted(a)
c = 0
for i in range(N-1):
  d =0 #カウンタの初期化
  for j in range(i+1):
    if a2[i+1] % a2[j] == 0:
      d =1
      break
    if a2[i+1]-a2[j]^2<0:
      break
  if d == 0:
    c =c+1
if not a2[0] ==a2[1]:
  c = c+1
print(c)

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)
    a_max = a[n-1]
    is_prime = [True] * 2 * 10**5
    is_prime[0] = False
    is_prime[1] = False
    count = [0] * 2 * 10**5
    
    for i in range(n):
        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
    
    print(sum(count))
    

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
alst = list(map(int, input().split()))
alst.sort()
tmp = [0 for _ in range(10 ** 6 + 1)]
ans = 0
if alst[0] == 1:
    if n == 1:
        print(1)
    elif alst[1] == 1:
        print(0)
    else:
        print(1)
    exit()
for num in alst:
    if tmp[num] == 2:
        if flg:
            ans -= 1
            flg = False
        continue
    flg = True
    if tmp[num] == 1:
        continue
    ans += 1
    tmp[num] = 2
    xx = num * 2
    while xx <= 10 **  6 + 1:
        tmp[xx] = 1
        xx += num
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import time
#from collections import deque, Counter, defaultdict
#from fractions import gcd
import bisect
#import heapq
import math
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
inf = 10**18
MOD = 1000000007
ri = lambda : int(input())
rs = lambda : input().strip()
rl = lambda : list(map(int, input().split()))
n = rl()
a=rl()
a.sort()
b=[0]*(2*10**5+1)
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]

for i in a:
    f=True
    if b[i]==-1:
        b[i]=1
        continue
    for j in make_divisors(i):
        if b[j]==-1:
            f=False
            break
    if f:
        b[i]=-1
cnt=0
for i in b:
    if i==-1:
        cnt+=1
print(cnt)

Submission status: Runtime Error

Solution code:
N=int(input())
l=list(map(int,input().split()))
l=[x for x in set(l) if not l.count(x) > 1]
count=0
l.sort(reverse=True)
M=max(l)
tmp=[0]*(M+1)
if not l:
    print(0)
else:
    for i in l:
        for j in range(i,M+1,i):
            tmp[j]+=1
    for i in l:
        if tmp[i]==1:
            count+=1
    print(count)

Submission status: Runtime Error

Solution code:
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
dp = [True] * (10 ** 6 + 1)
s = list(set(a))
for x in s:
    e = x * 2
    while e <= 10 ** 6:
        dp[e] = False
        e += x
ret = 0
for x in a:
    if c[x] == 1 and dp[x] == True:
        ret += 1
print(ans)

Submission status: Runtime Error

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
 
mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000
 
d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))
 

"""
3
1 1 2
のパターンが例外だった
"""

N = int(input())
A = LI()
A.sort()

table = [0 for i in range(2 * 10 ** 5 + 1)]
cnt = 0
for a in A:
    if table[a] != 0:
        pass
    else:
        cnt += 1
        for i in range(2 * 10 ** 5):
            if a * i > 2 * 10 ** 5:
                break
            table[a * i] = 1

A_dic = collections.Counter(A)
for key in A_dic.keys():
    if A_dic[key] > 1:
        cnt -= 1
    
print(cnt)

Submission status: Runtime Error

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

rmlst = []
i =1
while(i<len(A)):
    if A[i] == A[i-1]:
        rmlst.append(A[i-1])
        A.pop(i)
    else:
        i += 1

rmlst = list(set(rmlst))

# A[0]は最小なので同じ数字を除いてそれよりも大きい他の数では割り切れない。
i = 0

while(i < len(A)):
    j = i+1
    poplist = []
    while(j < len(A)):
        if A[j]%A[i] == 0: # 割り切れちゃった場合
            # A[j]をあとで消すために控える
            poplist.append(j)
                
        j += 1
        
    # poplistにあるA[]を消す
    # 前から消していくと順番が狂うので、後ろから消す。参考↓
    # https://gammasoft.jp/blog/remove-multiple-elements-from-python-list/
    for k in sorted(poplist, reverse=True):
        A.pop(k)
    # A[i]で割り切れるものは探しきって、次のA[i+1]は割り切れないもの。
    # 次はA[i+1]について考える
    i += 1

for i in rmlst:
    A.remove(i)

# print(A)
print(len(A))
# print(dellist)

Submission status: Runtime Error

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

kazu=[0]*(10**6)
for i in a_uni:
  for j in range(10**6):
    if i*j >= 10 ** 6:
      break
    kazu[i*j] += 1

count = 0
for i in a_uni:
  if kazu[i] == 1:
    count += 1
print(count)

Submission status: Runtime Error

Solution code:
import sys
import time
#from collections import deque, Counter, defaultdict
#from fractions import gcd
import bisect
#import heapq
import math
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
inf = 10**18
MOD = 1000000007
ri = lambda : int(input())
rs = lambda : input().strip()
rl = lambda : list(map(int, input().split()))
n = rl()
a=rl()
a.sort()
b=[0]*(2*10**5+1)
ans=[]
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]

for i in a:
    f=True
    if b[i]==-1:
        b[i]=1
        continue
    for j in make_divisors(i):
        if b[j]==1:
            f=False
            break
    if f:
        b[i]=-1
cnt=0
for i in b:
    if i==1:
        cnt+=1
print(cnt)

Submission status: Runtime Error

Solution code:
import sys
import collections
import sympy

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline

def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    aset = list(set(A))
    aset.sort()

    past = set()
    ans = 0
    ansset = set()
    for a in aset:
        divs = sympy.divisors(a)
        for div in divs:
            if div in past:
                break
        else:
            ansset.add(a)
            ans += 1

        past.add(a)

    c = collections.Counter(A)
    for cc in c.most_common():
        if cc[1] == 1:
            break

        if cc[1] > 1 and cc[0] in ansset:
            ans -= 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
dp = [0]*(1000000+1)
cnt = 0
for i in range(len(a)):
  if dp[a[i]]==1:
    continue
  while(a[i]*j<=a[-1]):
    dp[a[i]*j] = 1
    j += 1
  if i!=len(a)-1 and a[i+1]==a[i]:
    dp[a[i]] = 1
    continue
  cnt += 1
  dp[a[i]] = 1
  j = 2
print(cnt)

Submission status: Runtime Error

Solution code:
from collections import deque,defaultdict
import sys
input = sys.stdin.readline

def min_kinder(kinder_max):
  ret = float('inf')
  for x in kinder_max:
    if x==0:
      continue
    else:
      ret = min(ret,x)
  return(ret)
N,Q = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]
CD = [list(map(int,input().split())) for _ in range(Q)]
kinder = [defaultdict(int) for _ in range(2*10**5 + 5)]
kinder_max = [0] * (2*10**5 + 5)
kinder_num = [0] * (2*10**5 + 5)

for a,b in AB:
  kinder[b][a] += 1
  kinder_max[b] = max(kinder_max[b], a)
  kinder_num[b] += 1
  
equality = min_kinder(kinder_max)
for c,d in CD:
  a,b = AB[c-1]
  AB[c-1][1] = d
  kinder[b][a] -= 1
  kinder[d][a] += 1
  kinder_num[b] -= 1
  kinder_num[d] += 1
  
  if (kinder_max[b]==equality)or(kinder_max[d]==equality):
    judge = True
  else:
    judge = False
  
  if kinder_max[b]==a:
    if kinder[b][a]!=0:
      pass
    else:
      x = 0
      for key,value in kinder[b].items():
        if value<=0:
          continue
        else:
          x = max(x,key)
      kinder_max[b] = x

  kinder_max[d] = max(kinder_max[d], a)

    
  print(equality)

Submission status: Runtime Error

Solution code:
# coding=UTF-8
from collections import deque
from operator import itemgetter
from bisect import bisect_left, bisect
import itertools
import sys
import math
import numpy as np
import time
sys.setrecursionlimit(10**6)


def main():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    ans = 0
    max_a = max(a)
    arr = [1] * (max_a + 1)

    for num in a:
        if a.count(num) > 1:
            arr[num] = 0
        for i in range(num*2, max_a+1, num):
            arr[i] = 0

    for i in range(n):
        if arr[a[i]] == 1:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np

N = int(input())
A_list = list(map(int, input().split()))
ans_list =np.ones(N)
A_list = np.array(A_list)

for i in range(N-1):
    for j in range(i+1,N):
        if A_list[i] %  A_list[j] == 0:
            ans_list[i] = 0
            if (A_list[j] %  A_list[i] == 0):
                ans_list[j] = 0
        elif(A_list[j] %  A_list[i] == 0):
            ans_list[j] = 0
print(int(np.sum(ans_list)))

Submission status: Runtime Error

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

N = int(input())
A_list = list(map(int, input().split()))
ans_list =np.ones(N)
A_list = np.array(A_list)

for i in range(N-1):
    for j in range(i+1,N):
        if A_list[i] %  A_list[j] == 0:
            ans_list[i] = 0
            if (A_list[j] %  A_list[i] == 0):
                ans_list[j] = 0
        elif(A_list[j] %  A_list[i] == 0):
            ans_list[j] = 0
print(int(np.sum(ans_list)))

Submission status: Runtime Error

Solution code:
N = int(input())
A_list = list(map(int, input().split()))
ans_list =[0] *　N

for i in range(N-1):
    for j in range(i+1,N):
        if A_list[i] %  A_list[j] == 0:
            ans_list[i] = 0
            if (A_list[j] %  A_list[i] == 0):
                ans_list[j] = 0
        elif(A_list[j] %  A_list[i] == 0):
            ans_list[j] = 0
print(int(sum(ans_list)))

Submission status: Runtime Error

Solution code:
import bisect

n = int(input())
a = list(map(int, input().split()))
a.sort()
k = len(a)
ok = [0] * k
for i in range(k):
    if i < k - 1 and a[i] == a[i + 1]:
        ok[i] = 1
        ok[i + 1] = 1
        continue
    """"if a[i] < 2 * 100:
        for j in range(i + 1, k):
            if a[j] % a[i] == 0:
                ok[j] = 1"""
    else:
        times = 2
        while a[i] * times < a[-1]:
            l = bisect.bisect_left(a, a[i] * times)
            r = bisect.bisect_right(a, a[i] * times)
            if r != l:
                for idx in range(l, r):
                    ok[idx] = 1
            times += 1
# print(ok)
print(len([i for i in ok if i == 0]))
# print(ok) WAはどこ？

Submission status: Runtime Error

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

N = int(input())
A_list = list(map(int, input().split()))
ans_list =[0] *　N

for i in range(N-1):
    for j in range(i+1,N):
        if A_list[i] %  A_list[j] == 0:
            ans_list[i] = 0
            if (A_list[j] %  A_list[i] == 0):
                ans_list[j] = 0
        elif(A_list[j] %  A_list[i] == 0):
            ans_list[j] = 0
print(int(sum(ans_list)))

Submission status: Runtime Error

Solution code:
n = int(input())

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

a.sort()

dp = [True] * a[-1]

ans = 0

m = a[-1]

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

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

print(ans)

Submission status: Runtime Error

Solution code:
# 幅優先探索（行きがけ）
import collections
import sys
import math
import copy
import collections


def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())


def main():
    N = I()
    AArry = LI()
    AArry.sort()
    count = 0
    li = [0 for _ in range(10**6+2)]

    for i, v in enumerate(AArry):
        a = v
        if li[a] == 1:
            count += 1
        if li[a] == 0:
            if i != N-1 and AArry[i+1] == a:
                ans += 1

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

    print(N-count)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    ans = 0
    c = Counter()
    ma = max(A)
    for a in A:
        for i in range(ma//a + 1):
            c[a*i] += 1

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

    return ans


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))



if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
a.sort()
ans = 0
con = False
for i in range(1, n):
    if a[i] == a[i-1]:
        con = True
        a[i-1] = 0
    elif con:
        con = False
        ans -= 1
if con:
    ans -= 1

ng = [0] * 201000
for i in range(n):
    if not a[i]:
        continue
    if not ng[a[i]]:
        ans += 1
        for j in range(1, 201000//a[i]):
            ng[a[i]*j] = 1
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
*A, = map(int, input().split())
# 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:
        tmp = 2
        while a * tmp <= maxA:
            D[a * tmp] = 1
            tmp += 1
ans = 0
for a in A:
    if C[a] == 1 and D[a] == 0:
        ans += 1
print(ans)

Submission status: Runtime Error

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

n_max = a_lst[-1]

cnt =0
for i in range(len(a_lst)-1,-1,-1):
    for j in range(i-1,-1,-1):
        if a_lst[i]%a_lst[j]==0:
            cnt += 1
            #print([i,j])
            break
if a_lst[0] == a_lst[1]:
    cnt += 1
            
print(len(a_lst)-cnt)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import collections
n=int(input())
a=list(map(int,input().split()))
a=collections.Counter(a)
b,c=[],[]
for t in a:
  if a[t]==1:
    b.append(t)
  else:
    c.append(t)
if len(b) == 0:
  print(0)
  exit()
b.sort()
bm = b[-1]
ok = [True]*(bm+1)

if len(c)>0:
  c.sort()
  for t in c:
    if ok[t] == False: continue
    i = 1
    while i*t<=bm:
      ok[i*t]=False
      i+=1
for t in b:
  if ok[t] == False: continue
  i = 2
  while i*t<=bm:
    ok[i*t]=False
    i+=1
ans = 0
for t in b:
  if ok[t]:
    ans+=1
print(ans)

Submission status: Runtime Error

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

    a.sort()

    dp = [True]*int(1e6)

    for i in a:
        if i*2 > len(dp):
            pass
        if dp[i*2-1]==False:
            pass
        else:
            for j in range(2*i-1, len(dp), i):
                dp[j] = False


    count = 0
    for i in set(a):
        if len(set(a))==1:
            break
        if dp[i-1]==True:
            count += 1

    print(count)

Submission status: Runtime Error

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

n_max = a_lst[-1]

cnt =0
for i in range(len(a_lst)-1,-1,-1):
    for j in range(i-1,-1,-1):
        if a_lst[i]%a_lst[j]==0:
            cnt += 1
            ＃print([i,j])
            break
if a_lst[0] == a_lst[1]:
    cnt += 1
            
print(len(a_lst)-cnt)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
m = max(a)
l = [True]*max(a)

ans=0
a.sort()
if a[0]==a[1]:
    l[a[0]-1]=False
for i in a:
    if l[i-1]:
        ans+=1
        tmp = i
        while tmp<=m:
            l[tmp-1] = False
            tmp+=i
    #print(l)
    #print(ans)
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
a = map(int, input().split())
a = list(sorted(a))
big = a[n-1]
mark = [0]*big
for x in a:
  mark[x] += 1
  if mark[x] > 1:
    continue
  for j in range(x*2, big+1, x):
    mark[j] += 1

ans = 0
for x in a:
  if mark[x] == 1:
    ans += 1

print(ans)

Submission status: Runtime Error

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

def MakeDivisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

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

if a[0]==2:
    for i in range(1,n):
        if(a[i]%2==0):
            taboo[i]=1
if a[0]==3:
    for i in range(1,n):
        if(a[i]%3==0):
            taboo[i]=1
if a[1]==3:
    for i in range(2,n):
        if(a[i]%3==0):
            taboo[i]=1
if a[0]==5:
    for i in range(1,n):
        if(a[i]%5==0):
            taboo[i]=1
if a[1]==5:
    for i in range(2,n):
        if(a[i]%5==0):
            taboo[i]=1
#print(a)
#print(taboo)




for i in a:
    #print(i)
    if(taboo[co]==1):
        co+=1
        continue
    t = MakeDivisors(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 math
num = int(input())
arr = input().split()
arr = sorted([int(i) for i in arr])
arr = list(set(arr))

lis1 = [0]*(arr[-1]+1)

for num in arr:
  for j in range(0, len(lis1), num):
    lis1[j] += 1

cnt = 0
for num in arr:
  if lis1[num]==1: cnt+=1
    
print(cnt)

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
A=sorted(A)[::-1]
if A[-1]==A[-2]:
    ans=-1
else:
    ans=0
B=[]
while A:
    x=A.pop()
    B.append(x)
    for i in A[::-1]:
        if i%x==0:
            A.remove(i)
print(len(B)+ans)

Submission status: Runtime Error

Solution code:
from collections import Counter
N=int(input())
A=list(map(int,input().split()))
A=sorted(A)[::-1]
if A[-1]==A[-2]:
    ans=-1
else:
    ans=0
B=[]
while A:
    x=A.pop()
    B.append(x)
    for i in A[::-1]:
        if i%x==0:
            A.remove(i)
print(len(B)+ans)

Submission status: Runtime Error

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

b = souted(set(a))

maxA = max(b)
dp = [0]*(maxA+1)
count = 0

for e in b:
    for i in range(e,maxA+1,e):
        dp[i] += 1

for e in b:
    if dp[e] == 1:
        count += 1

print(count)

Submission status: Runtime Error

Solution code:
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int main(){
    int n;
    cin >> n;
    int Amax = 1000001;
    vector<int> A(Amax,0);
    
    for(int i=0;i<n;i++){
        int a;
        cin >> a;
        A[a]++;
    }

    int ans = 0;
    bool B[Amax];
    for(int i=0;i<Amax;i++){
        if(A[i]==1){
            B[i] = true;
        }else{
            B[i] = false;
        }
    }

    for(int i=1;i<Amax;i++){
        if(B[i]){
            ans++;
            
            for(int j=i*2;j<Amax;j+=i){
                if(B[j]){
                    B[j] = false;
                }
            }
        }
    }
    cout << ans << endl;
}

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int, input().split()))
A.sort()
inf=10**2+1
t=[True for i in range(inf)]

ans=0
for j in range(len(A)):
    if j==len(A)-1 and t[A[j]]:
        ans+=1
    if t[A[j]] and j+1<=N-1 and A[j+1]!=A[j]:
        ans+=1
        for nums in range(A[j],inf,A[j]):
            t[nums]=False
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import math
import collections
import decimal
import itertools
from collections import deque
from functools import reduce
import heapq
n = int(input())
#x, y = map(int, sys.stdin.readline().split())
#s = input()
a = list(map(int, sys.stdin.readline().split()))
     
def make_divisors(n):
    i = 1
    while i*i <= n:
        if n % i == 0:
            p = i
            q = n//i
            if p in d:
                return 0
            if q in d:
                return 0
        i += 1
    return 1

a.sort()
ans = 0
if a[0] == a[1]:
    ans -= 1
d = {}
for j in range(n):
    ans += make_divisors(a[j])
    d[a[j]] = a[j]

print(ans)

Submission status: Runtime Error

Solution code:
import math

def main():
  N = int(input())
  A = list(map(int, input().split()))
  MAX = A[-1]
  dp = [True] * MAX
  c = [0] * MAX
  ans = 0

  A.sort()

  for v in A:
    c[v - 1] += 1

    if(not dp[v - 1] and c[v - 1] > 1):
      continue

    e = v * 2    
    while e < MAX:
      dp[e-1] = False
      e += v
      
  for v in A:
    if dp[v - 1] and c[v - 1] == 1:
      ans += 1

  print(ans)

if __name__ == "__main__":
  main()

Submission status: Runtime Error

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

maxA = max(a)
count = 0

for e in a:
    for i in range(e,maxA+1,e):
        dp[i] += 1
        
for e in a:
    if dp[e] == 1:
        count += 1

print(count)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))
m = max(A)
U = [0]*(m+1)
for e in A:
    U[e] += 1
ans = 0
for k in range(1,m)+1):
    if U[k] == 1:
        ans += 1
    if U[k] > 0:
        for l in range(2*k,m+1,k):
            if U[l] > 0:
                U[l] += 1
print(ans)

Submission status: Runtime Error

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

    a.sort()

    dp = [True]*int(1e6)

    for i in a:
        if dp[i*2-1]==False:
            pass
        else:
            for j in range(2, int(len(dp)/i)):
                dp[i*j-1] = False


    count = 0
    for i in set(a):
        if len(set(a))==1:
            break
        if dp[i-1]==True:
            count += 1

    print(count)

Submission status: Runtime Error

Solution code:
N = int(input())

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


b = sorted(list(A))
dp = [0]*(max(A)+4)

m_a = max(A)
for i in b:
    dp[i] += 1
    if dp[i]==1 :
        for j in range(i*2, m_a,i):
            dp[j*i] +=100

print(dp.count(1))

Submission status: Runtime Error

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

l = [0]*(2*10**5+1)

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