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:
def examA():
    X = LI()
    for i in range(len(X)):
        if X[i]==0:
            ans = i+1
    print(ans)
    return

def examB():
    X, Y = LI()
    ans = "No"
    for i in range(X+1):
        if i*2+(X-i)*4==Y:
            ans = "Yes"
    print(ans)
    return

def examC():
    X, N = LI()
    P = LI()
    P = set(P)
    cur = inf
    ans = -1
    for i in range(-1,102):
        if i in P:
            continue
        now = abs(i-X)
        if now<cur:
            ans = i
            cur = now
    print(ans)
    return

def examD():
    N = I()
    A = LI()
    C = set()
    D = set()
    for a in A:
        if a in D:
            C.discard(a)
            continue
        D.add(a)
        C.add(a)
    if 1 in D:
        if 1 in C:
            print(1)
        else:
            print(0)
        return
    C2 = deepcopy(C)
    for a in C:
        for i in range(2,1+n//a):
            if (i*a) in C2:
                C2.discard(i*a)
    ans = len(C2)
    print(ans)
    return

def examE():
    N, Q = LI()
    AB = [LI()for _ in range(N)]



    ans = 0
    print(ans)
    return

def examF():
    H, W, K = LI()
    x1,y1,x2,y2 = LI()
    x1 -= 1; y1 -= 1; x2 -= 1; y2 -= 1
    C = [SI()for _ in range(H)]

    def bfs_grid(h, w, s, maze):
        distance = [[inf] * w for _ in range(h)]

        def bfsg():
            queue_up = deque()
            queue_d = deque()
            queue_r = deque()
            queue_l = deque()
            queue_up.append(s)
            queue_d.append(s)
            queue_r.append(s)
            queue_l.append(s)
            distance[s[0]][s[1]] = 0
            while (len(queue_up) or len(queue_r) or len(queue_d) or len(queue_l)):
                if queue_up:
                    y, x = queue_up.popleft()
                    for k in range(1, K + 1):
                        nx, ny = x, y + k
                        if (0 <= nx < w and 0 <= ny < h and maze[ny][nx] != '@'):
                            if distance[ny][nx] <= distance[y][x] + 1:
                                continue
                            queue_r.append((ny, nx))
                            queue_l.append((ny, nx))
                            distance[ny][nx] = distance[y][x] + 1
                        else:
                            break
                        if k == K:
                            queue_up.append((ny, nx))
                if queue_d:
                    y, x = queue_d.popleft()
                    for k in range(1, K + 1):
                        nx, ny = x, y - k
                        if (0 <= nx < w and 0 <= ny < h and maze[ny][nx] != '@'):
                            if distance[ny][nx] <= distance[y][x] + 1:
                                continue
                            queue_r.append((ny, nx))
                            queue_l.append((ny, nx))
                            distance[ny][nx] = distance[y][x] + 1
                        else:
                            break
                        if k == K:
                            queue_d.append((ny, nx))
                if queue_r:
                    y, x = queue_r.popleft()
                    for k in range(1, K + 1):
                        nx, ny = x + k, y
                        if (0 <= nx < w and 0 <= ny < h and maze[ny][nx] != '@'):
                            if distance[ny][nx] <= distance[y][x] + 1:
                                continue
                            queue_up.append((ny, nx))
                            queue_d.append((ny, nx))
                            distance[ny][nx] = distance[y][x] + 1
                        else:
                            break
                        if k == K:
                            queue_r.append((ny, nx))
                if queue_l:
                    y, x = queue_l.popleft()
                    for k in range(1, K + 1):
                        nx, ny = x - k, y
                        if (0 <= nx < w and 0 <= ny < h and maze[ny][nx] != '@'):
                            if distance[ny][nx] <= distance[y][x] + 1:
                                continue
                            queue_up.append((ny, nx))
                            queue_d.append((ny, nx))
                            distance[ny][nx] = distance[y][x] + 1
                        else:
                            break
                        if k == K:
                            queue_l.append((ny, nx))

            return distance

        return bfsg()
    L = bfs_grid(H,W,(x1,y1),C)
    #print(L)
    ans = L[x2][y2]
    if ans==inf:
        ans = -1
    print(ans)
    return

from decimal import Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Runtime Error

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

if A[0] % A[1] != 0:
    result += 1

for i in range(1,N):
    flag = False
    temp = A[i]
    for j in range(len(A[:i])):
        if temp % A[j] == 0:
            flag = True
            break
    if flag == False:
        result += 1

print(result)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

B = []
for i in range(N-1):
    a = A[i]
    if a != A[i+1]:
        B.append(a)
if A[-1] != A[-2]:
    B.append(A[-1])
if len(B) == 0:
    print(0)
    quit()
b = B[-1]
X = set(primes(b))
A = set(B)
B = list(A&X)
A = list(A-X)
A.sort()
B.sort()
ans = []
while len(A) > 1:
    a = A[0]
    C = []
    if a != A[1]:
        ans.append(a)
    for aa in A:
        if aa % a != 0:
            C.append(aa)
    A = C
ans1 = []
for gen in ans:
    for b in B:
        if gen % b == 0:
            break
        if b > gen:
            ans1.append(gen)
            break
print(len(ans1)+len(B))

Submission status: Runtime Error

Solution code:
N=list(map(int,input().split()))
A=list(map(int,input().split()))
A=list(set(A))
A.sort()
 
ans=[]
for a in A:
    for ans_idx in range(len(ans)+1):
        if ans_idx == len(ans):
            ans.append(a)
            ans_.append(a)
            break
            
        ans_temp=ans[ans_idx]
        if a % ans_temp == 0:
            break
        
print(len(ans))

Submission status: Runtime Error

Solution code:
N = int(input())
nokori = N
kaburi = set()
ans = 0
A = list(map(int,input().rstrip().split(" ")))
A2 = set()
for i in A:
    if i in A2:
        kaburi.add(i)
    else:
        A2.add(i)
for i in kaburi:
    A2.remove(i)
for i in kaburi:
    k = i
    for i2 in A2:
        if i2 % K == 0:
            A2.remove(i2)
while len(A2) != 0:
    i = min(A2)
    ans += 1
    k = i
    for i2 in A2:
        if i2 % K == 0:
            A2.remove(i2)
print(ans)

Submission status: Runtime Error

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

# 重複削除
a = list(set(a))
if len(a) <= 1:
    print(0)
    exit()

a.sort()
ans = []

for i in range(n):
    flg = True
    for j in range(i):
        if i == j: continue
        if a[i] % a[j] == 0:
            flg = False
            break
    if flg:
        ans.append(i)
print(len(ans))

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
a = list(map(int,readline().split()))
a.sort()
if a[0] == a[-1]:
  if n > 1:
    print(0)
  else:
    print(1)
  exit()

def divisorize(fct):
    b, e = fct.pop()
    pre_div = divisorize(fct) if fct else [[]]
    suf_div = [[(b, k)] for k in range(e + 1)]
    return [pre + suf for pre in pre_div for suf in suf_div]
 
 
def factorize(n):
    fct = []
    b, e = 2, 0
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct
 
 
def num(fct):
    a = 1
    for base, exponent in fct:
        a = a * base**exponent
    return a
    
s = set()
if a[0] < a[1]:
  ans = 1
else:
  ans = 0
s.add(a[0])
for i in a[1:]:
  c = set()
  fct = factorize(i)
  for div in divisorize(fct):
      c.add(num(div))
  if c&s == set():
    ans += 1
  s.add(i)

print(ans)

Submission status: Runtime Error

Solution code:
#D
'''
24,11,8,3,16を降順にソートし、24,16,11,8,3とする。
このとき、例えば11について検討するとき、11より大きい数字は
明らかに11を割り切れないので、これは無視してよい
'''
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
counter = 0
if A[-1]==A[-2]:
    counter += 1
def candiv(A):
    can_divide = False
    for i in range(1,len(A)):
        if A[0]%A[i]==0:
            can_divide = True
            break
    return can_divide
for i in range(N):
    if candiv(A):
        counter += 1
        #print(i,counter)
    A=A[1:]
print(N-counter)

Submission status: Runtime Error

Solution code:
_n = int(input())
_a = list(map(int, input().split(" "))).sort
_counter = 0

for _i in range(_n):
  for _j in range(_n):
    if _i != _j and _a[_i] % _a[_j] == 0:
      break
    elif _j == _n - 1:
      _counter += 1
print(_counter)

Submission status: Runtime Error

Solution code:
N = int(input())

A = [int(x) for x in input().split()]
A = sorted(A)
A = list(set(A))

if len(A) == 1:
    print(0)
else:
    if A[0] == A[1]:
        cnt = 0
    else:
        cnt = 1
    
    for i in range(1,N):
        flag = True
        for j in range(i):
            if A[i]%A[j] == 0:
                flag = False
                break

    
        if flag == True:
            cnt += 1
    print(cnt)

Submission status: Runtime Error

Solution code:
from collections import Counter
def check(n, l):
    cnt = 0
    x = Counter(l)
    for i in x.values():
        if i >= 2:
            cnt += i
    l = list(set(l))
    l.sort(reverse=True)
    if len(l) >= 2:  
        for i in range(n):
            for j in range(n-1, i, -1):
                if l[i]%l[j] == 0:
                    cnt += 1
                    break
    return cnt

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

    o = []
    e = []
    for i in range(n):
        if a[i]%2==0:
            e.append(a[i])
        else:
            o.append(a[i])

    cnt = check(len(o), o) + check(len(e), e)

    return n - cnt
    



print(solve())

Submission status: Runtime Error

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

A.sort()

x = A[0]
flag = True
for a in A:
    if a % x != 0:
        flag = False
if flag:
    print(0)
    exit()

used = [False] * A[-1]
ans = 0
for idx, a in enumerate(A):
    if used[a - 1]:
        continue
    if idx < n and a != A[idx + 1]:
        ans += 1
    for j in range(a, len(used) + 1, a):
        used[j - 1] = True
print(ans)

Submission status: Runtime Error

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

As.sort(reverse=True)
As = [A for A in As if As.count(A) == 1]
  
def func(lst):
  if lst == []:
    return 0
  else:
    if [a for a in lst if lst[0] % a == 0] == [lst[0]]:
      return 1 + func(lst[1:])
    else:
      return func(lst[1:])

print(func(As))

Submission status: Runtime Error

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

a.sort(reverse=True)
count = 0

for i in range(n):
  for i2 in range(i+1,n):
    if a[i]%a[i2] == 0:
      count-=1
      break
  count+=1
if a[-1]%a[-2]==0:
  count-=1
print(count)

Submission status: Runtime Error

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

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

if a[0]==1:
    if a[1]==1:
        print(0)
    else:
        print(1)
else:
    ans = 0
    for num in a:
        if a.count(num) >= 2:
            continue
        else:
            cands = set([i for i in a if i!=num])
            divs = set(make_divisors(num))
            if not cands&divs:
                ans+=1
            
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 8)

n = int(input())
a = list(map(int, input().split()))
a.sort()
l = [0] * (n+1)
cnt = 0
if a[0] == a[1]:
  l[n] = 1
for i in range(1, n):
  for j in range(1, i+1):
    if i != n-1:
      if a[i] == a[i+1]:
        cnt += 1
        break
    if l[j-1] == 0:
      if a[i] % a[j-1] == 0:
        l[i] = 1
        break

print(n-sum(l)-cnt)

Submission status: Runtime Error

Solution code:
from collections import Counter
n = int(input())
a = Counter(map(int, input().split()))
ans = n
for num, count in a.items():
    if count > 1:
        ans -= count
        continue
    if 1 in a and num != 1:
        ans -= count
        continue
    i = 2
    if num % i == 0:
            if i in a or (num // i) in a:
                ans -= count
                break
        i += 1
    while i * i <= num:
        if num % i == 0:
            if i in a or (num // i) in a:
                ans -= count
                break
        i += 2
print(ans)

Submission status: Runtime Error

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

def divisor(n): 
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            if i != 1:
                table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table

array = [0] * 10**6
ans = N
A.sort()
# print(A)
for i in range(N):
    flag = True
    # print(divisor(A[i]))
    for a in divisor(A[i]):
        if array[a-1] == 1 and flag == True:
            # print(A[i])
            ans -= 1
            flag = False
    array[A[i]-1] = 1

if ans == 1:
    if A[0] == A[1]:
        print(0)
        exit()

print(ans)

Submission status: Runtime Error

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

ans = 0

for i in range(N):
    tmp = True
    if i == 0:
        if A[i] == A[i+1]: tmp = False
    elif i == N-1:
        if A[i] != A[i-1]:
            for j in range(i):
                if A[i] % A[j] == 0:
                    tmp = False
                    break
        else: 
            tmp = False
    else:
        if A[i] != A[i-1] & A[i] != A[i+1]:
            for j in range(i):
                if A[i] % A[j] == 0:
                    tmp = False
                    break
        else: 
            tmp = False

    if tmp: ans += 1

print(ans)

Submission status: Runtime Error

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

cnt = 0

for i in range(n):
  if i == 0 and a[i+1] == a[i]:
    continue
  elif i == n-1 and a[i-1] == a[i]:
    continue
  elif i > 0 and i < n-1 and (a[i+1] == a[i] or a[i-1] == a[i]):
    continue
  
  flag = True
  for j in range(i):
    if a[i] % a[j] == 0:
      flag = False
      break
  if flag:
    cnt += 1
    
print(cnt)

Submission status: Runtime Error

Solution code:
N = int(input())
A = [int(n) for n in input().split()]
ans = 1

A_set = set(A)
A_set = list(A_set)
if len(A_set) == 1:
    print(0)
else:
    for i in range(N):
        for j in range(i):
            if A_set[i] % A_set[j] == 0:
                break
            if j == i-1:
                ans += 1
    print(ans)

Submission status: Runtime Error

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

A.sort()
ans=N
i=0
while i<len(A):
    if i==0 and A[i]==A[i+1]:
        ans-=1
        i+=1
        continue
    for a in A[:i]:
        if A[i]%a==0:
            ans-=1
            break
        if a>A[i]//2+1:
            break
    i+=1

print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
ans = 0
if A[0] == 1:
    if A[1] == 1:
        ans = 0
    else:
        ans = 1
B = [0] * (10**6 + 1)
for i in range (N):
    if B[A[i]] == 0:
        ans += 1
        if i != N - 1:
            if A[i] == A[i + 1]:
                ans -= 1
        B[A[i]] = 1
        c = A[i]
        d = A[i]
        while c + d <= max(A):
            c = c + d
            B[c] = 1
print(ans)

Submission status: Runtime Error

Solution code:
import sympy
num = int(input())
input_line = list(map(int,input().split(' ')))


ans = num

# flg2 = 0
# flg3 = 0
# if(2 in input_line):
#     flg2 = 1
# if(3 in input_line):
#     flg3 = 1

for i in range(num):
    now = input_line[i]
    # if(now!=2):
    #     if(now%2==0):
    #         if(flg2):
    #             ans-=1
    #             continue
    # if(now!=3):
    #     if(now%3==0):
    #         if(flg3):
    #             ans-=1
    #             continue
    divisor_now = sympy.divisors(now)
    for j in range(num):
        if(i!=j):
            if(input_line[j] in divisor_now):
                ans -= 1
                break

print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
# N=5
# A=[24, 11, 8, 3, 16]
import numpy as np
B=np.array(A*N).reshape(N,N).T%np.array(A)
B=np.sum(B==0,axis=1)
print(np.count_nonzero(B == 1))

Submission status: Runtime Error

Solution code:
from copy import deepcopy

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

ans = 0

if len(set(A)) == 1:
    print(0)
    exit()

# エラトステネスの篩っぽく処理
search_list = deepcopy(A)
ans = 0

tmp = min(search_list)
smax = int(max(search_list)**0.5) + 1

while search_list:
    ans += 1
    search_list = [i for i in search_list if i % tmp != 0]
    tmp = min(search_list)
    if tmp < smax:
        ans += len(search_list)
        break

print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
a = [int(x) for x in input().split()]
a.sort()
if a[0] == a[1]:
    ans = 0
else:
    ans = 1
for i in range(1, n):
    flg = True
    for j in range(i):
        x = a[i]
        y = a[j]
        if x%y == 0:
            flg = False
            break
    if flg:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
 
N = int(input())
x_list = np.array(list(map(int, input().split()))).reshape(1,N)

print(np.sum(np.sum(x_list%x_list.reshape(N,1)==0, axis=0)==1))

Submission status: Runtime Error

Solution code:
n = int(input())
a = [int(_) for _ in input().split()]
flag = 0
a.sort()
ans = []
for i in range(len(a)):
    if i == 0:
        if a[i] == a[i+1]:
            flag = 1
    for j in range(i):
        if a[i]%a[j]==0:
            flag = 1
    if flag == 0:
        ans.append(a[i])
    flag = 0

print(len(ans))

Submission status: Runtime Error

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

S = sorted(A)
print(S)

ans = 0
if S[0] == S[1]:
    for i in range(1, N):
        j = 0
        while S[i] % S[j] > 0:
            j += 1
            if i <= j:
                ans += 1
                break
else:
    ans = 1
    for i in range(1, N):
        j = 0
        while S[i] % S[j] > 0:
            j += 1
            if i <= j:
                ans += 1
                break
print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
A=sorted(map(int,input().split()))
L=[A[0]]

c=0
if A[0]!=A[1]:
    c=1
for i in range(n-1):
    flag=0
    for l in L:
        if A[i+1]%l==0:
            flag=1
            break
    if flag==0:
        L.append(A[i+1])
        c+=1
print(c)

Submission status: Runtime Error

Solution code:
import numpy as np

n=int(input())
a = np.array(list(map(int, input().split())))
a=np.append(0,a)
ans=0
b=np.cumsum(a))
for i in range(n):
    for j in range(n):
      if a[i]%(b[j+1]-b[j])==0 and i!=j:
          break
      if j==n-1:
          ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
p = [a[0]]
for i in range(1,n):
    v = 1
    for j in range(len(p)):
        if a[i] % a[j] == 0:
            v = 0
            break
    if v == 1:
        p.append(a[i])
ans = len(p)
for i in range(n-2):
    if a[i] == a[i+1] and a[i+1] != a[i+2]:
        ans -= 1
if a[-1] == a[-2]:
    ans -= 1
print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
a=sorted(list(map(int,input().split())))
count=0
if a[0]!=a[1]:
  count+=1
b=[a[0]]
for i in range(1,n):
  if i !=n-1:
    if a[i]==a[i+1]:
      if b[-1]!=a[i]:
        b.append(a[i])
      continue
  for j in b:
    if a[i]%j==0:
      break
    if j>a[i]//2:
      count+=1
      b.append(a[i])
      break
    if j==b[-1]:
      count+=1
      b.append(a[i])
      break
print(count)

Submission status: Runtime Error

Solution code:
import sympy

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

if a[0]==1:
    if a[1]==1:
        print(0)
    else:
        print(1)
else:
    ans = 0
    for num in a:
        if a.count(num) >= 2:
            continue
        else:
            cands = set([i for i in a if i!=num])
            divs = set(sympy.divisors(num))
            if not cands&divs:
                ans+=1
            
    print(ans)

Submission status: Runtime Error

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

print(n-sum(l)-cnt)

Submission status: Runtime Error

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

a.sort()

is_divisible = [-1] * (2 * (10 ** 5) + 1)
is_divisible[0] = False

ans = 0
for num in a:
    if is_divisible[num] == -1:
        ans += 1
        is_divisible[num] = 0
        for i in range(num * 2, 2 * (10 ** 5) + 1, num):
            is_divisible[i] = 1
    elif is_divisible[num] == 0:
        ans -= 1
        is_divisible[num] = 1
    else:
        continue

print(ans)

Submission status: Runtime Error

Solution code:
s = list(map(int,input().split()))
t = s.pop(0)
s.sort()
d = 0
for i in range(0,t):
  c = 1
  for k in range(0,i):
    if s[i]%s[k]==0:
      c = 0
      break
  if c == 1:
    d = d+1
print(d)

Submission status: Runtime Error

Solution code:
N = int(input())

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



b = sorted(list(set(A)))

x = set(b)

res = x

if b[0]==1:
    print(1)
    exit()

if b[0]==b[-1]:
    print(0)
    exit()


daburi = []

c = sorted(A)
for i in range(1,N):
    if c[i] == c[i-1]:
        daburi.append(c[i])

daburi = set(daburi)
#print(daburi)

i = 0
while len(x) > 0 :
    tmp = b[i]
    for j in range(2,10**5+3):
        c = tmp* j
        if c in x:
            x.discard(c)
        if b[-1] <= c:
            break
    if len(x) == i:
        break
    i+=1
        
#print(x)
#print(daburi)
print((len(x- daburi)))

Submission status: Runtime Error

Solution code:
import sympy

N = int(input())
A = list(map(int, input().split()))
count = 0
for i in range(N):
    if not set(sympy.divisors(A[i])) & set(A[:i] + A[i + 1:]):
        count += 1
print(count)

Submission status: Runtime Error

Solution code:
n = int(input())
a = [int(x) for x in input().split()]
a.sort()
count = 0
if(n == 1):
  print(1)
  sys.exit()
for i in range(1,n):
  flg = False
  for j in range(i):
    if(a[i] % a[j] == 0):
      flg = True
      break
  if(flg == False):
    count += 1

if(a[0] != a[1]):
  count += 1
print(count)

Submission status: Runtime Error

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

MAX_VAL = 2*10**5
prime = [1] * (MAX_VAL+1)
prime[0] = prime[1] = 0
for i in range(2, int(MAX_VAL**0.5)+1):
    if prime[i]:
        for k in range(2*i, MAX_VAL+1, i):
            prime[k] = 0

res = []
for i in range(n):
    if a[i] == a[i-1]:
        if res and a[i] == res[-1]:
            res.pop()
        continue
    if prime[a[i]]:
        res.append(a[i])
        continue

    for v in res:
        if a[i] % v == 0:
            break
    else:
        res.append(a[i])

print(len(res))

Submission status: Runtime Error

Solution code:
#x,n=map(int,input().split())
n=int(input())
lis=list(map(int,input().split()))
#s=input()
lis.sort()
f=1
i=0
while i<len(lis):
  x=lis[i]
  for k in lis[i+1:]:
    if k==x and f:
      lis.remove(k)
      f=0
      i-=1
    else:
      f=1
    if k%x==0:
      try:
        lis.remove(k)
      except:
        pass
  i+=1

print(len(lis))

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
A = list(map(int, input().split()))

a_g = np.zeros((N, N))
for i in range(N):
    for j in range(i+1, N):
        if A[j] % A[i] == 0:
            a_g[i, j] = 1
        if A[i] % A[j] == 0:
            a_g[j, i] = 1
ans = 0
for j in range(N):
    if np.all(a_g[:, j]==0):
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
N=int(input())
A=sorted(list(map(int,input().split())),reverse=True)
cnt=0
for i in range(len(A)-1):
	for j in range(i+1,len(A)):
		if A[i]%A[j]==0:
			break
	else:
		cnt+=1
if A[-2]!=A[-1]:
	cnt+=1
print(cnt)

Submission status: Runtime Error

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

als = sorted(al)
m = als[-1]

from collections import Counter
c = Counter(als)

def sieve_of_eratosthenes(n): #エラトステネスのふるい
    candidate = list(range(2, n+1)) #候補
    prime = []
    limit = n**0.5 + 1 #+1がないと平方数を素数にしてしまう

    while True:
        p = candidate[0] 
        if limit <= p:
            prime.extend(candidate) #この時点での残っているのは素数
            break
        prime.append(p) #pを素数リストに登録

        candidate = [i for i in candidate if i % p != 0]

        # i = 0
        # while True:
            # if i >= len(candidate): #iはcandidateの長さ分
                # break
            # elif candidate[i] % p == 0: #余りがゼロなら
                # candidate.pop(i) #素数ではないのでpop(取り除く)する
            # i += 1

    return prime

prime = sieve_of_eratosthenes(m)

res = 0
kouho =[]
for i in range(n):
    flg = 0
    j = als[i]
    if c[j] >1:
        kouho.append(j)
        pass
    elif j in prime:
        res += 1
        kouho.append(j)
    else:
        for k in kouho:
            if j % k ==0:
                flg = 1
                break
        if flg != 1:
            res += 1
print(res)

Submission status: Runtime Error

Solution code:
import numpy as np
N = list(map(int,input().split()))[0]
A_arr = list(map(int,input().split()))
count = 0
bool_list = np.zeros(int(1e6))
for i in range(N):
  if bool_list[A_arr[i]]:
    continue
  flag_not_div = True
  for j in range(N):
    if i == j:
      continue
    if A_arr[i]%A_arr[j] == 0:
      flag_not_div = False
      break
  if flag_not_div:
    bool_list[A_arr[i]] = True
    count += 1
print(count)

Submission status: Runtime Error

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

    A.sort()
    ans = 0
    temp = 0
    for i in range(N):
        if i == 0 and A[i+1] != A[i]:
            ans += 1
            continue

        temp = A[i]

        if i == N-1 and temp == A[i-1]:
            continue
        elif i != N-1:
            if temp == A[i+1] or temp == A[i-1]:
                continue

        for j in range(N):
            if A[j] <= temp/2 and A[i]%A[j] == 0:
                break
            elif A[j] <= temp//2 and A[i]%A[j] != 0:
                continue
            elif A[j] > temp//2:
                ans += 1
                break
    return ans

print(main())

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
# a = sorted(a)
a.sort()
if a[0] == 1:
    if a[1] == 1:
        print(0)
        exit()
    else:
        print(1)
        exit()
check = True
ans = 0
double = []
for i in range(n):
    if not i == 0:
        if a[i-1] == a[i]:
            double.append(a[i])
    for j in range(0, i):
        if not a[j] == 1:
            if a[j]*2 > a[i]:
                break
        if i == j:
            continue
        if a[i]%a[j] == 0:
            check = False
            break

    if check:
        ans += 1
        # print(i)
    check = True
# print(a)
# print(ans)
# print(double)
for i in set(double):
    ans -= a.count(i)
# ans -= len(set(double))
# ans -= len(double)
print(ans)

Submission status: Runtime Error

Solution code:
cnt=0
ans=[]
ans_=[]
for a in A:
    for ans_idx in range(len(ans)+1):
        if ans_idx == len(ans):
            ans.append(a)
            ans_.append(a)
            break
            
        ans_temp=ans[ans_idx]
        if a % ans_temp == 0:
            if a in ans_:
                ans_.remove(a)
            break
        
print(len(ans_))

Submission status: Runtime Error

Solution code:
import math
n =int(input())

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

flag1 = [1 for i in range(1010)]
flag1[0] = flag1[1] = 0

prime = []

for i in range(2, 1001):
    if flag1[i] == 1:
        prime.append(i)
        j = 2
        while(i*j < 1002):
            flag1[i*j] = 0
            j+= 1

#flag1: isprime

flag_e =  [0 for j in range(1001)]
ans = 0

a.sort()
a.append(10000000)

for i in range(n):
    flag = True
    j = 0
    while(prime[j] < int(math.sqrt(a[i]))+1):
        if (flag_e[prime[j]] == True):
            if (a[i] % prime[j] == 0):
                flag = False
        j+=1;

    if (a[i] == a[i+1] or a[i-1] == a[i]):
        flag = False

    if (flag):
        ans += 1

    j = 0 
    while(prime[j] <= int(a[i])):
        if (flag_e[prime[j]] == 0 and (a[i] % prime[j])==0):
            flag_e[prime[j]] = 1
        j+=1

print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
counter = [0 for _ in range(n)]
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        else:
            if counter[i] > 0:
                continue
            else:
                if a[i] % a[j] == 0:
                    counter[i] += 1:
print(counter.count(0))