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()
    n = max(A)
    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:
        print(q)
        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()

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)

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

    if cnt==n-i-1:
        ans+=1
if a[-1]==a[-2]:
    ans-=1
print(ans)

Submission status: Runtime Error

Solution code:
A=input().split();
A=[int(s) for s in A];
ans_list=[];
flag=True;
for i in range(N):
  for j in range(N):
    if i==j:
      continue;
    if A[i]%A[j]==0:
      flag=False;
      break;
  if (not A[i] in ans_list) and flag==True:
    ans_list.append(A[i]);
  flag=True;
print(len(ans_list))

Submission status: Runtime Error

Solution code:
N = int(input())
A = sorted(map(int,input().split()))
numbers = [0]*(max(A)+1)
import sympy
answer = 0
for i in range(N):
    yakusu = sympy.divisors(A[i])
    judge = 1
    for j in range(1,len(yakusu)-1):
        if numbers[yakusu[j]] != 1:
            judge = 0
    if judge == 1:
        answer += 1
    numbers[A[i]]=1
    if A[i]==A[i-1]:
        answer -= 1
    
print(answer)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
import math

sys.setrecursionlimit(10 ** 6)

# Made for abc097D
class UnionFind:
    def __init__(self, size):
        self.size = size
        self.parents = [i for i in range(size)]
        self.ranks = [0 for i in range(size)]

    def ancestor(self, i):
        if self.parents[i] == i:
            return i
        else:
            self.parents[i] = self.ancestor(self.parents[i])
            return self.parents[i]

    def union(self, i, j):
        ip = self.ancestor(i)
        jp = self.ancestor(j)
        if ip == jp:
            return False
        else:
            if self.ranks[ip] > self.ranks[jp]:
                self.parents[jp] = ip
            else:
                self.parents[ip] = jp
                if self.ranks[ip] == self.ranks[jp]:
                    self.ranks[ip] += 1

    def same(self, i, j):
        return self.ancestor(i) == self.ancestor(j)

    def __str__(self):
        parentDict = { }
        for i in range(self.size):
            a = self.ancestor(i)
            if a not in parentDict:
                parentDict[a] = [i]
            else:
                parentDict[a].append(i)
        result = "===UnionFind description===\nSize:" + str(self.size) + "\nGroupCount:" + str(
            len(parentDict)) + "\n\nGroups:\n"
        for k in parentDict.keys():
            elements = ""
            for elem in parentDict[k]:
                elements += " " + str(elem) + ","
            result += "Group-"+str(k)+"(Count:"+str(len(parentDict[k]))+"):["+elements+"]\n"
        return result

def debug(s):
    if False:
        print(s)

def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

def solve(N: int, A: "List[int]"):
    A = sorted(A)
    pst = set(get_sieve_of_eratosthenes(A[-1])) if len(A) > 0 else set()
    # debug(f"Sorted: {A}")
    # debug(f"pst {pst}")
    found = []
    c = 0
    i = 0
    while i < len(A):
        # debug(f"step: A{A[i]}. found:{found}")
        if i < len(A)-1 and A[i] == A[i+1]:
            found.append(A[i])
            ni = i+1
            while A[ni] == A[i]:
                if len(A)-1 == ni:
                    ni = len(A)
                    break
                ni += 1
            # debug(f"i was skipped from {i} to {ni}")
            i = ni
            continue
        else:
            contained = False
            if A[i] not in pst:
                # debug(f"{A[i]} is not a prime")
                for f in found:
                    # debug(f"Dividing {A[i]} with {f}. == {A[i]%f}")
                    if A[i] % f == 0:
                        # debug(f"{A[i]} was divided with {f}")
                        contained = True
                        break
                    if A[i]**2 < f:
                        break
            if not contained:
                # debug(f"{A[i]} is not contained appending")
                c+=1
                found.append(A[i])
            i+=1
    print(c)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort(reverse = True)
p = 0
 
for i in range(n):
    j = i + 1 
        while j < n:
            if i == j:
                pass
            elif a[i] % a[j] == 0:
                break
            else:
                pass
            if j == n - 1:
                p += 1
	    j += 1
 
print(p)

Submission status: Runtime Error

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

ans = 0
if N == 1:
    print(ans)
else:
    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
        if np.all(a_g:, i):
            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)
count = np.sum(x_list%x_list.reshape(N,1)==0, axis=0)==1
print(np.sum(count))

Submission status: Runtime Error

Solution code:
n = int(input())
a = sorted(list(map(int, input().split(" "))))
idx = 0
while True:
    removes = []
    v = a[idx]
    for target in a[idx:]:
        if target % v == 0:
            removes.append(target)
    removes.remove(v)
    if removes:
        if removes[0] == v:
            removes.append(v)
        for target in removes:
            a.remove(target)
    if len(a) == 0 or a[-1] == v:
        break
    idx += 1
print(len(a))

Submission status: Runtime Error

Solution code:
def factor(N):
    arr=[]
    for i in range(1,int(N**0.5)+1):
        if(N%i==0):
            arr.append(i)
            if(N//i!=i):
                arr.append(N//i)
    return arr

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

cnt=[0]*1000001
for i in range(N):
    cnt[A[i]]+=1
ng=set()
for i in range(N):
    if cnt[A[i]]>1:
        ng.add(A[i])

s=set(A)

ans=0
for i in reversed(range(N)):
    if A[i] in ng:
        continue
    if A[i]<min_*2:
        ans+=1
        continue
    s.remove(A[i])
    arr=factor(A[i])
    ok=True
    for x in arr:
        if x in s:
            ok=False
            break
    if ok:
        ans+=1
    s.add(A[i])
print(ans)

Submission status: Runtime Error

Solution code:
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 = [i for i in a if i<=num*(1/2)]
            for cand in cands:
                if num % cand == 0:
                    break
            else:
                ans+=1
    print(ans)

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    A = [int(i) for i in input().split()]
    from collections import Counter
    from math import gcd
    c = Counter(A)
    bl = set()
    for k, v in c.items():
        if v >= 2:
            L *= k
            bl.add(k)
    if c[1] == 1:
        return print(1)
    elif c[1] > 1:
        return print(0)
    A.sort()

    ans = 0
    L = 1
    for a in A:
        if a in bl:
            continue
        v = gcd(L, a)
        if v not in A:
            ans += 1
        L *= a
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

i = 0
while i < n:
    j = 0
    while j < n:
        if i != j and a[i] % a[j] == 0:
            result[i][j] = 1
            break
        j += 1
    i += 1
print(n-np.count_nonzero(np.sum(result, axis=1)))

Submission status: Runtime Error

Solution code:
n = int(input())
A = list(map(int, input().split()))
from collections import Counter
c = Counter(A)
sorted_key = sorted(c.keys(),reverse=True)
res = [0]*len(sorted_key)
ans = n
#print(sorted_key)
#for i,key in enumerate(sorted_key):
for key in sorted_key:
    if c[key]>1:
        ans -= c[key]
        continue
    for j in range(len(sorted_key)-1, i, -1):
        #print(i,key,j,sorted_key[j])
        if (key/sorted_key[j]>=1) and (key%sorted_key[j])==0:
            #res[i] = 1
            ans -= c[key]
            #print('===========',)
            break

#print('res', res)
#print(c)
'''ans = 0
for i,v in enumerate(sorted_key):
    if res[i]:
        ans += c[sorted_key[i]]
    else:
        if c[v] >1:
            ans += c[sorted_key[i]]'''
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()))
b = set()
if len(set(a)) == 1:
    print(0)
    exit()
a.sort()
cnt = 0

for i in a:
    flg = True
    l = set(make_divisors(i))
    print(l, b, l & b)
    if len(l & b) == 0:
        cnt += 1
    b.add(i)
print(cnt)

Submission status: Runtime Error

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

S = sorted(A)

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:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys
input = sys.stdin.readline
ipnl = lambda n: [int(input()) for _ in range(n)]
inp = lambda :int(input())
ip = lambda :[int(w) for w in input().split()]

n = inp()
x = ip()
if len(set(x)) == 1:
    print(0)
else:
    dt = {} 
    for i in x: dt[i] = dt.get(i,0)+1
    x = [i for i in dt if dt[i] == 1]
    if x == []:
        print(0)
    else:
        x.sort(reverse= True)
        ct = 1
        for i in reversed(range(n-1)):
            flag = 1
            for j in range(i+1,n):
                if x[i]%x[j] == 0:
                    flag = 0
                    break
            if flag:
                ct += 1
        print(ct)

Submission status: Runtime Error

Solution code:
import math
n, *a = map(int, open(0).read().split())
a.sort()
cnt = n
if a[1] == a[0]:
    cnt -= 1
    
def make_divisors(n,th):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n and i <= th:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    print(i)
    return lower_divisors + upper_divisors[::-1]
    
for i in range(n):
    divisors = make_divisors(a[i], a[i]//2 + 1) 
    
    for div in divisors:
        if div in a[:i]:
            cnt -= 1
            break

print(max(cnt,0))

Submission status: Runtime Error

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


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

    MOD = 10 ** 9 + 7
    A.sort()
    s = set()

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

    for i in range(1, n):
        if A[i - 1] == A[i]:
            continue

        for j in range(i):
            if A[j] in s:
                continue
            elif A[i] % A[j] == 0:
                s.add(i)
                break
        else:
            ans += 1
            # print(f"{i = }, {j = }, {ans = }")

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

def mergesort(a):
    def _merge_sort(a, left: int, right: int):
        if left < right:
            center = (left+right)//2

            _merge_sort(a,left,center)
            _merge_sort(a,center+1,right)

            #pは前半部をbuffにコピーする際のインデックス、jで取り出す
            p=j=0
            i=k=left

            #配列の前半部をbuffにコピー
            while i <= center:
                buff[p]=a[i]
                p+=1
                i+=1

            #後半部をコピーされた前半部と比較、小さい方をaに格納していく
            while i<= right and j < p:
                if buff[j] <= a[i]:
                    a[k]=buff[j]
                    j+=1
                else:
                    a[k]=a[i]
                    i+=1
                k+=1

            while j < p:
                a[k] =buff[j]
                k+=1
                j+=1

    n=len(a)
    #merge結果を一時的に格納
    buff=[None]*n
    _merge_sort(a,0,n-1)
    del buff

mergesort(a)

if a[0]==1:
    if a[1]==1:
        print(0)
        sys.exit()
    else:
        print(1)
        sys.exit()

if a[0]==a[1]:
    count=0
else:
    count=1

for i in range(n-1):
    if (i+1)!=n-1 and a[i+2]==a[i+1]:
        continue
    if a[i+1]==a[i]:
        continue
    for l in range(i+1):
        if a[i+1]%a[l]==0:
            break
        if i==l:
            count+=1

print(count)

Submission status: Runtime Error

Solution code:
import sys

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

i = 1
while i < len(a):
  fl = True
  for j in range(i):
    if a[i]%a[j] == 0:
      a.pop(i)
      fl = False
      break
  if fl:
    #print(a[i])
    cnt += 1
    i += 1

print(cnt)

Submission status: Runtime Error

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

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

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

print(ans+1)

Submission status: Runtime Error

Solution code:
import math

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True
  
n = int(input())
an = list(map(int, input().split()))
an = sorted(an)

count = 0
for i, ai in enumerate(an):
    if is_prime(ai) and an.count(ai) == 1:
        count+=1
    elif an.count(ai) == 1:
        ai_2 = (ai + 1) // 2
        for aj in an[:i]:
            if ai % aj == 0:
                break
            if aj > ai_r:
                count+=1
                break
        else:
            count+=1
print(count)

Submission status: Runtime Error

Solution code:
def primes(n):
    is_prime = [i % 2 != 0 and i % 3 != 0 and i % 5 != 0 and i % 7 != 0 for i in range(n + 1)]
    is_prime[1] = False
    is_prime[2] = is_prime[3] = is_prime[5] = is_prime[7] = True
    for p in range(3, int(n**0.5) + 1, 2):
        if not is_prime[p]:
            continue
        for i in range(p**2, n + 1, p):
            is_prime[i] = False
    return {i for i, p in enumerate(is_prime) if p}


def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    a.sort()
    if a[0] == 1:
        print(n - 1 + (a[1] == 1))
        return
    p = primes(10**6)
    b = set()
    c = 0
    for i in range(n):
        if i < n - 1 and a[i] == a[i + 1] or i > 0 and a[i] == a[i - 1]:
            b.add(a[i])
            continue
        if a[i] in p:
            c += 1
            b.add(a[i])
            continue
        for j in range(1, int(a[i]**0.5) + 1):
            if a[i] % j:
                continue
            if j in b or a[i] // j in b:
                break
        else:
            c += 1
            b.add(a[i])
    print(c)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from collections import deque

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

A = deque(sorted(A, reverse=True))


count = 0

if A[-1] == A[-2]:
    count -= 1

jud = True

for i in range(len(A)):
    c = int(A.popleft())
    for j in range(len(A)):
        if c % A[j] == 0:
            jud = False
            break
    if jud:
        count += 1

    jud = True

print(count)

Submission status: Runtime Error

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

A_div = [0 for _ in range(N)]
if len(A) == 1:
    print(0)
else:
    for i in range(N):
        if A_div[i] == 0:
            for j in range(i + 1, N):
                if A[i] % A[j] == 0:
                    A_div[i] += 1
                if A[j] % A[i] == 0:
                    A_div[j] += 1

    print(A_div.count(0))

Submission status: Runtime Error

Solution code:
import numpy as np
from numba import njit

@njit
def main(n, a):
  ans = 0
  divs = np.array([[0 for _ in range(n)] for _ in range(n)])
  for i in range(n):
    for j in range(i+1, n):
      if np.mod(a[i],a[j]) != 0:
        divs[i][j] = 1
      if np.mod(a[j], a[i]) != 0:
        divs[j][i] = 1
  
    if np.sum(divs[i,:]) == n-1:
      ans += 1
  
  print(ans)

if __name__ == "__main__":
  n = int(input())
  a = np.array(list(map(int, input().split())))
  main(n, a)

Submission status: Runtime Error

Solution code:
#!python3.8
# -*- coding: utf-8 -*-
# abc170/abc170_d
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N = i2n()
    A = sorted(int(c) for c in i2s().split(' '))
    max_ = A[-1]
    B = {}
    if N == 1:
        print(1)
        return
    if A[0] == A[1]:
        B[A[i]] = 2
    else:
        B[A[i]] = 1
    for i in range(1, N - 1):
        if A[i-1] == A[i] or A[i+1] == A[i]:
            B[A[i]] = 2
        else:
            B[A[i]] = 1
    if A[-2] == A[-1]:
        B[A[i]] = 2
    else:
        B[A[i]] = 1
    for b in B:
        if B[b] == 0:
            continue
        if B[b] == 2:
            B[b] = 0
        for i in range(2, max_ // b + 1):
            if b * i in B:
                B[b * i] = 0
    res = 0
    for v in B.values():
        if v:
            res += 1
    print(res)
    return

main()

Submission status: Runtime Error

Solution code:
import collections
n = int(input())
counter = collections.Counter()

for i in input().split():
    x = int(i)
    counter[x] += 1

a_list = sorted([i for i, v in counter.items() if v == 1])

def func(x, nums, count):
    if len(nums) == 0:
        return count
    else:
        new_nums = [i for i in nums if i % x != 0]
        count += 1
        return func(new_nums[0], new_nums[1:], count)

if len(a_list) == 0:
    count = 0
else:
    count = func(a_list[0], a_list[1:], 1)

print(count)

Submission status: Runtime Error

Solution code:
import math as mt
#import numpy as np
def ro(n):
  return mt.floor(mt.sqrt(n))
def ya():
  print("Yes")
  return
def na():
  print("No")
  return

#x,n=map(int,input().split())
n=int(input())
lis=list(map(int,input().split()))
#s=input()
lis.sort()
f=1
i=0
y=len(lis)
while i<y:
  try:
    x=lis[i]
  except:
    break
  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
  y=len(lis)

print(len(lis))

Submission status: Runtime Error

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

if a[0] == a[1]:
    cnt -= 1

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

Submission status: Runtime Error

Solution code:
import collections

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

def is_prime(n):
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return n != 1


def main():
    not_prime_list = []
    prime_list = []

    for v in sorted(a_list):
        if is_prime(v):
            prime_list.append(v)
        else:
            not_prime_list.append(v)

    # 素数の個数判定をする
    duplicated_counter = collections.Counter(prime_list)
    n_prime_duplicates = 0
    for k, v in duplicated_counter.most_common():
        if v == 1:
            break
        n_prime_duplicates += v

    # 全部素数ならこの時点でわかる
    if not not_prime_list:
        print(len(a_list) - n_prime_duplicates)
        return
    
    # この時点で、1個しかない素数は確定しているので、素数じゃないやつを探す
    candidate_list = []
    for v in not_prime_list:
        flag =0
        for p in prime_list:
            # 素数側がでかくなったらもうおわり
            if v < p:
                break
            if v % p == 0:
                # 割り切れたらこいつはだめ
                flag = 1
                break
        if flag == 0:
            candidate_list.append(v)
    if not candidate_list:
        print(len(prime_list) - n_prime_duplicates)
        return
    
    duplicated_counter = collections.Counter(candidate_list)
    n_duplicates = 0
    for k, v in duplicated_counter.most_common():
        if v == 1:
            break
        n_duplicates += 1
            
    not_prime_count = 0

    def find_ans(c, target_list, counter):
        next_target = []
        counter += 1
        for v in target_list:
            if v % c != 0:
                next_target.append(v)
        if not next_target:
            return counter
        else:
            ans = find_ans(next_target[0], next_target[1:], counter)
        return ans

    not_prime_count = find_ans(candidate_list[0], candidate_list[1:], 0)
    ans = len(prime_list) - n_prime_duplicates +  not_prime_count  - n_duplicates
    print(ans)

    
main()

Submission status: Runtime Error

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

if N==1:
	print(1)

else:
	a_ls.sort()
	ans=0
	ties=[]
	while len(a_ls)>0:
		A=[]
		for val in a_ls:
			A+=[val]
		target=a_ls[0]
		for val in a_ls:
			if val%target==0:
				A.remove(val)
			
		
		if len(a_ls)>1:
			if a_ls[1]!=a_ls[0]:
				ans+=1
		
		if len(a_ls)==1:
			ans+=1
		
		a_ls=A


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
start=time.time()
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
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:
        if ans:
            if i in ans:
                ans.remove(i)
        continue
    for j in make_divisors(i):
        if b[j]==1:
            f=False
            break
    if f:
        b[i]=1
        ans.append(i)

print(len(ans))

Submission status: Runtime Error

Solution code:
import math
n = int(input())
a = sorted(list(map(int,input().split())))
if 1 < len(a):
    c = 1 if a[0] == a[1] else 0
else:
    c = 0
for i in range(1, n):
    x = a[i]
    for j in range(math.ceil(i/2)):
        if x % a[j] == 0 or x % [i-j] == 0:
            break
    else:
        continue
    c+=1
print(n-c)