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

ans = 0

for i in range(N):
    tmp = True
    if A[i] != A[i-1] & A[i] != A[i+1]:
        for j in range(i):
            if A[i] % A[j] == 0:
                tmp = False
                break
    else: 
        tmp = False
    if tmp: 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(n):
  for j in range(i+2):
    if i != j:
      if a[i] % a[j] == 0:
        break
  else:
    ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
import collections

N = int(input())
A = list(map(int,input().split()))
A = sorted(A)
List = []
Count = 0
if(A[0] == A[1]):
    Count -= 1
for i in A:
    List.append(i)
    List2 = map(lambda x: i % x,List)
    c = collections.Counter(List2)
    if(c[0] == 1):
        Count += 1

print(str(Count))

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
import numpy as np
B=np.array(A*N).reshape(N,N).T%np.array(A)
count=0
for i in range(N):
    if np.sum(B[i]==0)==1:
        count +=1
print(count)

Submission status: Runtime Error

Solution code:
import math

def prime(x):
    if x==1:
        prime=True
        #この問題に合わせて１でもTrueとする
    else:
        prime=True
        for i in range(2,int(math.sqrt(x)+1)):
            if x%i==0:
                prime=False
                break
    return prime

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

    A.sort(reverse=True)
    
    #割り切れた場合+1
    cnt=0
    for i in range(N-1):
        #A[i]が素数または1の場合
        if prime(A[i]):
            #前後に同じ数がない場合、割り切れない
            if i<N-1:
                if A[i]==A[i+1]:
                    cnt+=1
            elif i>0:
                if A[i]==A[i-1]:
                    cnt+=1
        #A[i]が素数ではない場合
        else:
            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)

if __name__=="__main__":
    main()

Submission status: Runtime Error

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

ans = 0
  
while True:
  d = A.pop(0)
  if A[0] == d:
    d = A.pop(0)
  else:
    A = list(reversed([ a for a in A[::-1] if a % d != 0]))
    ans += 1
  if A:
    True
  else:
    break
  
print(ans)

Submission status: Runtime Error

Solution code:
from sys import exit

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

count=N

if 1 in A:
  if A.count(1)>1:
    print(0)
  else:
    print(1)
  exit()

for i in range(N):
  n=A[i]
  B=A.copy()
  B.pop(i)
  for j in range(1,max(B)):
    if n % j == 0:
      if j in B:#count
        #print(n,j)
        count-=1
        break
      if j != n // j:
        if n//j in B:#count
          #print(n,n//j,"//")
          count-=1
          break

print(count)

Submission status: Runtime Error

Solution code:
import sys
#sys.exit()
#sorted( ,reverse=True)
N = int(input())
#S,T = map(int, input().split())
A = list(map(int, input().split()))
#A = [int(input()) for _ in range(N)]
A1 = sorted(A,reverse=True)
#print(A1)
cnt = 0
if A1[-1] == A1[-2]:
    cnt -= 1
for i in range(N):
    a = i+1
    while a < N:
        #print(A1[i],A1[a])
        if A1[i]%A1[a] == 0:
            break
        a += 1
    else:
        cnt += 1
    #print(cnt,i,a)
print(cnt)
#cnt = 0
#cnt += 1



#print(N)
#print(S,T)
#print(A)
#print('Yes')
#print('No')
#print(cnt)

Submission status: Runtime Error

Solution code:
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

N = int(input())
A_list = sorted(list(map(int, input().split())), reverse = True)

ans = 0

for i, a in enumerate(A_list):
    if i < N - 1:
        di_list = make_divisors(a)
        search = A_list[i + 1:]
        if len(set(di_list + search)) == len(di_list + search):
 
            ans += 1
if A_list[0] != A_list[1]:
    ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
An = [int(_) for _ in input().split()]
An.sort()
An = list(set(An))
N = len(An)

ans = 0

# 割り切れるものの数を数える
def dfs(An):
    global ans
    if(len(An) == 0):
        return
    val = An.pop(-1)
    for i in An:
        # 割り切れる場合はansに数を足して今のループを抜ける
        if(val % i == 0):
            ans += 1
            break
    # どの数でも割り切れなかった場合は一度抜ける
    dfs(An)

dfs(An)
if(N == 1):
    last_ans = 0
else:
    last_ans = N - ans

print(last_ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = sorted(list(map(int,input().split())))
B = A.copy()
C = []

for i in range(N):
  b = B[0]
  B = [i for i in B[1:] if i % b != 0]
  #print(B)
  if len(B) == 0:
    if A[-2] != b:
      C.append(b)
    break
  if b not in B:
    C.append(b)
  #print(b)
  
print(len(C))

Submission status: Runtime Error

Solution code:
import numpy as np

n=int(input())
a = np.array(list(map(int, input().split())))
ans=0
b=[0]
b.append(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=[]
if A[0]!=A[1]:
    a.append(A[0])
if A[n-2]!=A[n-1]:
    a.append(A[n-1])
for i in range(1,n-1):
    if A[i]!=A[i+1] and A[i]!=A[i-1]:
        a.append(A[i])

a=sorted(a)
n=len(a)
ans=0
for i in range(n):
    num=a[i]
    ok=0
    l=min(i,-(int(-(n**0.5))))
    for j in range(l):
        if a[i]%a[j]==0:
            ok=1
    if ok==0:
        ans += 1
print(ans)

Submission status: Runtime Error

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

a.sort()
if a[0] == a[1]:
    cnt = 0

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

print(cnt)

Submission status: Runtime Error

Solution code:
import sympy
n = int(input());
a = list(map(int,input().split()));
    
b = max(a);
c = min(a);
result = 0;

for p in range(c,b+1):
    d = a.count(p);
                
    if d == 1:
        pp = sympy.divisors(p);
        qq = len(pp);
        rr = 0;
        for q in range(qq-1):
            if a.count(pp[q]) >= 1:
                rr = 1;
                break;
        if rr == 0:
            result += 1;
        
print(result);

Submission status: Runtime Error

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

def seachPrimeNum(N):
    max = int(math.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

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

cnt = 0
prime = seachPrimeNum(max(a))
new_a = [[i,a[i]] for i in range(n)]
for i in range(n-1):
    if a[i] in prime:
        if a.count(a[i]) > 1:
            new_a.remove([i,a[i]])
            cnt += 1
        continue
    for j in new_a:
        if i == j[0]:
            continue
        else:
            if a[i]%j[1] == 0:
                new_a.remove([i,a[i]])
                cnt += 1
                break

x = a.pop()
for j in a:
    if x % j == 0:
        cnt += 1
        break

print(n-cnt)

Submission status: Runtime Error

Solution code:
s = list(map(int,input().split()))
t = s.pop(0)
s.sort()
c = 1
d = 0
for i in range(t):
  for k in range(0,i):
    if s[i]%s[k]==0:
      c = 0
      break
  if c == 1:
    d = d+1
print(d)

Submission status: Runtime Error

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

while(A):
  a = A.pop(0)
  if a in A:
    A = [i for i in A if i!=a]
  else:
    results.append(a)
  A = [i for i in A if i%a!=0]
  if A[-1]<a*2:
    results.extend(A)
    break
print(len(results))

Submission status: Runtime Error

Solution code:
import sys
import time
#from collections import deque, Counter, defaultdict
#from fractions import gcd
#import bisect
#import heapq
import math
start=time.time()
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
inf = 10**18
MOD = 1000000007
ri = lambda : int(input())
rs = lambda : input().strip()
rl = lambda : list(map(int, input().split()))
n = rl()
a=rl()
a.sort()
b=[]
ans=[0]*2*10**5
for i in a:
    if len(b)==0:
        b.append(i)
        ans[i]=1
        continue
    flag=True
    for j in b:
        if i==j:
            ans[i]=0
        if i%j==0:
            flag=False
    if flag:
        b.append(i)
        ans[i]=1

print(sum(ans))

Submission status: Runtime Error

Solution code:
import sympy
n = int(input());
a = list(map(int,input().split()));
    
b = max(a);
c = min(a);
result = 0;

for p in range(c,b+1):
    d = a.count(p);
                
    if d == 1:
        pp = sympy.divisors(p);
        print(pp);
        qq = len(pp);
        rr = 0;
        for q in range(qq-1):
            if a.count(pp[q]) >= 1:
                rr = 1;
                break;
        if rr == 0:
            result += 1;
        
print(result);

Submission status: Runtime Error

Solution code:
n = int(input())

from collections import defaultdict

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

d = defaultdict(int)

for el in a:
    d[el] += 1

count = 0

d = sorted(d.items(), reverse=True)

m = max(d, key=lambda x: x[0])

while len(d):
    a, c = d.pop()
    if c == 1:
        count += 1
    if a == 1:
        break
    if a * a <= m:
        d = [elm for elm in d if elm[0] % a]

print(count)

Submission status: Runtime Error

Solution code:
import math
N= int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
prod = math.prod(A)

count = 0

for i in range(N):
    qualify = 1

    if i > 1 and A[i - 1] == A[i]:
        continue

    if prod/A[i] % A[i] != 0:
        continue

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


    count += qualify


print(count)

Submission status: Runtime Error

Solution code:
import sys

from numba import njit

import numpy as np

readline = sys.stdin.buffer.readline

@njit('i8(i8[:])', cache=True)
def solver(A):
    c = 0
    while True:
        if len(A) < 1:
            break
        a = A[0]
        A = A[A % a != 0]
        c += 1
    return c


def main():
    N = int(readline())
    A = np.array(list(map(int, readline().split())))

    u, counts = np.unique(A, return_counts=True)

    if 1 not in counts:
        print(0)
        sys.exit()

    A = A[counts == 1]

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


    c = solver(np.sort(A))
    print(c)

main()

Submission status: Runtime Error

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

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

a.sort(reverse = True)
p = 0

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

print(p+1)

Submission status: Runtime Error

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

sys.setrecursionlimit(10 ** 6)

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

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

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

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

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

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

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

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


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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict,deque
from sys import stdin,setrecursionlimit
import heapq,bisect,math,itertools,string,queue,datetime,copy
setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, stdin.readline().split()))

N = int(input())
Als = inpl()

Als.sort()

"""def era(ls):#sort済み
    result = []
    while len(ls)>=1:
        a = ls[0]
        f = False
        for item in ls[1:]:
            if item%a==0:
                ls.remove(item)
        result.append(a)
    print(len(result))"""

def era(ls):
    result = []
    while len(ls)>=1:
        a = ls[0]
        ls = ls[1:]
        f = False
        for item in ls:
            if item==a:
                f = True
            if item%a==0:
                ls.remove(item)
        if not f:
            result.append(a)

    print(len(result))

era(Als)
from collections import defaultdict,deque
from sys import stdin,setrecursionlimit
import heapq,bisect,math,itertools,string,queue,datetime,copy
setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, stdin.readline().split()))

N = int(input())
Als = inpl()

Als.sort()

def era(ls):
    result = []
    while len(ls)>=1:
        a = ls[0]
        ls = ls[1:]
        f = False
        for item in ls:
            if item==a:
                f = True
            if item%a==0:
                ls.remove(item)
        if not f:
            result.append(a)

    print(len(result))

era(Als)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from collections import defaultdict

n = int(input())
As  = list(map(int, input().split()))
if n == 1:
    print(0)
    exit()

Ss = sorted(As)
primes = set()
cnt = 0
d = defaultdict(int)
As = [False] * 10**6
for s in Ss:
    d[s] += 1
    if d[s] == 2:
        As[s] = True
# print(Ss)
for s in set(Ss):
    if As[s]: continue
    else:
        cnt += 1
        ind = 1
        while s * ind < 10**6:
            As[s*ind] = True
            ind += 1
print(cnt)

Submission status: Runtime Error

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

a = list(set(a))
if len(a) <= 1:
    print(0)
    exit()
a.sort()
ans = []
for i in range(n):
    flg = True
    for j in range(i):
        if i == j: continue
        if a[i] % a[j] == 0:
            flg = False
    if flg:
        ans.append(i)
print(len(ans))

Submission status: Runtime Error

Solution code:
import sympy

def binary_search(li, k):
    if not li:
        return False
    
    l = 0
    r = len(li) - 1
    
    while True:
        c = (l+r) // 2
        if li[c] == k:
            return True
        elif li[c] < k:
            l = c + 1
        else:
            r = c - 1
        if l > r:
            break
    return False


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

for i in range(len(a)):
    divs = sympy.divisors(a[i])
    for j in divs:
        if binary_search(a[:i], j):
            times += 1
            break
        elif i < len(a) - 1:
            if binary_search(a[i+1:], j):
                times += 1
                break
            
print(n-times)

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()
    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]
    tt = list(lis)
    ans = 0
    while tt.__len__():
        ans += 1
        newlis = []
        f = tt[0]
        for t in tt:
            if t % f != 0:
                newlis.append(t)
        tt = newlis
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

for i in range(n):
    for j in range(n):
        if a[-j] % a[i] == 0:

"""
n = int(input())
a = list(map(int, input().split()))
x = [x for x in set(a) if a.count(x) > 1]
a = list(set(a))
ans = 0


if len(a) == 1 and len(x) > 0:
    ans = 0
else:
    for i in range(n):
        count = 0
        for j in range(n):
            if a[i] % a[j] == 0:
                count += 1
            if count > 1:
                break
        if a[j] in x:
            break
        if count == 1:
            ans += 1

print(ans)

Submission status: Runtime Error

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

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]

ans = 0
temp = [0]*(10**6+3)
temp[A[0]] += 1
if A[0]!=A[1]:
    ans += 1


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

    if check == 0:
        ans += 1
        temp[A[i]]+=1
        
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 = input().split()
A = [int(s) for s in A]
list.sort(A)

count = 0

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

            
if A[0] == A[1]:
    count += 1

print(N-count)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>

using namespace std;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);

  int N;
  cin >> N;

  vector<int> A(N, 0);
  for (int i = 0; i < N; ++i) {
    cin >> A.at(i);
  }

  std::sort(A.begin(), A.end() );

  vector<int> flags(N, 1);
  for (int i = 0; i < N-1; ++i) {
    if (flags.at(i) == 0) {
      continue;
    }
    for (int j = i+1; j < N; ++j) {
      if (A[j] % A[i] == 0) {
        flags[j] = 0;
        if (A[j] == A[i]) {
          flags[i] = 0;
        }
      }
    }
  }


  int sum = 0;
  for (auto i : flags) {
    sum += i;
  }
  cout << sum << endl;
}

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 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 d == 0:
      b.append(a[i])

print(len(b))
#print(b)

Submission status: Runtime Error

Solution code:
n=int(input())
arr=list(map(int,input().split()))
arr.sort()
d={}
ans=0
s1=0
d={i:0 for i in range(1,10**6)}
for i in arr:
    if i==1:
        s1+=1
    d[i]+=1
if s1!=0:
    if s1>1:
        print(0)
        quit()
    else:
        print(1)
        quit()
for i in range(n):
    x=arr[i]
    if d[x]==1:
        f=1
        for j in range(2,int(x**0.5)+1):
            y=x//j
            if (d[j]>=1 and x%j==0) or ( d[y]>=1 and x%(y)==0):
                f=0
                break
        if f==1:
             ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
import copy
import sys
input = sys.stdin.readline
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

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

cnt = 0
prime = seachPrimeNum(max(a))
new_a = [[i,a[i]] for i in range(n)]
for i in range(n-1):
    if a[i] in prime:
        if a.count(a[i]) > 1:
            new_a.remove([i,a[i]])
            cnt += 1
        continue
    for j in new_a:
        if i == j[0]:
            continue
        else:
            if a[i]%j[1] == 0:
                new_a.remove([i,a[i]])
                cnt += 1
                break

x = a.pop()
for j in a:
    if x % j == 0:
        cnt += 1
        break

print(n-cnt)

Submission status: Runtime Error

Solution code:
from math import gcd

N = int(input())
A = sorted(list(map(int, input().split())))
memo = {A[0]:None}
ans = 0

gcd_check = A[0]

for a in A[1:]:
    gcd_result = gcd(gcd_check, a)
    if gcd_result == 1:
        ans += 1
        memo[a] = None
        gcd_check *= a
    elif not gcd_result in memo:
        if gcd_result != a:
            ans += 1
            memo[a] = None
            gcd_check *= a
        else:
            memo[a] = None
    else:
        continue

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

print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter

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

out = 0

for A in As:
    exists[A] = True

for A1, num in counter.items():
    try:

        if num >= 2:
            continue
        
        exist = False

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

        if not exist:
            out += 1
    except:
        pass

print(out)

Submission status: Runtime Error

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

checked = [0] * n
cnt = 0
if a[0] % a[1] == 0:
    cnt += 1

for i in range(n):
    if checked[i] == 1:
        cnt += 1
        continue
    for j in range(i+1,n):
        if a[j] % a[i] == 0:
            checked[j] = 1

print(n - cnt)

Submission status: Runtime Error

Solution code:
s = list(map(int,input().split()))
t = s.pop(0)
s.sort()
s.reverse()
c = 1
d = 1
for i in range(t):
  for k in range(i+1,t):
    if s[i]%s[k]==0:
      c = 0
      break
  if c == 1:
    d = d+1
print(d)

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


daburi = {}
for i in range(1,N):
    if b[i] == b[i-1]:
        daburi.add(b[i])


i = 0
while len(x) > 0 :
    tmp = b[i]
    for j in range(2,10**5+3):
        c = tmp* j
        if c in x:
            x.discard(c)
        if b[-1] <= c:
            break
    if len(x) == i:
        break
    i+=1
        

print(len(x)- len(daburi))

Submission status: Runtime Error

Solution code:
import copy

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

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]


divisors_list = {}
for i in range(1,1000000):
  divisors_list[i] = []

for k,i in enumerate(A):
  for j in make_divisors(i):
    divisors_list[j].append(k)

pass_li = {}
for i in range(N):
  pass_li[i] = 1

for i in range(N):
  tmp = pass_li[i]
  for j in divisors_list[A[i]]:
    pass_li[j] = 0
  pass_li[i] = tmp 
  
  
  
  
print(sum(pass_li.values()))

Submission status: Runtime Error

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

a = list(set(a))
if len(a) <= 1:
    print(0)
    exit()
ans = []

for i in range(n):
    flg = True
    for j in range(n):
        if i == j: continue
        if a[i] % a[j] == 0:
            flg = False
    if flg:
        ans.append(i)
print(len(ans))

Submission status: Runtime Error

Solution code:
from collections import Counter
import sympy


len_arr = int(input())
arr = list(map(int, input().split()))
counter = Counter(arr)
st = set(arr)

ans = 0
for value, count in counter.items():
    if count > 1:
        continue
    divs = set(sympy.divisors(value))
    if len(divs & st) == 1:
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
arr=list(map(int,input().split()))
arr.sort()
d={}
ans=0
s1=0
d={i:0 for i in range(1,10**6)}
for i in arr:
    if i==1:
        s1+=1
        d[i]+=1
if s1!=0:
    if s1>1:
        print(0)
        quit()
    else:
        print(1)
        quit()
for i in range(n):
    x=arr[i]
    if d[x]==1:
        f=1
        for j in range(2,int(x**0.5)+1):
            y=x//j
            if (d[j]>=1 and x%j==0) or ( d[y]>=1 and x%(y)==0):
                f=0
                break
        if f==1:
             ans+=1
print(ans)