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

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

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

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

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

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

    return arr

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

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

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

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


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

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

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

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

    else:
        ret = []

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

        for i in S:

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

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

        return ret

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


# ここから書き始める
n = int(input())
a = sorted(list(map(int, input().split())))
cnt = 0
for i in range(n):
    if a[i] == 1:
        if a[i + 1] != 1:
            cnt += 1
        continue
    d = make_divisors(a[i])[:-1]
    # print(d)
    if len(d) == 1:
        if i == 0 and a[i] != a[i + 1]:
            cnt += 1
        if i == n - 1 and a[i - 1] != a[i]:
            cnt += 1
        if i not in [0, n - 1] and a[i - 1] != a[i] and a[i] != a[i + 1]:
            cnt += 1
        continue
    for j in d:
        if a[bisect_left(a, j)] == j:
            break
    else:
        cnt += 1
print(cnt)

Submission status: Runtime Error

Solution code:
from collections import Counter, deque

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

n_map = {}
c = Counter(a)
a = [k for k, v in c.items() if v == 1]
a.sort()
q = deque(a)

res = 0
def solve(v,c_m):
    global res
    n_q = deque()
    while len(c_m) > 0:
        c = c_m.popleft()
        if c % v != 0:
           n_q.append(c)
    if len(n_q) == 0:
        return
    n_v = n_q.popleft()
    res += 1
    solve(n_v, n_q)


if len(q) > 0:
    v = q.popleft()
    res += 1
    solve(v, q)
print(res)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
n, *a = map(int, open(0).read().split())
a.sort()
ans = not(a[0] == a[1])
for i in range(1, n):
    t = 1
    for j in range(i):
        if a[i] % a[j] == 0:
            t = 0
            break
    ans += t
print(ans)

Submission status: Runtime Error

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

ans = 0

if len(A) > 2:
    for i in range(N):
        for j in range(i):
            if j == i:
                continue
            if A[i] % A[j] == 0:
                break
        else:
            ans += 1

print(ans)

Submission status: Runtime Error

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

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    if A[0]==A[1]:
        ans=0
    else:
        ans = 1
    
    for i in range(1,N):
        for j in range(i):
            if A[i]%A[j]==0:
                break
        else:
            ans+=1
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

for i in range(n):
  if i==0 and a[0]==a[1]:
    ans-=1
    continue
  for j in range(i):
    if a[i]==a[j]:
      ans-=1
      break
    if a[j]>a[i]/2:
      break
    if a[i]%a[j]==0:
      ans-=1
      break
      
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import sympy

N = int(input())
A = list(map(int, input().split()))
# a,b=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
# c=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
# s=[list(map(int,list(input()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

#K = int(input())
#S = input()

##一次元配列の初期化
#a=[0]*5
#[i for i in range(100) if i%2==1] #奇数のみ
##二次元配列の初期化
mod = np.array([[-1 for i in range(N)] for i in range(N)])

count = 0
for i in range(N):
    buf = sympy.divisors(A[i])
    if len(set(A) - set(buf)) == N-1:
        count += 1

#count = 0
#for i in range(N):
#        mod[i] = np.mod(A,A[i])
#for i in range(N):
#    c = list(mod[:,i]).count(0)
#    if c == 1:
#        count += 1
#        
print(count)

Submission status: Runtime Error

Solution code:
import numpy as np
n = int(input())
a = list(map(int, input().strip().split()))

p = np.zeros((n,n))
for i in range(n):
    p[:,i] = a

#for i in range(n):
#    print(p[i,:])

ans = 0
for i in range(n):

    if np.count_nonzero(np.mod(p[i,:],a)) == (n - 1):
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
N = map(int,input().split())
A = list(map(int,input().split()))
A = list(set(A))
A.sort()
k = len(A)
S = 0
while k >= 2:
  k = len(A)
  l = len(A)
  mod = A[0]
  j = 1
  for i in range(l-1):
    temp = A[j]
    if temp%mod == 0:
      A.remove(temp)
    else:
      j+=1
  A.remove(mod)    
  S += 1
  if len(A) == 1:
    S += 1
    break
print(S)

Submission status: Runtime Error

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

count = 0

for i, a in enumerate(A):
    for j in range(i+1, N):
        # print(a, A[j])
        if a % A[j] == 0:
            break
        if j == N -1:
            count += 1
if A[-1] != A[-2]:
    count += 1
print(count)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
cnt = 0
if a[0] == a[1]:
  cnt += 1

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

Submission status: Runtime Error

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

n = int(input())

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

a.sort()
cnt = 0

for i in range(n):
    for j in range(i+1):
        if i==0 and a[i] == a[i+1]:
            cnt += 1
            break
        if a[i]%a[j]==0 and i!=j:
            cnt += 1
            break

print(n-cnt)

Submission status: Runtime Error

Solution code:
from collections import deque
import copy
n=int(input())
a=list(map(int, input().split()))
sort(a)

t=0

for i in range(n):
    for j in range(n):
        if i != j and a[i]>=a[j] and a[i]%a[j] == 0:
            t+=1
            break


print(n-t)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import math
import sympy
from collections import defaultdict


def main():
    n = int(input().strip())
    a_list = map(int, input().split())

    ans_set = set()
    dup_set = set()
    for a in sorted(a_list):
        if a in ans_set:
            dup_set.add(a)
            continue

        divs = set(sympy.divisors(a))
        if divs.isdisjoint(ans_set):
            ans_set.add(a)

    print(len(ans_set) - len(dup_set))


if __name__ == '__main__':
    main()

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
for i in range(1,n):
  for j in range(i):
    if a[i]%a[j]==0:
      break
    if j==i-1:
      count+=1
print(count)

Submission status: Runtime Error

Solution code:
def make_divisors(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

n=int(input())
a=sorted(list(map(int,input().split())))
dic={}
for k in a:
    if k in dic:
        dic[k]=0
        continue
    print(x)
    f=1
    for i in x:
        if i in dic:
            f=0
            break
    if f:
        dic[k]=1
print(sum(dic.values()))

Submission status: Runtime Error

Solution code:
N=int(input())

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

A.sort()

ans = list()

while (len(A)>1):
    B=list()
 
    x=A[0]

    n=len(A)
    for i in range(1,n):
        if A[i] % x != 0:
            B.append(A[i])
    
    if len(B)>0:
        ans.append(x)

    A=B

ans = ans+B
# print(ans)
print(len(ans))

Submission status: Runtime Error

Solution code:
def main():
    N  = int(input()) 
    A=list(map(int, input().split()))
    B = list(set(A))
    _ ,s = sieve(10**6+5)
    B.sort(reverse=True)
    cnt = 0

    if A.count(1)>1:
        print(0)
        return
    elif A.count(1)==1:
        print(1)
        return


    for i in range(len(B)):
        if A.count(B[i])>1:
            continue
        if s[B[i]]==False:
            cnt += 1
            continue

        Flag = True
        for j in range(i+1,len(B)):
            if B[i] % B[j] == 0:
                Flag = False
                break
        if Flag:
            cnt += 1
    
    print(cnt)


def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [ i for i in range(1, n+1) if is_prime[i-1]]
    return is_prime, table



if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def make_divisors(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

n = int(input())
A = sorted(tuple(map(int, input().split())))
if A[0] == 1:
    if A[1] == 1:
        print(0)
    else:
        print(1)
else:
    ans = []
    tyo = []
    for i in range(n):
        flag = True
        if A[i] in tyo:
            continue
        for x in ans:
            if A[i]%x == 0:
                flag = False
                break
        if not flag:
            continue


        if i<n-1:
            if A[i+1] == A[i]:
                tyo.append(A[i])
                continue
        ans.append(A[i])
    print(len(ans))

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
num=[]
count=0

a=sorted(a)

for i in a:
  for j in num:
    if i%j==0:
      count+=1
      break
      
  num.append(i)
  
  
if a[0]==a[1]:
  count+=1
  
print(n-count)

Submission status: Runtime Error

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

    a.sort(reverse=True)
    cnt = 0
    for i in range(n):
        for j in range(n-1, i, -1):
            if a[i]%a[j] == 0:
                cnt += 1
                break
    if a[-2]==a[-1]: cnt+=1

    return n - cnt
    



print(solve())

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
A = list(map(int, input().split()))
A = np.array(A, dtype=int)
B = np.zeros((N, N), dtype=int)
for i, a in enumerate(A):
    B[i] = A % a
    B[i][i] = 1
B_prod = np.prod(B, axis=0)
print(len(np.where(B_prod)[0]))

Submission status: Runtime Error

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict

# import fractions

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = sorted(il(), reverse=True)

    ret = 0
    for i in range(N):
        for j in range(i + 1, N):
            if A[i] % A[j] == 0:
                break
        else:
            if A[j] not in A[:i]:
                ret += 1
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;


int main(void) {
    int n;
    cin >> n;

    auto a = vector<int>(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    
    int cnt = 0;
    auto flags = vector<bool>(n, true);

    for (int i = 0; i < n; i++)
    {
        if (!flags[i])
        {
            continue;
        }
        
        if (i == n - 1 || a[i] != a[i + 1])
        {
            cnt += 1;
        }
        
        for (int j = i + 1; j < n; j++)
        {
            if (flags[j] && a[j] % a[i] == 0)
            {
                flags[j] = false;
            }
        }
    }
    
    cout << cnt << endl;
    
    return 0;
}

Submission status: Runtime Error

Solution code:
import numpy as np
import itertools

x,n = map(int,input().split())
li = list(map(int,input().split()))
li.sort()
if x in li:
    idx = li.index(x)
    i = 0
    while(1):
        i = i+1
        if(idx-i<0):
            print(0)
            break
        if(idx+i>=len(li)):
            print(x+i)
            break
        if(li[idx-i]!=x-i):
            print(x-i)
            break
        elif(li[idx+i]!=x+i):
            print(x+i)
            break
else:
    print(x)

Submission status: Runtime Error

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

if(len(set(a)) == 1):
    print(0)
else:
    a.sort()
    b = [a[0]]
    for i in range(1,n):
        flag = 1
        for j in b:
            if(a[i]%j == 0):
                flag = 0
                break
        if(flag == 1):
            b.append(a[i])

print(len(b))

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

from math import sqrt
from collections import Counter, deque
N = int(input())
As = list(mapint())
As.sort()
C = Counter(As)

MAX = As[-1]
Ps = deque(As)
cnt = 0
for _ in range(N):
    p = Ps.popleft()
    if C[p]>=2:
        continue
    Ps = deque([i for i in Ps if i%p!=0])
    cnt += 1
    if p>=sqrt(MAX):
        break
print(len(Ps)+cnt)

Submission status: Runtime Error

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

if a[0] == a[1]:
    num = n-1
else:
    num = n

for i in range(1, n):
    for j in range(n):
        if i == j:
            continue
        if a[i] % a[j] == 0:
            num -= 1
            break
print(num)

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)
d={}
for a in A:
    if a in d:
        d[a]+=1
    else:
        d[a]=1

ans=0
for i in range(N):
    a=A[i]
    p=1
    if d[a]>1:
        continue
    for j in range(2,int(a**0.5)+1):
        if a%j==0:
            if j in d or a//j in d:
                p=0
                break
    ans+=p

if A[-1]==1:
    if A[-2]>1:
        ans=1
    else:
        ans=0
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)
n=int(input())
a=list(map(int,input().split()))
c=0
x=[]
for i in range(n):
    for j in range(n):
        if a[i]%a[j]!=0:
            c+=1
    x.append(c)
    c=0
z=c.count(n-1)  
print(z)

Submission status: Runtime Error

Solution code:
N = int(input())
*A, = map(int, input().split())
A = list(set(A))
A.sort()
if len(A) == 1:
    print(0)
    exit()
ans = 0
for i in reversed(range(N)):
    b = True
    for j in reversed(range(i)):
        if A[i] % A[j] == 0:
            b = False
    if b:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
count = 0
for i in range(N):
    judge = True
    if i == 0:
        if A[i+1] != A[i]:
            count += 1
        continue
    for j in range(i):
        if A[i] % A[j] == 0:
            judge = False
            break
    if judge:
        count += 1
print(count)

Submission status: Runtime Error

Solution code:
import sympy
from collections import defaultdict, Counter
# def factors(N): #約数を全て求める。ただし、順不同
#     from collections import deque
#     ret = deque()
#     middle = int( N**(1/2))
#     for i in range(1, middle):
#         if N%i == 0:
#             ret.append(i)
#             ret.append(N//i)
            
#     if N%middle == 0:
#         ret.append(middle)
#         if middle != N//middle:
#             ret.append(N//middle)
#     return ret

def main():
    N = int( input())
    A = list( map( int, input().split()))
    CA = Counter(A)
    d = defaultdict( lambda : False)
    for a in A:
        d[a] = True
    ans = 0
    for a in A:
        if CA[a] > 1:
            continue
        for p in sympy.divisors(a):
            if p == a:
                continue
            if d[p]:
                break
        else:
            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()
mx = a[-1]
c = [0 for _ in range(mx+1)]
ans = 0
if a[0] == 1:
  if a[1] == 1:
    print(0)
    exit()
  else:
    print(n)
    exit()
i = 0
while i < n:
  if c[a[i]] == 0:
    p = a[i]
    for _ in range(2,mx//a[i]+1):
      p += a[i]
      c[p] = 1
    flag = True
    while i+1 < n and a[i+1] == a[i]:
      i += 1
      flag = False
    if flag:
      ans += 1
  i += 1
print(ans)

Submission status: Runtime Error

Solution code:
def resolve():
    _ = int(input())
    targets = list(map(int, input().split()))

    targets = [x for x in set(targets) if targets.count(x) == 1]
    if len(targets) == 0:
        print(0)
        return
    targets.sort()
    targets = deque(targets)

    ans = []

    while len(targets) > 0:
        target = targets.popleft()
        ans.append(target)
        removeList = []
        for x in targets:
            if x % target == 0:
                removeList.append(x)
        for x in removeList:
            targets.remove(x)

    print(len(ans))

resolve()

Submission status: Runtime Error

Solution code:

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True


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

D = defaultdict(int)
for a in A:
    D[a] += 1

L = []
for k, v in D.items():
    if v > 1:
        continue
    L.append(k)

if len(L) == 0:
    print(0)
    exit()

L.sort()

ans = set()
for n in L:
    if is_prime(n):
        ans.add(n)
    flg = True
    for s in ans:
        if n % s == 0:
            flg = False
            break
    if flg is False:
        continue
    ans.add(n)

print(len(ans))

Submission status: Runtime Error

Solution code:
n=int(input())
l=list(map(int,input().split()))
l=list(set(l))
l.sort()
ans=0

if len(l)!=1:
    ans=1
    for i in range(1,n):
        ans+=1
        for j in range(i):
            if l[i]%l[j]==0:
                ans-=1
                break
print(ans)

Submission status: Runtime Error

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

if a[0] % a[1] == 0:
    ans -= 1

for i in range(1,n):
    for j in range(i):
        if a[i] % a[j] == 0:
            ans -= 1
            break

print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n=int(input())
A=list(map(int,input().split()))
A.sort()
S=[]
ans=n
if A[0]%A[1]==0:ans-=1
for a in A:
  flag=0
  for s in S:
    if a%s==0:
      ans-=1
      flag=1
      break
  if flag==0:
    S.append(a)
print(ans)

Submission status: Runtime Error

Solution code:
def main():
    N  = int(input()) 
    A=list(map(int, input().split()))
    B = list(set(A))
    _ ,s = sieve(10**6+5)
    B.sort(reverse=True)
    cnt = 0

    if A.count(1)>1:
        print(0)
    elif A.count(1)==1:
        print(1)


    for i in range(len(B)):
        if A.count(B[i])>1:
            continue
        if s[B[i]]==False:
            cnt += 1
            continue

        Flag = True
        for j in range(i+1,len(B)):
            if B[i] % B[j] == 0:
                Flag = False
                break
        if Flag:
            cnt += 1
    
    print(cnt)


def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [ i for i in range(1, n+1) if is_prime[i-1]]
    return is_prime, table



if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
A = sorted(list(map(int,input().split())))
ACP = {i:False for i in range(N)}
count = 0
if A[0] == A[1]:
  count += 1
for i in range(N):
    for j in range(i+1,N):
        if ACP[j]:
            continue
        if (j > 0 and A[j-1] == A[j]) or A[j]%A[i] == 0:
            ACP[j] = True
            count += 1
print(N-count)

Submission status: Runtime Error

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

ret = 0

for i in range(N):
  if sum( [1 for j in range(N) if N[i] % N[j]] ) == 1:
    ret += 1

print( ret )

Submission status: Runtime Error

Solution code:
N = int(input())
A = sorted([int(x) for x in input().split()], reverse=True)
ans = 0
for i, ai in enumerate(A):
    f = 1
    for aj in A[i+1:]:
        if ai % aj == 0:
            f = 0
            break
    ans += f
ans -= (A[-1] == A[-2])
print(ans)

Submission status: Runtime Error

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

    a.sort(reverse=True)
    cnt = 0
    for i in range(n):
        for j in range(i+1, n):
            if a[i]%a[j] == 0:
                cnt += 1
                break
    if a[-2]==a[-1]: cnt+=1

    return n - cnt
    



print(solve())

Submission status: Runtime Error

Solution code:
def _main(n, a_list):
    count = 0
    for i in range(n):
        i_value = a_list[i]
        fail = False
        for j in range(n):
            if i == j:
                continue
            j_value = a_list[j]
            result = i_value // j_value
            if j_value * result == i_value:
                fail = True
                break
        if not fail:
            count += 1

    print(count)


# if __name__ == "__main__":
n_a = int(input())
a_list_a = map(int, input().split())
_main(n_a, a_list_a)

Submission status: Runtime Error

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


a.sort()
count = 0
fac = []

for i in range(n):
    if i == 0:
        if a[i] != a[i+1]:
            count += 1
        fac.append(a[i])
    else:
        if all(a[i] % j != 0 for j in fac):
            count += 1
            fac.append(a[i]) 

print(count)

Submission status: Runtime Error

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

ret = 0

for i in range(N):
  if sum( [1 for j in range(N) if N[i] % N[j]] ) == 1:
    ret += 1

print( ret )

Submission status: Runtime Error

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

from collections import Counter
ca = Counter(a)

# 同じ数はまとめる
remain = []
ans=0
for i,cnt in ca.items():
    if cnt >1:
        ans+=cnt
    else:
        remain.append(i)

remain.sort(reverse=True)
print(ans)
for i in range(len(remain)):
    for j in range(i+1,n):
        if remain[i]%remain[j]==0:
            ans+=1
            break
print(n-ans)

Submission status: Runtime Error

Solution code:
n=int(input())
a=sorted([int(i) for i in input().split()])
if a[0]==a[1]:
    ans=0
else:
    ans=1
lis=[a[0]]


for i in range(1,n):
    ok=True
    for l in lis:
        if a[i]%l==0:
            ok=False
            break
    if ok:
        lis.append(a[i])
        ans+=1
print(ans)

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

cnt = 0
for i in A:
    p = make_divisors(i)[1:]
    l = 0
    for j in p:
        if j in A:
            break
        else:
            l += 1
    if (p[len(p)-1] in A[:A.index(i)]) or p[len(p)-1] in A[A.index(i)+1:]:
        continue
    elif l == len(p)-1:
        cnt += 1
print(cnt)

Submission status: Runtime Error

Solution code:
import sys
import  math
from heapq import *
import fractions
from collections import defaultdict
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))


N=int(input())
A=nl()
A.sort()
A_MAX=10**6+5
p_l=[0]*(A_MAX)
c=0

for i in range(len(A)):
    if(i==0):
        if(A[i]==A[i+1]):
            continue
    elif(i==(len(A)-1)):
        if(A[i]==A[i-1]):
            continue
    else:
        if(A[i]==A[i-1] or A[i]==A[i+1]):
            continue 
    if(p_l[A[i]]==0):
        c+=1
        for k in range(A[i]*2,A_MAX,A[i]):
            if(p_l[k]):
                continue
            p_l[k]=1

print(c)

Submission status: Runtime Error

Solution code:
def make_divisors(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

n = int(input())
A = sorted(tuple(map(int, input().split())))
if A[0] == 1:
    if A[1] == 1:
        print(0)
    else:
        print(1)
else:
    ans = []
    tyo = []
    for i in range(n):
        flag = True
        if A[i] in tyo:
            continue
        tmp = make_divisors(A[i])
        for x in tmp:
            if x in ans:
                flag = False
                break
        if not flag:
            continue


        if i<n-1:
            if A[i+1] == A[i]:
                tyo.append(A[i])
                continue
        ans.append(A[i])
print(len(ans))

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort()
ans=N
for i in range(N-1):
  if A[i]==A[i+1]:
    ans-=1
  else:  
    for k in range(0,i):
      if A[i]%A[k]==0:
        ans-=1
        break
for i in range(N-1):
  if A[N-1]%A[k]==0:
    ans-=1
    break
print(ans)

Submission status: Runtime Error

Solution code:
from math import ceil

X, N = [int(x) for x in input().split()]
l = [int(x) for x in input().split()]
l2 = [abs(int(x)-X) for x in l]
l2.sort()
for i in range(N):
    if ceil(i/2) != l2[i]:
        t = ceil(i/2)
        break
if X - t in l:
    print(X + t)
else:
    print(X - t)

Submission status: Runtime Error

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