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 math
N = int(input())
A = list(map(int, input().split()))

As = sorted(A)

dellist = []
# A[0]は最小なので同じ数字を除いてそれよりも大きい他の数では割り切れない。
i = 0
MAX = int(math.sqrt(As[N-1]))+2
while(i < len(As) or As[i] < MAX):
#     print('i:{}'.format(i))
#     print('As:{}'.format(As))
    # As[i]で、A[i+1]～A[len(As)]で割り切れるものを探し、消す。
    j = i+1
    poplist = []
    while(j < len(As)):
#         print('j:{}'.format(j))
#         print('As[i]:{}'.format(As[i]))
#         print('As[j]:{}'.format(As[j]))
        if As[j]%As[i] == 0: # 割り切れちゃった場合
            # A[j]をあとで消すために控える
            poplist.append(j)
            # A[i]とA[j]が同じ数字なら、最後にA[i]も消す必要があるので、
            # A[i]を削除リストに入れる
            if As[i]  == As[j]:
                dellist.append(A[i])
                
        j += 1
        
    # poplistにあるAs[]を消す
    # 前から消していくと順番が狂うので、後ろから消す。参考↓
    # https://gammasoft.jp/blog/remove-multiple-elements-from-python-list/
    for k in sorted(poplist, reverse=True):
        As.pop(k)
    # As[i]で割り切れるものは探しきって、次のAs[i+1]は割り切れないもの。
    # 次はAs[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:
n=int(input())
a=list(map(int, input().split()))

l = sorted(a)
tmp = l
ans = []
ans.append(tmp[0])

#print(l)

for i in range(n):
    tmp = [s for s in tmp if s % ans[0] != 0]
    #print(tmp)
    if tmp != []:
        if tmp[0] not in ans:
            ans.insert(0,tmp[0])

if len(ans) == 1 and l[0] == l[1]:
    print(0)
else:
    print(len(ans))

Submission status: Runtime Error

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

import sys


def input():
    return sys.stdin.readline()

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]

def resolve():
    n = int(input().rstrip())
    a_list = list(map(int, input().split()))

    a_list.sort()

    cnt = 0

    for i in range(len(a_list)):
        num = a_list[i]
        prime_list = []
        # 最小の値は割れない
        if i == 0:
            num2 = a_list[i+1]
            if num != num2:
                cnt += 1
            continue
        if i+1 < n and num == a_list[i+1]:
            continue

        if i == n-1 and cnt ==0:
            continue

        prime_list = make_divisors(num)

        prime_list.pop()

        del prime_list[0]

        if len(prime_list) == 0:
            cnt += 1
            continue

        div_flag = False
        for pr in prime_list:
            if pr in a_list:
                div_flag = True
                break

        if not div_flag:
            cnt += 1

        """
        div_flag = False
        for j, num2 in enumerate(a_list):
            #print(num, num2)
            if i == j:
                break
            if num % num2 == 0:
                div_flag = True
                break

        if not div_flag:
            cnt += 1
        """
    print(cnt)


if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        if 2 in S:
            return 0
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            if 2 in S:
                return 0
            n //= f
        else:
            f += 2
	if n in S:
		return(0)
    return 1
  
N = int(input())
key = 0
S = map(int,input().split())
for i in N:
	key +=  prime_factorize(S[i])
print(key)

Submission status: Runtime Error

Solution code:
from collections import Counter
n = int(input())
A = sorted(map(int, input().split()))

c = Counter(A)

yes_or_no = [1 for i in range(A[n-1])]

for a in A:
  t = a*2
  while t <= A[n-1]:
    yes_or_no[t] = 0
    t += a
ans = 0
for a in A:
  if c[a] == 1 and yes_or_no[a] == 1:
    ans += 1
print(ans)

Submission status: Runtime Error

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

i = 0
while True:
    if i>len(num_list):
        break
    for j in range(i+1, len(num_list)):
        print(i, j, num_list[i], num_list[j], len(num_list))
        if num_list[i] % num_list[j] == 0:
            del num_list[i]
            break
    if j+1 == len(num_list):
        i += 1
print(len(num_list))

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
vec = np.array([int(i) for i in input().split()])
counter = 0
matrix = np.zeros((N, N))
for i in range(N):
    matrix[i] = vec%vec[i]
for j in range(N):
    if list(matrix.T[j]).count(0) == 1:
        counter += 1
print(counter)

Submission status: Runtime Error

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

import sys


def input():
    return sys.stdin.readline()

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]

def resolve():
    n = int(input().rstrip())
    a_list = list(map(int, input().split()))

    a_list.sort()
    print(a_list)

    cnt = 0

    for i in range(len(a_list)):
        num = a_list[i]
        prime_list = []
        # 最小の値は割れない
        if i == 0:
            num2 = a_list[i+1]
            if num != num2:
                cnt += 1
            continue
        if i+1 < n and num == a_list[i+1]:
            continue

        if i == n-1 and cnt ==0:
            continue

        prime_list = make_divisors(num)

        prime_list.pop()

        del prime_list[0]

        if len(prime_list) == 0:
            cnt += 1
            continue
        
        div_flag = False
        for pr in prime_list:
            if pr in a_list:
                div_flag = True
                break

        if not div_flag:
            cnt += 1

        """
        div_flag = False
        for j, num2 in enumerate(a_list):
            #print(num, num2)
            if i == j:
                break
            if num % num2 == 0:
                div_flag = True
                break

        if not div_flag:
            cnt += 1
        """
    print(cnt)


if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
def make_divisors(n):
    if n == 1:
        return [1]
    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 = list(map(int, input().split()))
X = [0] * (2 * 10**5 + 1)
for a in A:
    X[a] += 1
ans = 0
for a in A:
    if X[a] > 1:
        continue
    for d in make_divisors(a)[:-1]:
        if X[d]:
            break
    else:
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
import bisect

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

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

for i in range(N - 1,-1,-1):
  sup = A[i] // 2 
  ind = bisect.bisect(A,sup)
  ind = max(ind,1)
  #print(ind)
  for j in range(0,ind):
    if A[i] % A[j] == 0:
      ans -= 1
      break

print(ans)

Submission status: Runtime Error

Solution code:
def main1():
    N=int(input())
    A=list(map(int,input().split()))
    A.sort()
    ans=[0]*(10**6)
    for i in  range(len(A)-1):
        if ans[A[i]]>=2:
            continue
        if A[i]!=A[i+1]:
            ans[i]+=1
        for j in range(A[i]*2,10**6,A[i]):
                ans[j]=2
    print(ans.count(1))
main1()

Submission status: Runtime Error

Solution code:
# from numba import njit
import timeit
import numpy as np
n = int(input())
an = np.array([int(a) for a in input().split()], dtype=np.int64)
dd = np.reshape(an, (n, 1))
res = 0

grid = np.tile(an, (n, 1))
div = np.remainder(grid, dd)
div = np.count_nonzero(div, axis=0)
res = div[div == (n-1)].size


#@njit
#def loop(n, an, validate, res, an_slice_size):
#    res = 0
#    for i in range(n):
#        validate[:] = True
#        validate[i] = False
#        an_slice = an[validate]
#        diveded = an[i] % an_slice
#        if diveded[diveded != 0].size == an_slice_size:
#            res+=1
#print(timeit.timeit("loop(n, an, validate, res, an_slice_size)", globals=globals()))

print(res)

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 = list(map(int, input().split()))
X = [0] * (2 * 10**5 + 1)
for a in A:
    X[a] += 1
ans = 0
for a in A:
    if X[a] > 1:
        continue
    for d in make_divisors(a)[:-1]:
        if X[d]:
            break
    else:
        ans += 1

print(ans)

Submission status: Runtime Error

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

a = sorted(a)
a.append(0)

ans = 0
tmp = 0
for i in range(len(a)):
    if a[i] == 1:continue
    tmp = a[i]
    if a[i] != a[i+1]:
        ans += 1
    for j in range(len(a)):
        if a[j] % tmp == 0:
            a[j] = 1
        if all(x == 1 for x in a):
            print(ans)
            exit()

Submission status: Runtime Error

Solution code:
from collections import Counter
import math

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

dic = Counter(a)

ans = 0

memo = {}

def seachPrimeNum(N):
    max = int(np.sqrt(N))
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum

primeNum = set(seachPrimeNum(10**6))

for ai in a:
    cnt = 0
    f = 1
    if ai not in memo:
        if ai not in primeNum:
            for i in range(1, int(math.sqrt(ai))+1):
                if ai % i == 0:
                    d = i
                    if d in dic:
                        cnt += dic[d]
                    if d == ai:
                        cnt -= 1
                    if cnt > 0:
                        f = 0
                        break
                    if i != ai // i:
                        d = ai // i
                        if d in dic:
                            cnt += dic[d]
                        if d == ai:
                            cnt -= 1
                        if cnt > 0:
                            f = 0
                            break
    else:
        f = memo[ai]
    ans += f
    memo[ai] = f

print(ans)

Submission status: Runtime Error

Solution code:
def main1():
    N=int(input())
    A=map(int,input().split())
    A.sort()
    ans=[0]*(10**6)
    for i in  range(len(A)-1):
        if ans[i]>=2:
            continue
        if A[i]!=A[i+1]:
            ans[i]+=1
        for j in range(A[i]*2,10**6,A[i]):
                ans[j]=2
    print(ans.count(1))
main1()

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
#n=2*10**5
#a=[i+2 for i in range(0,n)]
a.sort()
aa={}
for i in range(0,a[-1]):
  aa[i]=0
if a[0]==a[n-1]:
  print(0)
elif a[0]==1:
  print(1)
else:
  ans=0
  while len(a)!=1:
    now=a.pop(0)
    if aa[now]==0:
      ans+=1
      new=0+now
      while a[-1]>=now:
        aa[now]=1
        now+=new
  if aa[a[0]]==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 = A.sort() # 一応

count = 0
while A ~= []:
    new = []
    b = A[0]
    for a in A[1:]:
        if a % b > 0: # bで割れなければ続投
            new.append(a)
    A = new
    count += 1


print(count)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import numpy as np

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

sosu = []
count = 0

def loop(target, A):
  global count
  B = []
  flg = True
  for i in range(len(A)):
    if A[i] % target != 0:
      B.append(A[i])
    if target % A[i] == 0:
      flg = False
  if flg:
    count+=1
  if len(B) == 1:
    count+=1
    return
  if len(B) == 0:
    return
  target = B.pop(0)
  loop(target, B)

target = A.pop(0)
loop(target, A)
print(count)

Submission status: Runtime Error

Solution code:
n = int(input())

a = list(map(int, input().split()))
a.sort()
valid = valid = [1] * n
ret = 0
tgt = 0

#print(a)

while True:
	num = a[tgt]
	valid[tgt] = 0
#	print("tgt",tgt,num)

	for i in range((tgt+1),n):
#		print(a[i],num,a[i]%num)
		if(a[i]%num == 0):
			valid[i] = 0
	
	ret += 1
	
	for i in range((tgt+1),n):
		if(valid[i] == 1):
			tgt = i
			break


	if(i==n-1):
		if(tgt == n-1):
			ret+=1
		break

if(ret==1):
	print(0)
else:
	print(ret)

Submission status: Runtime Error

Solution code:
import numpy as np

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

sosu = []
count = 0

def loop(target, A):
  global count
  B = []
  flg = True
  for i in range(len(A)):
    if A[i] % target != 0:
      B.append(A[i])
    if target == A[i]:
      flg = False
  if flg:
    count+=1
  if len(B) == 1:
    count+=1
    return
  if len(B) == 0:
    return
  target = B.pop(0)
  loop(target, B)

target = A.pop(0)
loop(target, A)
print(count)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
a.sort()
count = 0

li = [0]*(10**6)
for i in a:
    if li[i]>0:
        count += 1
        print(i)
    k = i    
    while k < 10**6:
        li[k]+=1
        k+=i
print(n-count)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
c = Counter(A)
lst = [1] * (10**6+1)
res = 0

for i,a in enumerate(A):
  if lst[a] == 0: continue
  if i==N-1 or A[i+1] != a:
    res += 1
  for j in range(a, 10**6+1, a):
    lst[j] = 0

print(res)

Submission status: Runtime Error

Solution code:
import numpy as np
n = int(input())
a = list(map(int, input().split()))
a.sort()
for i in range(n-1):
    de = []
    for j in range(i+1,n):
        if a[j]%a[i]==0:
            de.append(j)
        if j<=n-1:
            if j==n-1 and a[j] == a[j-1]:
                de.append(j)
            elif a[j]==a[j-1] and (a[j]!=a[j+1]):
                de.append(j)
    de = np.array(de)
    for j in range(len(de)):
        a.pop(de[j])
        de-=1
        n-=1
print(n)

Submission status: Runtime Error

Solution code:
def main(N, a):
    a.sort()
    if a[0] == 1:
        if a[1] == 1:
            return 0
        return 1
    i = 0
    while True:
        num = a[0]
        if 2 > len(a):
            return len(a)+i
        while True:
            if num == a[1]:
                a = [i for i in a if i != num]
                if 2 > len(a):
                    return len(a)+i
                num = a[0]
            else:
                break
        if num*2 > a[len(a)-1]:
            a = [i for i in a if i % num != 0]
            return len(a)+i+1
        a = [i for i in a if i % num != 0]
        i = i+1


N = int(input())
a = list(map(int, input().split()))
print(main(N, a))

Submission status: Runtime Error

Solution code:

import glob
import os
import bisect

bn = os.path.basename(__file__).split('.')[0]
dn = os.path.dirname(__file__).split('/')

# 問題ごとのディレクトリのトップからの相対パス
REL_PATH = dn[len(dn)-2] + '\\' + dn[len(dn)-1] + '\\' + bn

# テスト用ファイル置き場のトップ
TOP_PATH = 'C:\\AtCoder'

class Common:

    problem = []
    index = 0

    def __init__(self, rel_path):
        self.rel_path = rel_path

    def initialize(self, path):
        file = open(path)
        self.problem = file.readlines()
        self.index = 0
        return

    def input_data(self):
        try:
            IS_TEST
            self.index += 1
            return self.problem[self.index-1]

        except NameError:
            return input()

    def resolve(self):
        pass

    def exec_resolve(self):
        try:
            IS_TEST
            for path in glob.glob(TOP_PATH + '\\' + self.rel_path + '/*.txt'):
                print("Test: " + path)
                self.initialize(path)
                self.resolve()
                print("\n\n")
        except NameError:
            self.resolve()


class Solver(Common):

    def resolve(self):

        N = int( self.input_data())
        A = list(set(map(int, self.input_data().split())))

        A_sorted = sorted(A)

        index = 0
        remove_list = [0]* (N+1)

        for index in range(0, N-1):
            if remove_list[index] == 1:
                continue
            next = bisect.bisect_left(A_sorted, A_sorted[index]*2)
            for i in range(next, len(A_sorted)):
                if A_sorted[i] % A_sorted[index] == 0:
                    remove_list[i] = 1

        count = 0
        for i in remove_list:
            count += (1 - i)
        print(str(count-1))


solver = Solver(REL_PATH)
solver.exec_resolve()

Submission status: Runtime Error

Solution code:
n = int(input())

a = list(map(int, input().split()))
a.sort()
valid = valid = [1] * n
ret = 0
tgt = 0

print(a)

while True:
	num = a[tgt]
	valid[tgt] = 0
	print("tgt",tgt,num)

	for i in range((tgt+1),n):
		print(a[i],num,a[i]%num)
		if(a[i]%num == 0):
			valid[i] = 0
	
	ret += 1
	
	for i in range((tgt+1),n):
		if(valid[i] == 1):
			tgt = i
			break


	if(i==n-1):
		if(tgt == n-1):
			ret+=1
		break

if(ret==1):
	print(0)
else:
	print(ret)

Submission status: Runtime Error

Solution code:
import numpy as np

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

sosu = []
count = 0

def loop(target, A):
  global count
  B = []
  flg = True
  for i in range(len(A)):
    if A[i] % target != 0:
      B.append(A[i])
    if target == A[i]:
      flg = False
  if flg:
    count+=1
  if len(B) == 1:
    count+=1
    return
  if len(B) == 0:
    return
  target = B.pop(0)
  loop(target, B)

target = A.pop(0)
loop(target, A)
print(count)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
t = []
for i in range(10):
    t.append([])
for i in range(n):
    j = a[i]//10#24
    t[j].append(a[i])
#print(t)
p = n
for i in range(len(t[0])):
    for j in range(len(t[0])):
        if(i != j):
            if(t[0][i] % t[0][j] == 0):
                p -= 1
                #print(t[0][i],t[0][j])
                break
for i in range(1,10):
    for j in range(len(t[i])):
        x = 0
        for k in range(len(t[i])):
            if(j != k):
                if(t[i][j] ==  t[i][k]):
                    p -= 1
                    #print(t[i][j],t[i][k],-1)
                    x = 1
                    break
        if(x == 0):
            for k in range((i+2)//2):
                for l in range(len(t[k])):
                    if(t[i][j] % t[k][l] == 0):
                        p -= 1
                        #print(t[i][j],t[k][l])
                        x = 1
                        break
                if(x == 1):
                    break

print(p)

Submission status: Runtime Error

Solution code:
import math

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

l = [[] for i in range(2*10**6+1)]

def waru(k,l):
    for i in range(1,int(math.sqrt(k))+1):
        if k % i == 0:
            l[i].append(k)
            l[k//i].append(k)
            
for i in a:
    waru(i,l)
ans_l = [0 for i in range(2*10**5+1)]
for i in a:
    for j in l[i]:
        ans_l[j] += 1

ans = 0
for i in a:
    if ans_l[i] == 1:
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
import copy

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

A.sort()


def div_by_min(a: list, start: int):
    dic = {k: 0 for k in a}
    for i in range(start+1, len(a)):
        if not dic:
            break
        if a[i] % a[start] == 0:
            del dic[a[i]]
    ans_list = list(dic.keys())
    return ans_list


Start = 0
prev_len = 1000000
tmp = A

while True:
    if Start >= len(tmp):
        break
    else:
        tmp = div_by_min(tmp, Start)
        if prev_len == len(tmp):
            Start += 1
        else:
            prev_len = len(tmp)
            Start = 0

print(len(tmp))

Submission status: Runtime Error

Solution code:
#4問目
import math
N = int(input())
A = list(map(int, input().split()))
count = 0
A = list(set(A))
A.reverse()
if len(A) != 1:
    for i in range(N):
        flag = True
        for j in range(i+1, N):
            if A[i] % A[j] == 0:
                flag = False
                break
        if flag == True:
            count += 1
else:
    count = 0
print(count)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
d_l = []
for n in range(len(A)):
    for k in range(len(A)-1, n, -1):
        if A[k] % A[n] == 0:
            if A[k] == A[n]: d_l.append(A[n])
            A.pop(k)
for i, a in enumerate(reversed(A)):
    for d in reversed(d_l):
        if a == d:
           A.pop(i)
print(len(A))

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
c = [0]*len(a)
cnt = len(a)
k = 1
for e in a:
  if c[k]==1:
    continue
  for i in range(k, len(a)):
    if a[i]%e!=0:
      continue
    else:
      c[i] = 1
      cnt -= 1
  k +=1
if c[1]==1 and a[0]!=0:
  print(0)
else:
  print(cnt)

Submission status: Runtime Error

Solution code:
import copy
N = int(input())
A = list(map(int,input().split()))
A.sort()
B = copy.copy(A)
cnt = 0
for i in range(N):
    if A.count(A[i])> 1:
        continue
    for j in range(len(B)):
        if 2 * B[j] > A[i]:
            cnt += 1
            break
        if A[i] % B[j] == 0:
            break
        if j
print(cnt)

Submission status: Runtime Error

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

d_num = a

div = []
a_set = list(set(a))
flag = False
if len(a_set) == 1:
    print(0)
else:
    for i in range(len(a_set)):
        flag = False
        for j in range(len(div)):
            if(a_set[i]%div[j] == 0):
                d_num -= 1
                flag = True
                break
        if flag == False:
            div.append(a_set[i])
    print(1)

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline

def main():
    n = int(input().rstrip())
    a = sorted(list(map(int, input().rstrip().split())))
    count = 0
    b = []
    for i in range(n):
      flag = True
      for x in b:
        if a[i] % x == 0:
          flag = False
          break
      if flag:
        for k in range(n):
          if i != k and a[i] % k ==0;
            flag = False
            break
      if flag:
        count += 1
        b.append(a[i])
    print(count)
  
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:

if len(a)==1:
    print(0)
else:
    while len(a) > 1:
            count += 1
            m = a[0]
            ma = a[-1]
            multi = [m*i for i in range(ma//m + 1)]

            p_set = set(a)
            multi_set = set(multi)
            next_set = p_set - multi_set

            a = list(next_set)
            a.sort()
            
            if len(a) == 1:
                count += 1
                print(count)
                break

Submission status: Runtime Error

Solution code:
#4問目
import math
N = int(input())
A = list(map(int, input().split()))
count = 0
A = sorted(A, reverse=True)
A = list(dict.fromkeys(A))
if len(A) != 1:
    for i in range(N):
        flag = True
        for j in range(i+1, N):
            if A[i] % A[j] == 0:
                flag = False
                break
        if flag == True:
            count += 1
else:
    count = 0
print(count)

Submission status: Runtime Error

Solution code:
import bisect

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]

def index(a, x):
    i = bisect.bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    else:
        return -1

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

A = set(A)
A = list(A)
A.sort()

cnt = 0
for a in A:
    numlist = make_divisors(a)
    div = 0
    for x in numlist:
        if index(A, x) != -1:
            div += 1
    if div != 1:
        cnt += 1
if cnt == 0:
  print 0
 else:
  print(len(A) - cnt)

Submission status: Runtime Error

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

b = sorted(a)

stack = []
stack.push(b[0])
for i in range(1,n):
    flag = 0
    for e in stack:
        if b[i] % e == 0:
            flag = 1
            break
    if flag == 0:
        stack.push(e)

print(len(stack))

Submission status: Runtime Error

Solution code:
import math
n = int(input())
l = list(map(int, input().split()))
l.sort()
if len(l)==l.count(l[0]):
  print(0)
else :
  count = 0
  for i in range(1,n):
    if l[i]==l[i+1] or l[i]==l[i-1]:
      continue
    for j in range(i):
      if math.sqrt(l[i]) < l[j]:
        break
      if l[i] % l[j]:
        break
    else :
      count += 1
  print(count)

Submission status: Runtime Error

Solution code:
import copy
N = int(input())
A = list(map(int,input().split()))
A.sort()
B = copy.copy(A)
cnt = 0
for i in range(N):
    if A.count(A[i])> 1:
        continue
    for j in range(len(B)):
        if 2 * B[j] > A[i]:
            cnt += 1
            break
        if A[i] % B[j] == 0:
            B.remove(A[i])
            break
        if j
print(cnt)

Submission status: Runtime Error

Solution code:
import sys

n = int(input())
li = list(map(int, input().split()))
li.sort()

if len(set(li)) == 1:
  print(0)
  sys.exit()

def del_(list_):
  key = list_.pop(0)
  new = [x for x in list_ if x % key != 0]
  return new

result = 0
j = len(li)

while result <= j:
  if len(li) == 1:
    result += 1
    break
  else:
    if li[0] ==li[1]:
      result -= 1
    li = del_(li)
    result += 1

print(result)

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
Q=[True]*n
a.sort()
t=0
for i in range(n):
    if !Q[j]:
        continue
    b=a[i]
    for j in range(i,n):
        if !Q[j]:
            continue
        if a[j]%b==0:
            Q[j]=False
    t+=1
print(t)

Submission status: Runtime Error

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

def div(x):
  
  i = 2
  while i**2 < x:
    if x % i == 0:
      a = x/i
      if i in A:
        break
      elif a in A:
        break
    i += 1
    if i**2 > x:
      ans_list.append(1)
      break
  

for i in A:
  div(i)
  
print(sum(ans_list)-N + len(set(N)))

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[1:] + upper_divisors[::-1]

# print('input >>')
N = int(input())
As = list(map(int,(input().split())))

As.sort()
print(As)

warusu = set()
ans = 0

# for x in range(len(As)):
    # print(As)

for A1 in As:
    for A2 in sorted(As, reverse=True):
        if A2 % A1 == 0:
            As.remove(A1)

# print('-----output-----')
print(len(As))

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

if N == 1:
    print(1)


daburi = []

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

daburi = set(daburi)
#print(daburi)

f = False
res = 0


i = 0

s = set(b)

while len(s) >= res:
    for j in x:
        if b[i] == j: 
            continue
        if j%b[i]== 0 :
            s.discard(j)
#            print(s)
    i+=1
    res+=1

print(len(s))

Submission status: Runtime Error

Solution code:
N = int(input())
A_ = [int(i) for i in input().split()]
A=set(A_)
if len(_A)>len(A) and len(A)=0:
    print(0)
else:
    A.sort()
    A.reverse()
    times = 0
    for n,i in enumerate(A):
        flag = 0
        for j in list(range(n-1,n))+list(range(n+1,len(A))):
            if A[j]<=i:
                if i%A[j]==0:
                    flag = 1
                    break
        if flag == 0:            
            times+=1   
            
    print(times)

Submission status: Runtime Error

Solution code:
n=int(input())
a=[int(i) for i in input().split()]
b=[0 for i in range(n+1)]
ans=0
for i in a:
    if b[i]==0:
        while i<n:
            b[i]=1
            i*=2
    else:
        ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
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())
A = input().split()
ANS = 0
flag = 0
for i in range(N):
  if is_prime(i) == True:
    for j in range(N):
      if i != j:
        if A[i] == A[j]:
          flag = 1
          break
    if flag = 0:
      ANS += 1
    flag = 0
print(ANS)

Submission status: Runtime Error

Solution code:
#'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

N=int(input())
A=list(map(int, input().split()))
ans=0
for i in range(N):
	for a in A:
		if N[i]==a:
			continue
		else:
			if N[i]%a==0:
				continue
			else:
				flag=1
				break
		if flag==0:
			ans+=1
		flag=0
	
print(ans)