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 = sorted(list(map(int, input().split())), reverse=True)
count = 0
for i in range(N-1):
    for j, k in enumerate(a[i+1:]):
        if i != j+1:
            if a[i] % k == 0:
                break
        if j == N-i-2:
            count += 1
if a[-1] != a[-2]:
    count += 1
print(count)

Submission status: Runtime Error

Solution code:
import sys
from sympy import divisors
from collections import Counter


def main():
    input = sys.stdin.buffer.readline
    n = int(input())
    a_list = list(map(int, input().split()))
    # キーに要素、値に出現回数を持つカウンタ
    a_counter = Counter(a_list)
    ans = 0
    for a in a_list:
        # aの約数の集合
        divs = divisors(a)
        for divisor in divs:
            if a_counter[divisor] > 0:
                if divisor == a and a_counter[divisor] == 1:
                    continue
                break
        else:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

divlist = list()
for i in range(N):
  

for i in range(N):
  for j in range(N):
    if (Alist[i] % Alist[j]) != 0:
      break
  if j + 1 == N:
  	ret += 1

print( ret )

Submission status: Runtime Error

Solution code:
def input_int():
    return map(int, input().split())

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))



N=one_int()

As = many_int()

same = -1 if len(set(As))==1 else 0

As = sorted(As)

count=0
for a in As:
    ind = bisect.bisect_left(As, a//2 + 1)
    
    flg=True
    for b in As[:ind]:
        if a%b==0:
            flg=False
    if flg:
        count+=1
        
print(count+same)

Submission status: Runtime Error

Solution code:
visited=[False]*(10**6+1)

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

if A[1]==1:
  print(0)
  exit()
if A[0]==1:
  print(1)
  exit()
ans=0
for i in range(N):
  if visited[A[i]]:
    continue
  if i < N-1 and A[i]==A[i+1]:
    continue
  ans+=1
  index=1
  while A[i]*index<=10**6:
    visited[A[i]*index]=True
    index+=1
    
print(ans)

Submission status: Runtime Error

Solution code:
import sympy
from copy import copy

N = int(input())
As = list(map(lambda x: int(x), input().split(" ")))

result = 0

for i, a in enumerate(As):
    temp_list = copy(As)
    del temp_list[i]
    temp_set = set(temp_list)
    candidate = set(sympy.divisors(a))
    if len(candidate & temp_set) == 0:
        result += 1

print(result)

Submission status: Runtime Error

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

a.sort()
if a[0]==a[1]:
    flag=True
else:
    flag=False
for i in range(n-1):
    if a[i]==0:
        continue
    else:
        for j in range(i+1,n):
            # print(a[j],a[i])
            if a[j]%a[i]==0:
                a[j]=0
            # print(a)

print(n-a.count(0)-1 if flag else n-a.count(0))

Submission status: Runtime Error

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
A.sort()
cnt=0
if A[0]!=A[1]:
    cnt+=1
for i in range(1,N):
    flag=False
    for t in range(0,i):
        if A[i]%A[t]==0:
            flag=True
            break
        elif A[t]>(A[i]/A[0]):
            break
    if flag==False:
        cnt+=1
print(cnt)

Submission status: Runtime Error

Solution code:
n = int(input())

a = [0 for _ in range(n)]
a = [int(s) for s in input().split()]
list.sort(a,reverse=False)

cnt = 0
for i in range(n):
    #print(a[i])
    for j in range(i):
        if(i == j):
            continue

        if(a[i]%a[j] == 0):
            cnt += 1
            break

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

Submission status: Runtime Error

Solution code:
import math
import numpy as np

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

gcd_list=np.zeros((N,N))
for i in range(N):
  for j in range(i+1,N):
    temp_gcd=math.gcd(A[i], A[j])
    gcd_list[i][j]=temp_gcd
    gcd_list[j][i]=temp_gcd
    
ans=0
for i in range(N):
  counter=0
  for j in range(N):
    if gcd_list[i][j]==A[j]:
      break
    else:
      counter+=1
  if counter==N:
    ans+=1
    #print(i)
print(ans)

Submission status: Runtime Error

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

ls = []
for i in range(N):
    if A.count(A[i]) == 1:
        ls.append(A[i])

if len(ls) == 0:
    print(0)
else:
    limit = int(ls[-1] ** 0.5)
    ans = 0
    while limit > ls[0]:
        if len(ls) == 1:
            ans += 1
        elif ls[0] != ls[1]:
            ans += 1
        ls = [i for i in ls if i % ls[0] != 0]
    
    print(ans+len(ls))

Submission status: Runtime Error

Solution code:
import sys


n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
y = [0 for i in range(max(a) + 1)]
same = [0 for i in range(max(a) + 1)]
for i in a:
    same[i] += 1

# 約数
def divisor(x):
    ret = []
    for i in range(1, int(x ** 0.5) / 2 + 1):
        if x % i == 0:
            if y[i] == 1 or y[x // i] == 1:
                return False
    return True


ans = 0
for i in a:
    if divisor(i) and same[i] <= 1:
        ans += 1
    y[i] = 1


print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
seen = [0]*(200000+1)
A.sort()
ans = 0
for a in A:
    if seen[a] == 0:
        ans += 1
        x = a
        j = 1
        while x <= 200000:
            seen[x] = 1
            j += 1
            x = a*j
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()))
    ans = 0

    a.sort()

    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 = []

    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:
n, *A = map(int, open(0).read().split())
X = [0] * (10**6 + 1)
c = 0
for a in A:
    X[a] += 1
for a in A:
    B = divisors(a)
    X[a] -= 1
    c += all(X[b] == 0 for b in B)
    X[a] += 1
print(c)

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys

stdin = sys.stdin
ns = lambda: stdin.readline().rstrip() # ignore trailing spaces
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))


def BinarySearch(num, List):
    if len(List) == 0:
        print("Erorr : list has no element")
        return
    left,right = 0,len(List)
    while left < right:
        mid  = (left+right)//2
        if num < List[mid]:#
            right = mid
        else:
            left = mid + 1
    return right


def main():
    nn = ni()
    atmp = sorted(na())
    a = []
    if atmp[0] != atmp[1]:
        a = [atmp[0]]
    pre = atmp[0]
    for i in range(1, nn):
        if pre != atmp[i]:
            a += [atmp[i]]
    n = len(a)
    if n == 0:
        print(0)
        return
    asub = [i for i in a]
    ans = 0
    for i in range(n):
        ai = a[i]
        if ai != -1:
            ans += 1
            cnt = 2
            right = i
            while right != n:
                right = BinarySearch(ai*cnt, asub)
                if a[right-1] == ai*cnt:
                    a[right-1] = -1
                cnt += 1
    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))

from collections import Counter

n = ii()
A = iil()

di = Counter(A)
A.sort()

ans = 0
l = []
for item in A:
    if di[item] > 1:
        if l[-1] != item:
            l.append(item)
        continue
    flag = True
    for i in l:
        if item%i == 0:
            flag = False
            break
    if flag:
        l.append(item)
        ans += 1
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from sys import stdin


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


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    N = int(_in[0])  # type:int
    A_arr = set(map(int, _in[1].split(' ')))  # type:set(int)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    A_div = [[] for i in range(N)]
    for i, A in enumerate(A_arr):
        _ = make_divisors(A)
        _.remove(1)
        A_div[i] = set(_)

    ans = 0
    for i, A_d in enumerate(A_div):
        if len(A_d & A_arr) == 1:
            ans += 1
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
seen = [0]*(200+1)
A.sort()
ans = 0
for a in A:
    if seen[a] == 0:
        ans += 1
        x = a
        j = 1
        while x <= 200:
            seen[x] = 1
            j += 1
            x = a*j
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
s = list(map(int,input().split()))
s.sort(reverse=True)
sum = 0
for i in range(n-1):
    for j in range(i+1,n):
        if s[i]==s[j]:continue
        if s[i]%s[j]==0:
            break
        if j==n-1:sum+=1

if s[-1]!=s[-2]:sum+=1
print(sum)

Submission status: Runtime Error

Solution code:
from math import gcd
from collections import Counter
n = int(input())
a = list(map(int,input().split()))
a.sort()
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
M = max(a)
cnt = [0]*(M+1)
ans = 0
for i in range(n):
    if cnt[a[i]]:
        continue
    j = a[i]
    if i == 0:
        if a[i] == a[i+1]:
            1
        else:
            ans += 1
    elif i == n-1:
        if a[i-1] == a[i]:
            1
        else:
            ans += 1
    elif a[i] == a[i+1] or a[i-1] == a[i]:
        1
    else:
        ans += 1
    while j <= M:
        cnt[j] = 1
        j += a[i]
print(ans)

Submission status: Runtime Error

Solution code:
def resolve():
    import bisect
    import math
    n = int(input())
    a = list(map(int, input().split()))
    a = sorted(a)
    maxa = a[-1]
    maxi = bisect.bisect_right(a, math.ceil(maxa**0.5))

    ans = [1]*n
    for i in range(0, maxi+1):
        if ans[i] == 1:
            for j in range(i+1, n):
                if ans[j] == 0:
                    continue
                if a[j] == a[i]:
                    ans[i] = 0
                if a[j] % a[i] ==0:
                    ans[j] = 0
    print(sum(ans))
resolve()

Submission status: Runtime Error

Solution code:
from collections import deque
N = int(input())
A = sorted([int(x) for x in input().split()])
D = deque(A)
ans = 0
if A[0] == A[1]: 
    ans -= 1
while len(D):
    a = D.popleft()
    ans += 1
    D = deque(filter(lambda x: x%a != 0, D))
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from collections import Counter
import bisect
N = int(input())
A = list(map(int,input().split()))

cnt = Counter(A)
A.sort()
ans = 0
for j in range(len(A)):

    a = A[j]
    if cnt[a] > 1:
        continue
    if j==0:
        ans+=1

    i = bisect.bisect_right(A, pow(a,0.5))
    #print(a,i)


    ok = True

    while(i>=0):
        if a % A[i]==0:
            #print (a,A[i])
            ok = False
            break
        i-=1
    if ok:
        #print(a)
        ans+=1
print (ans)

Submission status: Runtime Error

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

divlist = list()
for i in range(N):
  

for i in range(N):
  for j in range(N):
    if Alist[i] % Alist[j] != 0:
      break
  if j + 1 == N:
  	ret += 1

print( ret )

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import sympy

num = int(input())
a = list(map(int, input().split()))
b = 0
for i in a:
  for f in sympy.divisors(i)[:-1]:
    if f in a:
      b += 1
      break
print(num - b)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

readline = sys.stdin.readline

@njit('i8(i8[:])', cache=True)
def solve(a):
    ans = 0
    while len(a):
        if len(a) != 1:
            if a[0]==a[1]:
                a = a[a != a[0]]
                continue
        ans += 1
        a = a[a % a[0] != 0]
    return ans

n = int(input())
a = np.array(readline().split(), dtype=np.int64)
a.sort()
print(solve(a))

Submission status: Runtime Error

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

ans = 0
temp = []
temp.append(A[0])
if A[0]!=A[1]:
    ans += 1


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

    if check == 0:
        ans += 1
        temp.append(A[i])
        
if A[0]==1:
    if A[1]==1:
        print(0)
    else:
        print(1)
else:
    print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
A.sort()
ans =0
X=0
Y=0

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

for i in range(1,N):
  for j in range(i):
    if A[i] % A[j] !=0:
      X +=1
    else:
      Y +=1
  
  if X == i:    
    ans +=1
  
    
  X =0
  Y =0
  
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import sympy

num = int(input())
a = list(map(int, input().split()))
b = 0
for i in a:
  for f in sympy.divisors(i)[:-1]:
    if f in a:
      b += 1
      break
print(num - b)

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
import numpy as np

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
def main():
    n = int(input())
    a = list(map(int, input().split()))
    dic = defaultdict(int)
    a.sort()
    f = seachPrimeNum(max(a))
    ans = 0
    for i in range(n):
        x = a[i]
        if i < n-1 and a[i] == a[i+1]:
            dic[a[i]] = 1
            continue
        flag = 1
        for check in f:
            if check >= int(x**0.5)+1:
                break
            if(x%check==0):
                if dic[check]:
                    flag = 0
                    break
                if dic[x//check]:
                    flag = 0
                    break
        if flag:
            ans += 1
        dic[a[i]] = 1
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = set(i for i in range(n))
ans = [0]*n
warizai_index = set()

for i in range(n):
    for wari in warizai_index:
        if a[i]%a[wari] == 0 and i != wari:
            ans[i] = 1
            b.remove(i)
            break
    if ans[i] == 1:
        continue
    
    for j in b:
        if i == j:
            continue
        if a[i]%a[j] == 0:
            ans[i] = 1
            b.remove(i)
            warizai_index.add(j)
            b.remove(j)
            break

print(ans.count(0))

Submission status: Runtime Error

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

a.sort()

MAXN = 2 * 10 ** 5


def prime_factorization(n):
    pmax = int(n ** 0.5 // 1) + 1

    factors = {}
    for p in range(2, pmax + 1):
        while n % p == 0:
            factors[p] = factors.get(p, 0) + 1
            n //= p
    if n != 1:
        factors[n] = factors.get(n, 0) + 1

    return factors


divisors = [False for _ in range(MAXN + 1)]
answer = 0
apast = None
for i, ai in enumerate(a):
    if ai == apast:
        is_good = False
    elif i < n - 1 and ai == a[i + 1]:
        is_good = False
    else:
        is_good = not divisors[ai]

        m = 1
        while ai * m <= MAXN:
            divisors[m * ai] = True
            m += 1

        # factors = prime_factorization(ai)
        # factors[1] = 1
        # for p, m in factors.items():
        #     pm = 1
        #     for i in range(m):
        #         p *=
        #         if p ** (i + 1) in divisors:
        #             is_good = False
        #             break
        #     if not is_good:
        #         break

    if is_good:
        answer += 1

    apast = ai


print(answer)

Submission status: Runtime Error

Solution code:
N = map(int, input().split())
A = list(map(int, input().split()))
ls = [0 for i in range(0, 2*(10**5)+2)]
for a in A:
    ls[a] += 1

ans = 0

for a in A:
    if ls[a] >= 2 or ls[1] >= 1:
        continue
    flag = True
    i = 2
    while(i <= a//i):
        while (a % i != 0):
            i += 1
        if i >= a:
            break
        # print(i, a//i)
        if ls[i] or ls[a//i]:
            flag = False
            break
        i += 1

    if flag:
        # print("ok: ", a)
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
import sequtils
import strutils

var N: int64 = stdin.readLine.parseBiggestInt()
var A: seq[int64] = stdin.readline.split.map(parseBiggestInt)
var answers: int = 0

for i, a in A:
    var not_divisible = true
    for j, b in A:
        if i == j:
            continue
        if a mod b == 0:
            not_divisible = false
            break
    if not_divisible:
        answers += 1
echo answers

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
    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:
n = int(input())
a_l = list(map(int,input().split()))
a_l.sort()

cnt = 0
for i in range(n-1,-1,-1):
    if len(a_l) < i-1:
        continue
    if len(a_l) == 0:
        break

    for j in range(len(a_l)-(1+cnt)):
        x = a_l[i]
        if x % a_l[j] == 0:
            while x in a_l:
                a_l.remove(x)
            break
    else:
        cnt += 1

print(cnt)

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
a=[int(j)for j in input().split()]
a.sort()
s=set()
ans=0
i=0
while i<len(a):
    for j in a[i+1:]:
        if a!=[]:
            if j%a[i]==0:
                a.remove(j)
                while j in a:
                    a.remove(j)
            else:
                i+=1
        else:
            break
print(len(a))

Submission status: Runtime Error

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

# print(li)
li.sort()
# print(li)

one = [1 for _ in range(n)]

if li[0] == li[1]:
    one[0] = 0

check = [i for i in range(1, n)]

for i in range(n-1):
    a = set([_ for _ in range(i+1, n)]) & set(check)
    for j in a:
        if li[j] % li[i] == 0:
            one[j] = 0
    del check[0]
print(sum(one))

Submission status: Runtime Error

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

if a[0] != a[1]:
    ans = 1

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

Submission status: Runtime Error

Solution code:
def ra(a): #圧縮された要素を非保持
    ll,l=[],1
    for i in range(len(a)-1):
        if a[i]==a[i+1]:
            l+=1
        else:
            ll.append(l)
            l=1
    ll.append(l)
    return ll

n=int(input())
a=list(map(int,input().split()))
b=[1]*(10**6+10)
c=0
d=ra(a)
for i in d:
    if i!=1:
        c-=i
for i in range(n):
    e=a[i]
    for j in range(2,10**6+4):
        b[a[i]*j]=0
        if a[i]*(j+1)>=10**6+5:
            break
for i in range(n):
    c+=b[a[i]]
print(c)

Submission status: Runtime Error

Solution code:
import numpy as np

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

def main():
    ans = 0
    for i, ai in enumerate(A):
        ans += ((ai % np.delete(A, i)).min() != 0)
    print(ans)

main()

Submission status: Runtime Error

Solution code:
import glob
import os

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(map(int, self.input_data().split()))

        A_sorted = sorted(A)

        index = 0
        while True:
            remove_list = []
            for i in range(index+1, len(A_sorted)):
                if A_sorted[i] % A_sorted[index] == 0:
                    remove_list.append(i)
            if A_sorted[index] == A_sorted[index+1]:
                remove_list.insert(0,index)
            else:
                index += 1

            for i in range(len(remove_list)-1, -1, -1):
                A_sorted.pop(remove_list[i])

            if index >= len(A_sorted)-1:
                break

        print(str(len(A_sorted)))


solver = Solver(REL_PATH)
solver.exec_resolve()

Submission status: Runtime Error

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

Submission status: Runtime Error

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

A.sort()
ans=N
i=0
while i<N:
    if i==0 and A[i]==A[i+1]:
        ans-=1
        i+=1
        continue
    if A[i]==A[i-1]:
        ans-=1
        i+=1
        continue
    for a in A[:i]:
        if A[i]%a==0:
            ans-=1
            break
        if i>10**4 and a>int(A[i]**0.5)+1:
            break
    i+=1

print(ans)

Submission status: Runtime Error

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

A.sort()

ans = 0

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

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

print(ans)

Submission status: Runtime Error

Solution code:
N=int(input())
a=list(map(int,input().split()))
A=a.sort(reverse=True)
S=0
for i in range(N):
	flag = 0
	max=A[i]**(1/2)
	for j in range(i+1,N):
		if A[j]<=max:
			if A[i]%A[j]==0:
				frag=1
				break
		if flag == 0:
			S=S+1
print(S)

Submission status: Runtime Error

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

ans = 0
temp = []
temp.append(A[0])
if A[0]!=A[1]:
    ans += 1


for i in range(1,N):
    check = 0
    for j in temp:
        if A[i]%j==0:
            check += 1

    if check == 0:
        ans += 1
        temp.append(A[i])
        
if A[0]==1:
    if A[1]==1:
        print(0)
    else:
        print(1)
else:
    print(ans)

Submission status: Runtime Error

Solution code:
from numba import jit

@jit(parallel=True)
def check():
    global ans
    for x in arr:
        if x in s:
            ok=False
            break
    if ok:
        ans+=1
        
@jit(parallel=True)
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=list(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 range(N):
    if A[i] in ng:
        continue
    s.remove(A[i])
    arr=factor(A[i])
    ok=True
    check()
    s.add(A[i])
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
import random
from decimal import Decimal
import itertools
import re
import bisect
from collections import deque, Counter
from functools import lru_cache

sys.setrecursionlimit(10**9)
INF = 10**13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
def SERIES(n): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ')
def GRID(h,w): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ').reshape(h,-1)[:,:w]
def GRIDfromString(h,w): return np.frombuffer(sys.stdin.buffer.read(), 'S1').reshape(h,-1)[:,:w]
MOD = 1000000007

def main():
	n = I()
	A = np.array(LI())
	A.sort()
	count = 0
	i = 0
	while True:
		if i == 0:
			if A[i] != A[i+1]:
				count += 1
			i += 1
		else:
			try:
				if np.all(A[i]%A[:i]!=0):
					count += 1
					i += 1
				else:
					A = np.delete(A, i)
			except IndexError:
				break
	print(count)




if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

A.sort(reverse=True)

cnt=0
for i in range(N-1):
    for j in reversed(range(i+1,N)):
        if A[i]%A[j]==0:
            cnt+=1
            break
if A[-1]%A[-2]==0:
    cnt+=1
print(N-cnt)

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(i))
    temp2 = bisect.bisect(a,temp)
    for j in (0,temp2+1):
        if(a[i] % a[j] == 0 and i != j):
            flag = 0
            break
    if(flag == 1):
        count += 1

print(count)

Submission status: Runtime Error

Solution code:
def _main(n, a_list):
    a_list.sort()
    count = 0
    for i in range(n):
        i_value = a_list[i]
        fail = False
        for j in range(0, i + 2):
            if i == j:
                continue
            j_value = a_list[j]
            q, mod = divmod(i_value, j_value)
            if mod == 0:
                fail = True
                break
        if not fail:
            count += 1

    print(count)


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

Submission status: Runtime Error

Solution code:
visited=[False]*(10**6+1)

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

if A[1]==1:
  print(0)
  exit()
if A[0]==1:
  print(1)
  exit()
ans=0
for i in range(N):
  if visited[A[i]]:
    continue
  ans+=1
  index=1
  while A[i]*index<=10**6+1:
    visited[A[i]*index]=True
    index+=1
num=0
for i in range(1,N):
  if A[i]==A[i-1] and num!=A[i]:
    ans-=1
    num=A[i]
    
print(ans)

Submission status: Runtime Error

Solution code:
import sequtils
import strutils

var N: int = stdin.readLine.parseInt()
var A: seq[int] = stdin.readline.split.map(parseInt)
var answers: int = 0

for i, a in A:
    var not_divisible = true
    for j, b in A:
        if i == j:
            continue
        if a mod b == 0:
            not_divisible = false
            break
    if not_divisible:
        answers += 1
echo answers

Submission status: Runtime Error

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

A.sort()
ans=0

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

if A[0]==1 and A[1]==1:
    print(0)
    exit()
elif A[0]==1 and A[1]!=1:
    print(1)
    exit()

for i in range(1,N):
    if A[i]==A[i-1] or ((i!=N-1) and (A[i]==A[i+1])):            
        continue
    for j in range(i):
        if A[i]%A[j]==0:
            break
        if j==i-1:
            ans+=1

print(ans)