Problem:


Score : 400 points

Problem Statement

Given is a number sequence A of length N.

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

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

Constraints

All values in input are integers.

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

1 \leq A_i \leq 10^6

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answer.

Sample Input 1

5
24 11 8 3 16

Sample Output 1

3

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

Sample Input 2

4
5 5 5 5

Sample Output 2

0

Note that there can be multiple equal numbers.

Sample Input 3

10
33 18 45 28 8 19 89 86 2 4

Sample Output 3

5



Sample input:
5
24 11 8 3 16


Sample output:
3

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
from math import floor, sqrt, factorial, hypot, log  # log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter, defaultdict, deque
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint


def ceil(a, b): return (a + b - 1) // b


inf = float('inf')
mod = 10 ** 9 + 7


def pprint(*A):
    for a in A:     print(*a, sep='\n')


def INT_(n): return int(n) - 1


def MI(): return map(int, input().split())


def MF(): return map(float, input().split())


def MI_(): return map(INT_, input().split())


def LI(): return list(MI())


def LI_(): return [int(x) - 1 for x in input().split()]


def LF(): return list(MF())


def LIN(n: int): return [I() for _ in range(n)]


def LLIN(n: int): return [LI() for _ in range(n)]


def LLIN_(n: int): return [LI_() for _ in range(n)]


def LLI(): return [list(map(int, l.split())) for l in input()]


def I(): return int(input())


def F(): return float(input())


def ST(): return input().replace('\n', '')


def main():
    N = I()
    A = LI()
    A.sort(reverse=True)
    lis = {}
    bef = -1
    for a in A:
        if a == bef:
            continue
        else:
            lis[bef] = 1
            bef = a
    if A[-1] != A[-2]:
        lis[A[-1]] = 1
    del lis[-1]
    ans = 0
    while lis.__len__():
        p, _ = lis.popitem()
        ans += 1
        keys = lis.keys()
        dellis = []
        for k in keys:
            if k % p == 0:
                dellis.append(k)
        for k in dellis:
            del lis[k]
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
import math
sys.setrecursionlimit(10**8)
from bisect import bisect_left


def divisors(n):
    ret = set()
    for i in range(1, int(n ** 0.5) + 1):
        d, m = divmod(n, i)
        if m == 0:
            ret.add(i)
            ret.add(d)
    return ret


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

    # 愚直に行うとO(N^2)となる
    # 各要素、約数を列挙(sqrt(N))
    # 約数がこれまでに存在したかをチェックO(1)
    # 存在すれば1を加える

    ans = 0
    past = set()
    for i in range(len(A)):
        flag = False
        for d in divisors(A[i]):
            if d in past:
                flag = True
                break
        if flag:
            ans += 1
        past.add(A[i])

    if A[0] != A[1]:
        print(N-ans)
    else:
        print(N-ans-1)

    return


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:

N = int(input())
As = input().split()
A = []

for i in range(N):
    A.append(int(As[i]))

rA = sorted(A)

count = 0
dividable = False


for i in range(1):
    if rA[0]%rA[i+1]==0:
        dividable = True
if dividable==False:
    count += 1
else:
    dividable = False

for i in range(1, len(rA)):
    for s in range(i):
        if rA[i]%rA[s] == 0:
            dividable = True
    if dividable==False:
        count += 1
    else:
        dividable = False

print(count)

Submission status: Runtime Error

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

a = sorted(set(a))
w = 0
h = 0
while True:
    h = 1
    while True:
        if w + h == len(a):
            print(a)
            break
        if a[w+h] % a[w] == 0:
            print(h)
            del a[w+h]
        else:
            print(a[w+h], h, w, a)
            h += 1
    w += 1
    if w == len(a):
        print(len(a))
        exit()

Submission status: Runtime Error

Solution code:
N = int(input())
a = list(map(int,input().split()))
b = []
if N == 1:
  print(1)
  exit()
a.sort()
k = 2*N
c = {}
if a[0] == a[1]:
  c = {a[0]}
  for i in range(1,N-1):
    if a[i] != a[i+1]:
      k = i+1
      break
  if k == 2*N:
    print(0)
    exit()
else:
  b = [a[0]]
  k = 1
for i in range(k,N):
  if i < N-1:
      if a[i] == a[i+1] or a[i-1] == a[i]:
        c.append(a[i])
      else:
        d = 0
        for j in b:
          if a[i]%j ==0:
            d = 1
          if 2*j > a[i]:
            break
        for j in c:
          if a[i]%j == 0:
            d = 1
          if 2*j > a[i]:
            break
        if d == 0:
          b.append(a[i])
  elif a[i-1] != a[i]:
    d = 0
    for j in b:
      if a[i]%j ==0:
        d = 1
      if 2*j > a[i]:
        break
    for j in c:
      if a[i]%j == 0:
        d = 1
      if 2*j > a[i]:
        break
    if d == 0:
      b.append(a[i])
          
print(len(b))
#print(b)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
if n == 1:
    print(1)
    exit()
flag = [True for i in range(10**6+1)]
a.sort()
for i in range(n):
    if flag[a[i]] == False:
        continue
    if i >= 1:
        if a[i] == a[i-1]:
            continue
    for j in range(2,(10**6)//a[i]+1):
        flag[a[i]*j] = False
ans = 0
for i in range(n):
    if flag[a[i]]:
        if i >= 1:
            if a[i] == a[i-1]:
                continue
        if i <= n-1:
            if a[i] == a[i+1]:
                continue
        ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
import numpy as np
def update(dt):
    t = dt[0]
    is_f = False
    if t in dt[1:]:
        is_f = True
    dtu = filter(lambda x: x % t != 0, dt[1:])
    if is_f:
        return list(dtu), False
    else:
        return list(dtu), t

res = []
resid = 0
while True:
    if len(A) == len(set(A)) and A[0] > A[len(A)-1]//2:
        resid = len(A)
        break
    A, t = update(A)
    if t:
        res.append(t)

print(len(res) + resid)

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

A.sort()
if A[0] == 1 and A[1] == 1:
    ans = 0
elif A[0] == 1 and A[1] != 1:
    ans = 1
else:
    for a in A:
        checked = [y for y in A if y != a]
        if A.count(a) >= 2: A = checked
        removed = [x for x in checked if x % a == 0]
        if len(removed) == 0:
            break
        else:
            A = list(filter(lambda x: x not in removed, A))
    ans = len(A)

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
lis=[]
for i in range(101):
    lis.append(i)
lis.remove(0)

listA=[]
while True:
    try:
        listA.append(list(map(int,input().split())))
    except:
        break;
#print(listA)

X_=listA[0]
X =X_[0]
P =listA[1]

arr = np.array(lis)
P_max = max(P)
P_min = min(P)-1
arr=arr[arr<=P_max]
arr=arr[arr>=P_min]
lis=arr.tolist()
for p in P:
	lis.remove(p)
#print(lis)
lis_=[]
for l in lis:
    lis_.append(abs(l-X))
#print(lis_)
lis_min=min(lis_)
   
def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

print(lis[my_index(lis_, lis_min)])

Submission status: Runtime Error

Solution code:
n = int(input())
la = list(map(int, input().split()))
la.sort()
la = [a for a in la if la.count(a) == 1]
ans = 0
if la != []:
  if la[0]==1:
    ans += 1
    del l[0]
  while 1:
    if la == []:
      break
    i = la[0]
    la = [a for a in la if a % i != 0]
    ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
from sympy import divisors
n = int(input())
a = list(map(int, input().split()))
b = list(map(lambda n: divisors(n), a))

cnt = n
for i in range(n):
    for j in range(n):
        if i != j and a[i] in b[j]:
            cnt -= 1
            break
print(cnt)

Submission status: Runtime Error

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

import numpy as np

A.sort()
A = A[::-1]

flags = np.ones(N)
for i in range(N):
    for j in range(N-i-1):
        if A[i]%A[j+i+1] == 0:
            flags[i] = 0
            break
if A[-1] == A[-2]:
    flags[-1] = 0
print(int(np.sum(flags)))

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int, input().split()))
a.sort()
ans = 0
c= 0 #調べ始める位置する数
if a[0] != a[1]:
    c = 1
    ans = 1
else:
    c = a.count(a[0])

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

Submission status: Runtime Error

Solution code:
n = int(input())
nums = [int(e) for e in input().split()]
import numpy as np
npnums = np.array(nums)

cnt = 0 #個数のカウント

test = np.zeros(n*n).reshape(n,n)
for i,v in enumerate(nums):
    test[i] +=v

mask = (test % npnums ==0)

for i in mask:
    if np.count_nonzero(i) >1:
        cnt+=1

print(n-cnt)

Submission status: Runtime Error

Solution code:
from collections import Counter
import sympy

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

counter = Counter(A)

ans = 0
for k, v in counter.items():
    if v != 1:
        continue
    can = True
    for d in sympy.divisors(k):
        if d == k:
            continue
        if d in counter:
            can = False
    if can:
        ans += 1

print(ans)

Submission status: Runtime Error

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

als = sorted(al)

m = als[-1]

from collections import Counter
c = Counter(als)

def sieve_of_eratosthenes(n): #エラトステネスのふるい
    candidate = list(range(2, n+1)) #候補
    prime = []
    limit = n**0.5 + 1 #+1がないと平方数を素数にしてしまう

    while True:
        p = candidate[0] 
        if limit <= p:
            prime.extend(candidate) #この時点での残っているのは素数
            break
        prime.append(p) #pを素数リストに登録

        candidate = [i for i in candidate if i % p != 0]

        # i = 0
        # while True:
            # if i >= len(candidate): #iはcandidateの長さ分
                # break
            # elif candidate[i] % p == 0: #余りがゼロなら
                # candidate.pop(i) #素数ではないのでpop(取り除く)する
            # i += 1

    return prime

prime = sieve_of_eratosthenes(m)

res = 0
for i in range(n):
    flg = 0
    j = als[i]
    if c[j] >1:
        pass
    elif j in prime:
        res += 1
    else:
        for k in range(i):
            if j % als[k] ==0:
                flg = 1
                break
        if flg != 1:
            res += 1
print(res)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
tmp=set()
onaji=set()
if a[0]!=a[1]:
    tmp.add(a[0])
for i in range(1,n-1):
    flg=True
    if a[i]==a[i+1] or a[i]==a[i-1]:
        flg=False
    for j in tmp:
        if a[i]%j==0:
            flg=False
    if flg:
        tmp.add(a[i])
flg=True
if a[n-1]==a[n-2]:
    flg=False
for i in tmp:
    if a[n-1]%i==0:
        flg=False
if flg:
    tmp.add(a[n-1])
print(len(tmp))

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
d = {}
n = A[-1]
def makePrimeChecker(n):
    isPrime = [True] * (n + 1)
    isPrime[0] = False
    isPrime[1] = False
    i = 0
    for j in A:
        if i == j:
            d[i] = 1
        i = j
        if i > 10**3:
            break
        if isPrime[i]:
            for j in range(i * i, n + 1, i):
                isPrime[j] = False
    return isPrime
P = makePrimeChecker(n)
i = 0
ans = 0
for j in A:
    if i == j:
        continue
    else:
        i = j
        if P[i]:
            if d[i] == 0:
                ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
from sys import stdin

A = int(stdin.readline())
B = list(map(int,stdin.readline().split()))
B.sort()
count=0

while len(B)>0:
    if len(B)==1:
        if Q==0:
           count+=1
        break
    K=B[0]
    B.remove(B[0])

    Q=0
    D=B.copy()
    for t in D:

        if t==K:
            Q=1
        if t%K==0:
            B.remove(t)

    if Q==0:
       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()
    Boo = [True]*len(B)
    _,s = sieve((10**6)+7)

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

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

    cnt = 0
    for i in range(len(B)):
        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:
# import numpy as np
# import heapq

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

N = int(input())

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

As.sort()

sosus = set([As[0]])
ans = 1

for i in range(1, N):
    a = As[i]
    prime_factors = prime_factorize(a)
    if len(prime_factors) == 1:
        sosus.add(a)
        if a != As[min(i+1, N-1)] or a != As[i-1]:
            ans += 1
        continue

    flag = True
    for sosu in sosus:
        if a % sosu == 0:
            flag = False
            break
        elif sosu > a//2:
            break
    if flag:
        sosus.add(a)
        ans += 1

if As[0] == As[1]:
    print(ans - 1)
else:
    print(ans)

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
        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:
import sys
import numpy as np

N = int(sys.stdin.readline())
A = [int(x) for x in sys.stdin.readline().split()]
A.sort(reverse=True)

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

print(ans)

Submission status: Runtime Error

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

counter = 0

A.sort(reverse=True)


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

Submission status: Runtime Error

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

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

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

    cnt = 0
    for i in range(len(B)):
        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 sympy import sieve

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

ans = 0

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

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
n=int(input())
a=np.array(list(map(int,input().split())))
ans=0
b=np.cumsum(a)
for i in range(n):
    for j in range(n):
      if a[i]%(b[j+1]-b[j])==0 and i!=j:
          break
      if j==n-1:
          ans+=1
print(ans)

Submission status: Runtime Error

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

A = sorted(A)
li = []
co = []
count = 0
line = A[-1]//A[0]

for i, a in enumerate(A):
    judge = True
    if a == 1:
        if A[i+1] == 1:
            break
        else:
            count += 1
            break
    elif a > 3:
        for j in range(len(li)):
            if a % li[j] == 0:
                judge = False
                if a == li[j]:
                    count -= co[j]
                    co[j] = 0
                break
            elif li[j] > a//2:
                break
        if judge:
            count += 1
            li.append(a)
            co.append(1)
    else:
        if a not in li:
            li.append(a)
            count += 1
        else:
            count -= co[-1]
            co[-1] = 0

print(count)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

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

ans=0

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

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

print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter

def fctr1(n): 
    f=[]
    c=0
    r=int(n**0.5)
    for i in range(2,r+2):
        while n%i==0:
            c+=1
            n=n//i
        if c!=0:
            f.append(i)
            c=0
    if n!=1:
        f.append(n)
    return f

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: # choufuku
                divisors.append(n//i)
    # divisors.sort()
    return divisors


exists = [False] * (2 * (10 ** 5) + 1)

input = raw_input
n0 = int(input())
As_0 = map(int, input().split(" "))

counter = Counter(As_0)
As = counter.keys()
n = len(As)

#As = sorted(As, reverse=True)
out = 0

for A in As:
    exists[A] = True

for i in range(n):
    A1 = As[i]

    num = counter[A1]
    if num >= 2:
        continue
    
    exist = False

    ds = make_divisors(A1)
    for d in ds:
        if d != A1 and exists[d]:
            exist = True

    #for j in range(i+1, n):
    #    A2 = As[j]
    #    if A1 % A2 == 0:
    #        exist = True
    #        break
    if not exist:
        #print(A1)
        out += 1

print(out)

Submission status: Runtime Error

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

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

c = Counter(A)
A = [i[0] for i in c.items() if i[1] == 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:
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 = set([i for i in range(1, n)])

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

A_sort = sorted(A, reverse=True)

cnt = 0

for i in range(N):
    for j in range(i+1, N):
        if A_sort[i] % A_sort[j] == 0:
            break
        elif j==N-1:
            cnt += 1

if A_sort[-1] != A_sort[-2]:
    cnt += 1

print(cnt)

Submission status: Runtime Error

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

if(len(set(a))==1 and len(a)>1):
    print(0)
    exit()

    
a.sort()


#print(a)
i=0
j=1
while(i<=n):
    j=i+1
    if(a[i]*2>a[-1]):
        break
    while(j<n):

        if(a[j]%a[i]==0):
            a.pop(j)
            n-=1
            continue
        j+=1

    i+=1
           
#print(a)

print(len(a))

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
d = {}
def makePrimeChecker(n):
    isPrime = [True] * (n + 1)
    isPrime[0] = False
    isPrime[1] = False
    for j in A:
        if i == j:
            d[i] = 1
        i = j
        if i > 10**3:
            break
        if isPrime[i]:
            for j in range(i * i, n + 1, i):
                isPrime[j] = False
    return isPrime
P = makePrimeChecker(n)
i = 0
ans = 0
for j in A:
    if i == j:
        continue
    else:
        i = j
        if P[i]:
            if d[i] == 0:
                ans += 1
print(ans)

Submission status: Runtime Error

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

for i in range(1, n):
    # print('\n#i:', i)
    for j in range(i//2+1):
        # print('#j:', j)
        # print(a[i], a[j])
        if a[i] % a[j] == 0:
            ans += 1
            break

# print(a)
# print('anti ans:', ans)
print(n - ans)

Submission status: Runtime Error

Solution code:
import numpy as np

N = int(input())
x_list = np.array(list(map(int, input().split())), reverse=True)

count = 0
for xi in x_list:
  if np.sum(xi%x_list==0) == 1:
      count += 1
print(count)

Submission status: Runtime Error

Solution code:
a=int(input())
b=[int(x) for x in input().split()]
b=sorted(b)
c=0
if b[0] == b[1]:
  c+=1
for i in range(0, a):
  for j in range(0, i):
    if b[i] % b[j] == 0:
      c+=1
      break
print(a-c)

Submission status: Runtime Error

Solution code:
import bisect

N = int(input())
a = list(map(int, input().split()))
yaku = [[] for _ in range(N)]
for i in range(N):
    for j in range(1, int(a[i] ** 0.5) + 1):
        if a[i] % j == 0:
            yaku[i].append(j)
            if j != a[i] // j:
                yaku[i].append(a[i]//j)
asort = sorted(a)
cnt = 0
for i in range(N):
    cntF = True
    for j in yaku[i]:
        tmp = bisect.bisect_right(asort, j)
        if tmp == 0:
            continue
        if tmp == N:
            tmp -= 1
        if j != asort[tmp - 1]:
            continue
        if a[i] % asort[tmp - 1] == 0:
            if a[i] == asort[tmp - 1]:
                if a[tmp - 1] == a[tmp - 2]:
                    cntF = False
                    break
                else:
                    continue
            else:
                cntF = False
                break
    if cntF:
        cnt += 1

print(cnt)

Submission status: Runtime Error

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

A.sort()
Al = A[N-1]
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])
    A = B
    if len(A)==0:
        break
    
    if A[0] == Al:
        break
    
if len(A)>0:
    print(len(A))
else:
    print(0)

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 = 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:
n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=0
for i in range(1,a[-1]+1):
    if a.count(i)>=2:
        ans+=1
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)-ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = sorted(list(map(int, input().split())))
ans = 0
if A[0] != A[1]:
    ans += 1
for i in range(1, N):
    tmp = 0
    for j in range(i):
        if A[i] % A[j] == 0:
            break
        elif A[i] < A[j] * 2:
            ans += 1
            break
        else:
            tmp += 1
    if tmp == j + 1:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
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
p = seachPrimeNum(1000)
def factorization(n):
    arr = []
    temp = n
    for i in p:
        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
n = int(input())
a = list(map(int,input().split()))
a.sort()
ans = 0
for i in range(n-2):
    if a[i] == a[i+1] and a[i+1] != a[i+2]:
        ans -= 1
if a[-1] == a[-2]:
    ans -= 1
for i in range(n):
    a[i] = factorization(a[i])
import collections
d = collections.defaultdict(int)
for i in range(n):
    for j in range(len(a[i])):
        if a[i][j][0] in d:
            break
        ans += 1
        d[a[i][j][0]] = 1
if a[0] == [[1,1]]:
    print(0)
else:
    print(ans)

Submission status: Runtime Error

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


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

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

print(count)

Submission status: Runtime Error

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

if(len(set(a))==1 and len(a)>1):
    print(0)
    exit()

    
a.sort()


#print(a)
i=0
j=1
while(i<=n):
    j=i+1
    if(a[i]*2>a[n]):
        break
    while(j<n):

        if(a[j]%a[i]==0):
            a.pop(j)
            n-=1
            continue
        j+=1

    i+=1
           
#print(a)

print(len(a))

Submission status: Runtime Error

Solution code:
import numpy as np
n=int(input())
a=np.array(list(map(int,input().split())))
ans=0
b=numpy.cumsum(numpy.array(a))
for i in range(n):
    for j in range(n):
      if a[i]%(b[j+1]-b[j])==0 and i!=j:
          break
      if j==n-1:
          ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
a=sorted(a)
ans=0
L=[]
for j in range(n):
    num=a[j]
    same=0
    if j==0:
        if num==a[j+1]:
            same=1
    elif j==n-1:
        if num==a[j-1]:
            same=1
    else:
        if num==a[j-1] or num==a[j+1]:
            same=1
    if same==0:
        ok=0
        for i in range(2,-(int(-(num**0.5)))):
            if num%i==0:
                if i or num//i in L:
                    ok=1
        if ok==0:
            ans += 1
            L.append(num)
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
X = [1]*N
for i in range(N-1):
    for j in range(i+1, N):
        if A[j]%A[i] == 0:
            X[j] = 0
c = 0
for i in range(N):
    c += X[i]
if A[0] == A[1]:
    c -= 1
print(c)

Submission status: Runtime Error

Solution code:
N = int(input())
Nmax = 2*(10**5)+1

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

prime = [0]*Nmax
for i in range(N):
    if prime[A[i]] == 0:
        prime[A[i]] = 1
    else:
        prime[A[i]] = -1

for a in A:
    if prime[a] == 1:
        for q in range(a*2, Nmax, a):
            prime[q] = 0



print(sum(a for a in prime if a == 1))

Submission status: Runtime Error

Solution code:
from collections import Counter

n = int(input())
alist = [int(v) for v in input().split()]
dup_set = {k for k, v in Counter(alist).items() if v >= 2}
alist = sorted(set(alist))
adict = {a: False for a in alist}
a_max = alist[-1]
max_ind = -1

count = 0
if 1 in adict:
    count = 0 if 1 in dup_set else 1
else:
    for a, f in adict.items():
        if f:
            continue
        if a not in dup_set:
            count += 1
        for k in range(a, a_max + 1, a):
            if k in adict:
                adict[k] = True
                if k == a_max:
                    max_ind -= 1
                    a_max = alist[max_ind]

print(count)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)

n = int(input())
a = list(map(int, input().split()))
#n, m = map(int, input().split())
#s = input()
#s,t = input().split()
#
#readline = sys.stdin.readline
#n,m = [int(i) for i in readline().split()]
#ab = [[int(i) for i in readline().split()] for _ in range(n)]

a.sort()

ans = 0

for i in range(n):
    
    x = a[i]

    l = 0; r = n # 二分探索時は探索範囲は取り得る値+-1しておく

    while l+1 < r:
        c = (l+r)//2
        if a[c] < int(x**0.5)+1:
            l = c
        else:
            r = c

    tmp = 1
    for j in range(c+1):
        if i != j and x%a[j] == 0:
            break
    else:
        ans += tmp

print(ans)