Problem:


Score : 400 points

Problem Statement

Given is a number sequence A of length N.

Find the number of integers i \left(1 \leq i \leq N\right) with the following property:

For every integer j \left(1 \leq j \leq N\right) such that i \neq j , A_j does not divide A_i.

Constraints

All values in input are integers.

1 \leq N \leq 2 \times 10^5

1 \leq A_i \leq 10^6

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answer.

Sample Input 1

5
24 11 8 3 16

Sample Output 1

3

The integers with the property are 2, 3, and 4.

Sample Input 2

4
5 5 5 5

Sample Output 2

0

Note that there can be multiple equal numbers.

Sample Input 3

10
33 18 45 28 8 19 89 86 2 4

Sample Output 3

5



Sample input:
5
24 11 8 3 16


Sample output:
3

Submission status: Runtime Error

Solution code:
N = int(input())

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



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

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

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]))
    debug(f"Sorted: {A}")
    found = []
    c = 0
    i = 0
    while i < len(A):
        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:
                for f in found:
                    if A[i] % f == 0:
                        debug(f"{A[i]} was divided with {f}")
                        contained = True
                    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()
B=[]
for i in range(N-1):
    if A[i]==A[i+1]:
        B.append(A[i])
B=list(set(B))
for i in B:
    A = [x for x in A if x != i]
L=len(A)
for i in range(L):
    if i<len(A):
        for j in range(min(len(A)-1,i+1),len(A)-1):
            if A[j]%A[i]==0:
                A.remove(A[j])
print(len(A))

Submission status: Runtime Error

Solution code:
import sys

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

As = sorted(As)

# 例外処理
if len(set(As)) == 1:
  print(0)
  sys.exit()

cnt = [True]*n
for i in range(0, n):
  for j in range(i+1, n):
    if As[j]%As[i] == 0:
      cnt[j] = False
      del As[j]
    if As[j] == As[i]:
      cnt[i] = False

print(sum(cnt))

Submission status: Runtime Error

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import deque
import pprint

inf = 10**18
mod = 10**9+7

n = int(input())
a = list(map(int, input().split()))
a.sort()
b = []
pre = a[0]
if a[0] != a[1]:
    b.append(a[0])
    if pre == 1:
        print(1)
        sys.exit()
else:
    if pre == 1:
        print(0)
        sys.exit()

for num in a:
    if pre != num:
        b.append(num)
        pre = num

judge = [False for i in range(10**6+1)]
for num in b:
    judge[num] = True
for i in range(1,int(math.sqrt(10**6+1))):
    if judge[i] == True:
        for j in range(i*2,10**6+1,i):
            judge[j] = False
ans = 0
for i in range(1,10**6+1):
    if judge[i]:
        ans+=1
print(ans)

Submission status: Runtime Error

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

not_divisible = np.sum(np.sum(As[None]%As[:,None]==0, 0)==1)
print(not_divisible)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from collections import Counter
def main():
    N = int(input())
    A = list(map(int, input().split()))
    cnt = Counter(A)
    A.sort()
    ans = set()
    table = {i:-1 for i in range(1, 2 * 10 ** 5 + 1)}
    for a in A:
        table[a] = 0
    for a in A:
        if table[a] == 0 and cnt[a] == 1:
            ans.add(a)
        elif table[a] == 1:
            continue
        i = 2
        target = a
        while True:
            target = a * i
            if table[target] == 0:
                table[target] = 1
            i += 1
            if target >= A[-1]:
                break
    print(len(ans))
if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

a.sort()
if a[0] == 1:
    if a[1] != 1:
        print(1)
    else:
        print(0)
else:
    cnt = 1
    b = []
    for i in range(n-1):
        if a[i] != a[i+1]:
            b.append([a[i], cnt])
            cnt = 1
        else:
            cnt += 1
    b.append([a[n-1], cnt])

    ret = 0
    d_lst = []
    for c in b:
        num, cnt = c
        for d in d_lst:
            if num % d == 0:
                break
        else:
            if cnt == 1:
                ret += 1
            d_lst.append(num)

    print(ret)

Submission status: Runtime Error

Solution code:
#! env/bin/local python3

import sympy

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

a_divisors = {ac: set(sympy.divisors(ac)) for ac in a}
counter = 0
for key, value in a_divisors.items():
    a.remove(key)

    if len(set(a) & value) > 0:
        counter += 1
    a.append(key)

print(len(set(a)) - counter)

Submission status: Runtime Error

Solution code:
N = int(input())

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

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 i != N-1:
        if A[i] == A[i+1]:
            flag = False
    
    if flag == True:
        cnt += 1
print(cnt)

Submission status: Runtime Error

Solution code:
def main():

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

    d = dict()
    for v in A:
        d[v] = d.get(v, 0) + 1
    if 1 in d:
        if d[1] == 1: return 1
        else: return 0

    A = list(set(A))
    A.sort()
    s = set()
    ans = 0
    for i in range(N):
        if d[A[i]] == 1:
            if A[i] not in s:
                ans += 1
        k = 1
        while k * A[i] <= A[-1]:
            s.add(k * A[i])
            k += 1

    return ans




if __name__ == '__main__':
    print(main())

Submission status: Runtime Error

Solution code:
n=int(input())
l=list(map(int,input().split()))
count=n
l=sorted(l)
newl=[]
for i  in l:
    flag=True
    for j in newl:
        if i%j==0:
            flag=False
            count-=1
            break
    if flag==True:
        newl.append(i)
if l[0]==l[1]:
        count-=1
print(count)

Submission status: Runtime Error

Solution code:
# D 

from collections import deque
N=int(input())
A=list(map(int,input().split()))
A.sort()
B=deque(A)
#print(B)

cnt=0
tmp=[]
while B:
    i = B.popleft()
    for j in B:
        flag=True
        if j==i:
            flag=False
        elif j%i==0:
            pass
        else:
            tmp.append(j)
    else:
        if flag:
            cnt += 1
        #print(i,tmp,cnt)
        B=deque(tmp)
        tmp=[]
        continue

print(cnt)

Submission status: Runtime Error

Solution code:
N = int(input())
num_list = list(map(int, input().split()))
count=0
num_list = list(set(num_list))
if len(num_list) == 0:
  print(0)
  
else:
  for i in range(N):
    for j in range(N)
    if i != j:
      if num_list[i] % num_list[j]==0:
        count = count+1
        
  if count != 0:
    print(count/2)
  else:
    print(0)

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

print(cnt)

Submission status: Runtime Error

Solution code:
from collections import deque
n = int(input())
A = list(map(int,input().split()))
A.sort()
D = deque()
for a in A:
  if len(D) == 0:
    D.append(a)
  else:
    for d in D:
      if a == d:
        same == True
      elif a % d == 0:
        break
    else:
      D.append(a)
print(len(D))

Submission status: Runtime Error

Solution code:
import sympy as sp

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

a = sorted(a)
ads = [0]*(2*10**5)

ans = 0
dups = []
for ai in a:
    ds = sp.divisors(ai)
    ok = True
    if ads[ai]:
        if ai not in dups:
            dups.append(ai)
        continue
    for d in ds:
        if ads[d]:
            ok = False
            break
    if ok:
        ads[ai] = 1
        ans += 1

print(ans - len(dups))

Submission status: Runtime Error

Solution code:
import math
import bisect

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

a.sort()

count = 0
for i in reversed(range(0,n)):
    flag = 1
    temp = int(math.sqrt(a[i]))
    temp2 = bisect.bisect(a,temp)
    for j in range(0,temp2+1):
        if(a[i] % a[j] == 0 and i != j):
            flag = 0
            break
    if(flag == 1):
        count += 1

if(n >= 2):
    if(a[0] == a[1]):
        count -= 1

print(count)

Submission status: Runtime Error

Solution code:
import collections

N = int(input())
A = sorted([int(i) for i in input().split()])

limit = int(A[-1] ** 0.5)
ans = 0
while limit > A[0]:
    if len(A) == 1:
        ans += 1
    elif A[0] != A[1]:
        ans += 1
    A = [i for i in A if i % A[0] != 0]
    
a = collections.Counter(A)
print(ans + len([i[0] for i in a.items() if i[1] == 1]))

Submission status: Runtime Error

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

if n == 1:
    print(1)
    exit()

b = [True]*n
fix = [False]*n
for i in range(n):
    if not b[i] or fix[i]:
        continue
    if i < n and a[i] == a[i+1]:
        b[i] = False
        fix[i] = True
    for j in range(i+1, n):
        if a[i] < a[j] < a[i]*2:
            fix[j] = True
            continue
        if a[j] % a[i] == 0:
            fix[j] = True
            b[j] = False

print(sum(b))

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(range(2, 20001))

A = sorted(A, reverse= True)

posi = 0
Ja = A[0]
Kakutougi= [0]*N

for i in range (1, N):
	if A[i] == Ja:
		Kakutougi[i] = posi
	else:
		Kakutougi[i] = i
		Ja = A[i]
		posi = i

counter = N

for i in range (0, N):
	for j in range (Kakutougi[i]+1, N):
		if A[i]%A[j]==0:
			counter-=1
			break

print(counter)

Submission status: Runtime Error

Solution code:
import sympy


def calc():
    n, *a = map(int, open(0).read().split())
    black = set()
    r = set()
    for x in a:
        if x in r:
            black.add(x)
        r.add(x)

    r = set(a)
    count = 0
    for x in r:
        if r & black:
            continue
        if r & set(sympy.divisors(x)[:-1]):
            continue
        count += 1
    return count

print(calc())

Submission status: Runtime Error

Solution code:
import math

def removeCopies(l):
    i=0
    n=len(l)
    while i<n-1:
        if l[i]==l[i+1]:
            l.pop(i)
            i-=1
            n-=1
        i+=1

n=int(input())
l=list(map(int, input().split(' ')))

l=sorted(l)
removeCopies(l)
if len(l)==1:
    print(0)
else:
    index = 1
    ans=1
    while index<n:
        sindex=0
        tindex=index
        while sindex<tindex:
            if l[index]%l[sindex]==0:
                l.pop(index)
                index-=1
                n-=1
                break
            sindex+=1
        if sindex==tindex:
            ans+=1
        index+=1
    print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

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


    if 1 in a:
        if 1 in a[1:]:
            print(0)
        else:
            print(1)
    else:
        ans = 0

        odds = [i for i in a if i % 2 == 1]
        evens = [i for i in a if i % 2 == 0]
        if evens[0] == 2:
            evens = evens[:2]

        for a in [odds, evens]:
            for i in range(0, len(a)):
                if not a[i] in a[:i] + a[i + 1:]:
                    flag = 0
                    for j in range(0, i):
                        if a[i] % a[j] == 0:
                            flag = 1
                            break
                    if flag == 0:
                        ans += 1
        print(ans)

Submission status: Runtime Error

Solution code:
import sympy

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

exist = set()
dup = set()
for item in a:
    if item in exist:
        dup.add(item)
    else:
        exist.add(item)

ret = 0

for i in range(n):
    is_ok = True
    val = a[i]
    if val in dup:
        continue
    divs = sympy.divisors(val)
    for item in divs:
        if item == val:
            continue
        elif item in cand:
            is_ok = False
            break
    if is_ok:
        ret += 1

print(ret)

Submission status: Runtime Error

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

As = sorted(A)

dellist = []
# A[0]は最小なので同じ数字を除いてそれよりも大きい他の数では割り切れない。
i = 1
while(i < len(As)):
#     print('i:{}'.format(i))
#     print('As:{}'.format(As))
    # As[i]が、A[0]～A[i-1]で割り切れるか試す
    for j in range(i):
#         print('j:{}'.format(j))
#         print('As[i]:{}'.format(As[i]))
#         print('As[j]:{}'.format(As[j]))
        if As[i]%As[j]==0: # 割り切れちゃった場合
            # A[i]とA[j]が同じ数字なら、後でA[j]も消す必要があるので、
            # A[j]を削除リストに入れる
            if As[i] == As[j]:
                dellist.append(A[j])
            # A[i]を消す
            As.pop(i)
            # 消す前にA[i+1]だったものがA[i]になるので、iの値は変えずに
            # 新しいA[i]についてwhile中の最初から割り切れるかを検討する。
            # break後に1増えてしまうので、ここで減らしておく
            i-=1
            break
        
    # A[0]～A[i-1]で割り切れなかった場合：A[i]は残す。
    # iを一つ増やして、A[i+1]について考える
    i += 1

# remove は、指定した要素がlistに含まれていないとエラーを吐くみたいなので、
# 重複を排除する
dellist = list(set(dellist))
    
for i in dellist:
    As.remove(i)

# print(As)
print(len(As))
# print(dellist)

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
cnt1 = a.count(1)
if cnt1 > 1:
    print(0)
    sys.exit()
elif cnt1 == 1:
    print(1)
    sys.exit()
for i in range(n):
    d = make_divisors(a[i])
    # print(d)
    if i == 0 and a[i] == a[i + 1]:
        continue
    if i == n - 1 and a[i - 1] == a[i]:
        continue
    if i not in [0, n - 1] and (a[i - 1] == a[i] or a[i] == a[i + 1]):
        continue
    if len(d) == 2:
        cnt += 1
        continue
    d = d[:-1]
    for j in d:
        if a[bisect_left(a, j)] == j:
            break
    else:
        cnt += 1
print(cnt)

Submission status: Runtime Error

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import deque
import pprint

inf = 10**18
mod = 10**9+7

n = int(input())
a = list(map(int, input().split()))
a.sort()
b = []
pre = a[0]
if a[0] != a[1]:
    b.append(a[0])
    if pre == 1:
        print(1)
        sys.exit()
else:
    if pre == 1:
        print(0)
        sys.exit()

for num in a:
    if pre != num:
        b.append(num)
        pre = num

judge = [False for i in range(10**6+1)]
for num in b:
    judge[num] = True
for i in range(1,int(math.sqrt(10**6+1))):
    if judge[i] == 1:
        for j in range(i*2,10**6+1,i):
            judge[j] = False
ans = 0
for i in range(1,10**6+1):
    if judge[i]:
        ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
#from fractions import gcd
#from itertools import combinations # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n = I()
A = sorted(readInts())
dic = defaultdict(int)
cnt = 0
ANS = [0] * (10**6+1)
for i in A:
    dic[i] = min(dic[i]+1,2)
    ANS[i-1] = 1
if A[0] == 1:
    print(1)
    exit()
for i in range(n-1):
    if ANS[A[i]-1] == 0:
        continue
    else:
        if ANS[A[i]*2-1] == 0:
            continue
        else:
            for v in range(A[i]*2,10**6+1,A[i]):
                ANS[v-1] = 0
#print(dic)
for k,v in dic.items():
    if v >= 2:
        ANS[k-1] = 0
print(sum(ANS))

Submission status: Runtime Error

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

A.sort()

total = 0
for i in A:
    B =[]
    for n in range(1,len(A)):
        if A[n] % i !=0:
            B.append(A[n])
    if A[0] != A[1]:
        B.append(A[0])
    #print(B)
    A = B
    if len(A)==0:
        break
    Al = max(A)
    if A[0] == Al:
        break
    
if len(A)>0:
    print(len(A))
else:
    print(0)

Submission status: Runtime Error

Solution code:
import bisect
N=int(input())
A=list(map(int,input().split()))
A.sort()
ans=0
for i in range(N)[::-1]:
    flag=0
    a=A[i]
    b=a//2
    r=bisect.bisect_right(A,b)
    for j in range(r+1):
        if j==i:
            if a%A[j+1]==0:
                flag=1
        elif a%A[j]==0:
            flag=1
            break
    if flag==0:
        ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
num_list = list(map(int, input().split()))
count=0
num_list = list(set(num_list))
if len(num_list) == 0:
  print(0)
  
else:
  for i in range(N):
    for j in range(N)
    if i != j:
      if num_list[i]%num_list[j]==0:
        count = count+1
print(count)

Submission status: Runtime Error

Solution code:
import numpy as np

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


    if 1 in a:
        if 1 in a[1:]:
            print(0)
        else:
            print(1)
    else:
        ans = 0


        odds = [i for i in a if i % 2 == 1]
        evens = [i for i in a if i % 2 == 0]
        if evens[0] == 2:
            evens = evens[:2]

        for a in [odds, evens]:
            for i in range(0, len(a)):
                if not a[i] in a[:i] + a[i + 1:]:
                    flag = 0
                    for j in range(0, i):
                        if a[i] % a[j] == 0:
                            flag = 1
                            break
                    if flag == 0:
                        print(a[i])
                        ans += 1
        print()
        print(ans)

Submission status: Runtime Error

Solution code:

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

A.sort()
a_list = [A[0]]
ans = 0
if A[0] != A[1]:
    ans += 1
for i in range(1, N):
    if A[i] == A[i-1]:
        continue
    for a in a_list:
        if A[i] % a == 0:
            break
    else:
        a_list.append(A[i])
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
import sys
import copy

data = sys.stdin
data_list = data.readlines()
data_1 = data_list[0].strip("\n").split(" ")
data_2 = data_list[1].strip("\n").split(" ")

ans = 0

for i in range(int(data_1[0])):
  moto = int(data_2[i])
  new_list = data_2.copy()
  del new_list[i]
  for x in new_list:
    if moto % int(x) == 0:
      flag = 1
      break
    else:
      flag = 0
  if flag == 0:
    ans += 1
print(ans)

Submission status: Runtime Error

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

N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)
count=0
while len(A)>0:
    x=A.pop()
    if x==A[-1]:
        count-=1
    A=[i for i in A if i%x != 0]
    count+=1
print(count)

Submission status: Runtime Error

Solution code:
from collections import Counter


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

c = Counter(a)
new = []
for key, val in c.most_common():
    if val == 1:
        new.append(key)

ans = 0
for i in new:
    div = make_divisors(i)
    if len(set(new) & set(div)) == 1:
        ans += 1åç

print(ans)

Submission status: Runtime Error

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

if A.count(A[0])==N:
    print(0)
    exit(0)

flag = [0 for _ in range(N)]
for n in range(N):
    if flag[n] == 1: continue
    if A[n] == A[n+1] and n < N-1:
        flag[n] = 1
    for i in range(n+1,N):
        if flag[i] == 1: continue
        if A[i]%A[n] == 0:
            flag[i] = 1

print(N-sum(flag))

Submission status: Runtime Error

Solution code:
N = int(input())
num_list = list(map(int, input().split()))
count=0
num_list = set(num_list)
if len(num_list) == 0:
  print(0)
  
else:
  for i in range(N):
    for j in range(N)
    if i != j:
      if num_list[i]%num_list[j]==0:
        count = count+1
print(count)

Submission status: Runtime Error

Solution code:
def main():
    N  = int(input()) 
    A=list(map(int, input().split()))
    B = list(set(A))
    B.sort()
    lenb = len(B)
    Boo = [True]*lenb
    _,s = sieve((10**6)+7)

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

    for i in range(lenb):
        for j in range(i+1,lenb):
            if Boo[j] and s[B[j]] and B[j] % B[i] == 0:
                Boo[j] = False

    cnt = 0
    for i in range(lenb):
        if Boo[i] and A.count(B[i])==1:
            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:
from collections import Counter
N = int(input())
A = list(map(int, input().split()))

c = Counter(A)
A = [i[0] for i in c.items() if i[1] == 1]

A.sort()
ans = 0
i = 0
j = len(A)-1

while A:
  if A[j] % A[i] == 0:
    A.pop(j)
  j -= 1
  if j == i:
    ans += 1
    j = int(len(A)-1)
    i += 1
  if j == i:
    ans += 1
    break;

print(ans)

Submission status: Runtime Error

Solution code:
import sympy

n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
count = 0

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

print(n-count)

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
As = set((map(int, input().split())))
N = len(As)
As = np.asarray(list(As))

Bs = [True]*N

for index, i in enumerate(As):
    Cs = As%i != 0
    Cs[index] = True
    Bs = np.logical_and(Cs, Bs)
print(Bs)
print(list(Bs).count(True))

Submission status: Runtime Error

Solution code:

n = int(input())
li = list(map(int, input().split()))
li.sort()
inf = 2*(10**5)+1
isprime = [False]*(inf)
for i in li:
    isprime[i] = [True]
for i in range(len(li)):
    if i+1<len(li):
      if li[i] == li[i+1]:
        isprime[li[i]] = False
for i in li:
    if not isprime[i]:
        continue
    for k in range(i+i, inf, i):
        isprime[k] = False
prime_list = []
for i in range(inf):
    if isprime[i]:
        prime_list.append(i)
print(len(prime_list))