Problem:


Score : 400 points

Problem Statement

Given is a number sequence A of length N.

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

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

Constraints

All values in input are integers.

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

1 \leq A_i \leq 10^6

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answer.

Sample Input 1

5
24 11 8 3 16

Sample Output 1

3

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

Sample Input 2

4
5 5 5 5

Sample Output 2

0

Note that there can be multiple equal numbers.

Sample Input 3

10
33 18 45 28 8 19 89 86 2 4

Sample Output 3

5



Sample input:
5
24 11 8 3 16


Sample output:
3

Submission status: Runtime Error

Solution code:
n = int(input())
a= list(map(int,input().split()))
count=set()
for i in range(n):
  	flag=0
	for j in range(n):
    	if i!=j:
    		if a[j]%a[i]==0:
		 		flag=1
	if flag==0:count.add(i) 
    
print(len(count))

Submission status: Runtime Error

Solution code:
N = int(input())
List = list(map(int, input().split()))
res = 0
List.sort()
K = List[N-1]+1
Flag = [1]*K
for i in range(N):
  if Flag[List[i]] ==1:
    res +=1
    for j in range(List[i],K,List[i]):
      Flag[j] = 0
    if List[i] == List[i+1]:
      res += -1
print(res)

Submission status: Runtime Error

Solution code:
import numpy as np
n,*a=map(int,open(0).read().split())
a=np.array(sorted(a))
i = 0
while len(a):
    if a[0] != a[1]:
        i+=1
    a = a[a%a[0] != 0]
print(i)

Submission status: Runtime Error

Solution code:
def run(n, num_array):
    '''
    '''
    # results = []
    # array_len = len(num_array)
    #   table = [](l(array_len)
    #   w if len([j for j in range(array_len) if j != i and num_array[i]%num_array[j] == 0]0: # i:
    #         continueが n の約数である場合、 n/i も n の約数
    #     results.append(i+1)
    
    # print(len(results))

    def divisor(n):
        i = 1
        table = []
        while i * i <= n:
            if n%i == 0: # i が n の約数である場合、 n/i も n の約数
                table.append(i)
                table.append(n//i)
            i += 1
        return set(table)
    
    count = 0
    for i in range(len(num_array)):
        _list = copy.deepcopy(num_array)
        del _list[i]
        if len(divisor(num_array[i]) & set(_list)) >= 1:
            continue
        count += 1

    print(count)

if __name__ == "__main__":
    n = int(input())
    num_array = list(map(int, input().split()))
    run(n, num_array)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Jun 20 16:25:37 2020

@author: naoki
"""
import math

N = int(input()) # the number of integers
A = list(map(int,input().split())) # the row of integers
A.sort() # sorting the contents of the row from small numbers 
dest = int(math.sqrt(A[N-1])) # the range of calculation
prime_list = []
"""
# the smallest number is not divided by any numbers in the row except for the same number 
for i in range(N): # the divided number
    k=0
    while  (A[i] % A[k] != 0 or k == i) and k<=min(i+1,N-1): # if divisible, drop out the loop                  
        if k==min(i+1,N-1):
            count+=1
            break
        else:
            k+=1
"""
j = 0 
while True:
    if j>= len(A):
        break
    elif A[j] == A[j+1]: 
        A.pop(j)
        A.pop(j)
    
i = 0 
while True:
    if i >= len(A):
        break
    elif A[i] % A[0] == 0:
        A.pop(i) # 
        i+=1
    
print(len(A))

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
A = list(set(A))
A = sorted(A, reverse=True)
#print(A)
if len(A) == 1:
  ans = 0
else:
  del_term = []
  for i in range(N):
    for j in range(i+1, N):
#      print(A[i], A[j])
      a = A[i] % A[j]
      if a == 0:
        del_term.append(A[i])
        break
#  print(del_term)
  ans = N - len(del_term)
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from collections import Counter
N = int(input())
A = list(map(int, input().split())) 
ans = set(A)
watched = set()
for k, v in Counter(A).items():
    if v != 1:
        ans.remove(k)
    temp = {k*i for i in range(2,10**6//k + 1)}
    ans -= ans&temp
print(len(ans))

Submission status: Runtime Error

Solution code:
x = int(input())
y = list(map(int, input().split()))

y.sort()
remove = []
ans = []

while y[len(y)-1] / y[0] > 2:
    for i in range(1,len(y)):
        if y[i] % y[0] == 0:
            remove.append(y[i])
    if len(y)>1 and y[0] == y[1]:
        remove.append(y[0])
    else:
        ans.append(y.pop(0))
    while len(remove) != 0:
        y.remove(remove.pop(0))
        print(remove)
    
print(len(ans) + len(y))

Submission status: Runtime Error

Solution code:
# coding: utf-8
import copy
N=int(input())
A=list(map(int,input().split()))
A.sort()
n=max(A)
cnt=0

while A[0]*2<=n:
    p=A[0]
    tmp=[]
    flg=True
    for i in range(1,len(A)):
        if A[i]%p!=0:
            tmp.append(A[i])
        if p==A[i]:
            flg=False
    if flg:
        cnt+=1
    A=copy.deepcopy(tmp)


print(len(A)+cnt)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

for i in range(N):
  for j in range(N):
    if i == j:
      continue
    elif A[i] % A[j] == 0:
      K =+ 1

print(K)

Submission status: Runtime Error

Solution code:
N = int(input())
nums = [i for i in map(int, input().split())]
nums = sorted(nums)
first_num = nums[0]
branch_point = int(nums[-1]/2)
target_index = 0
target_num=0
answer=[]
first_flag=0
duplicate = [x for x in set(nums) if nums.count(x)>1]
while target_num<branch_point:
    target_num = nums[target_index]
    # if target_num == nums[target_index+1]:

    nums = [num for num in nums if num%target_num !=0]
    nums.append(target_num)
    if first_flag==1 and target_num ==first_num:
        break
    if first_flag==0:
        first_flag=1

for dup in duplicate:
    nums.remove(dup)

print(len(nums))

Submission status: Runtime Error

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

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
N = I()
A = readInts()
import collections
dic = collections.Counter(A)
A = set(A)
is_prime = [True] * (2*10**5+1)
for a in A:
    if is_prime[a]:
        for v in range(a*2,2*10**5+1,a):
            is_prime[v] = False
cnt = 0
for a in A:
    if is_prime[a]:
        cnt += 1
for k,v in dic.items():
    if v >= 2 and is_prime[k]:
        cnt -= 1
print(cnt)

Submission status: Runtime Error

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

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
N = I()
A = readInts()
import collections
dic = collections.Counter(A)
A = set(A)
is_prime = [True] * (2*10**5+1)
for a in A:
    if is_prime[a]:
        for v in range(a*2,2*10**5+1,a):
            is_prime[v] = False
cnt = 0
for a in A:
    if is_prime[a]:
        cnt += 1
for k,v in dic.items():
    if v >= 2 and is_prime[k]:
        cnt -= 1
print(cnt)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    N=int(input())
    A=sorted(list(map(int,input().split())))

    l=[0]*(10**6+1)

    for i in A:
        if l[i+1]!=0:
            l[i+1]+=1
            continue
        for j in range(1,10**6//i):
            l[j*i+1]+=1
    
    cnt=0
    for i in A:
        if l[i+1]<=1:
            cnt+=1
    print(cnt)




    
resolve()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    N=int(input())
    A=sorted(list(map(int,input().split())))

    l=[0]*(10**6+1)

    for i in A:
        for j in range(1,10**6//i):
            l[j*i+1]+=1
    
    cnt=0
    for i in A:
        if l[i+1]<=1:
            cnt+=1
    print(cnt)




    
resolve()

Submission status: Runtime Error

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

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

print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(4100000)

import math

import logging

logging.basicConfig(level=logging.DEBUG)

logger = logging.getLogger(__name__)

import numpy as np


def resolve():
    # S = [x for x in sys.stdin.readline().split()][0]  # 文字列 一つ
    N = [int(x) for x in sys.stdin.readline().split()][0]  # int 一つ
    # N, D = [int(x) for x in sys.stdin.readline().split()]  # 複数int
    a_list = [int(x) for x in sys.stdin.readline().split()]  # 複数int

    # grid = [list(sys.stdin.readline().split()[0]) for _ in range(N)]  # 文字列grid
    # v_list = [int(sys.stdin.readline().split()[0]) for _ in range(N)]
    # grid = [[int(x) for x in sys.stdin.readline().split()]
    #         for _ in range(N)]  # int grid

    logger.debug('{}'.format([]))

    MAX = 10**6
    count_list = np.array([0 for _ in range(1, MAX + 1)])
    for a in a_list:
        count_list[a] += 1

    for i in range(1, int(np.floor(np.sqrt(MAX))) + 1):
        if count_list[i]:
            count_list[i * 2::i] = 0
            if count_list[i] >= 2:
                count_list[i] = 0

    print(count_list.sum())


if __name__ == "__main__":
    resolve()

# AtCoder Unit Test で自動生成できる, 最後のunittest.main は消す
# python -m unittest template/template.py で実行できる
# pypy3 -m unittest template/template.py で実行できる

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """5
24 11 8 3 16"""
        output = """3"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """4
5 5 5 5"""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """10
33 18 45 28 8 19 89 86 2 4"""
        output = """5"""
        self.assertIO(input, output)

Submission status: Runtime Error

Solution code:
import math
input = lambda: sys.stdin.readline().rstrip()
n = int(input())
ai = [int(i) for i in input().split()]

num_li = [0]*(10**6+1)


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



for i in range(n):
    num_li[ai[i]] += 1

ans = 0
    
for i in range(n):
    if num_li[ai[i]] > 1:
        continue
    #print(ai[i])
    flag = True
    div = make_divisors(ai[i])
    #print(div)
    for j in range(len(div)):
        if div[j] == ai[i]:
            continue
        #print(div[j],div)
        if num_li[div[j]] > 0:
            flag = False
            break
    if flag == True:
        ans += 1
    #exit()
print(ans)

Submission status: Runtime Error

Solution code:
import sys
n = int(sys.stdin.readline().rstrip("\n"))
a = [int(s) for s in sys.stdin.readline().rstrip("\n").split()]
a.sort()
a_true = [True]*n
a_set = set(a)
if 1 in a or len(a_set) == 1:
    print(0)
else:
    a_max = a[n-1]
    i = 0
    while a[i]*2 <= a_max:
        while i < n-1:
            if a[i] == a[i+1]:
                a_true[i] = False
                a_true[i+1] = False
            i += 1
        for j in range(i+1,n):
            if a[j] % a[i] == 0:
                a_true[j] = False
        i += 1
    while i < n-1:
        if a[i] == a[i+1]:
            a_true[i] = False
            a_true[i+1] = False
        i += 1
    print(len([i for i in range(0, n) if a_true[i]]))

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
f=[1]*(2*10**5+10)
from collections import Counter
c=Counter(a)
ans=0
for ai in a:
  if c[ai]==1 and f[ai]==1:ans+=1
  for i in range(ai,2*10**5,ai):
    f[i]=0
print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
f=[1]*(2*10**5+1)
from collections import Counter
c=Counter(a)
ans=0
for ai in a:
  if c[ai]==1 and f[ai]==1:ans+=1
  for i in range(ai,2*10**5,ai):
    f[i]=0
print(ans)

Submission status: Runtime Error

Solution code:
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
lis=LI()
m=2*(10**5)+1
dp=[0 for i in range(m)]
#print(dp)
for i in range(n):
    x=lis[i]
    #print(x)
    for j in range(2,((m-1)//x)+1):
        dp[x*j]=1
        #print(x*j)
#print(dp)
ans=0
c=Counter(lis)
for y in lis:
    if c[y]<=1:
        ans+=1-dp[y]
print(ans)
#print(dp)
#print(dp[2*(10**5)])

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))
C = {}
for i in range(N):
    a = A[i]
    if a not in C:
        C[a] = 0
    C[a] += 1
A = []
for a in C:
    if C[a]==1:
        A.append(a)
if len(A)==0:
    print(0)
else:
    A = sorted(A)
    amax = A[-1]
    P = [0 for _ in range(amax+1)]
    for i in range(N):
        P[A[i]] = 1
    for i in range(N):
        a = A[i]
        for j in range(a*2,amax+1,a):
            P[j] = 0
    print(sum(P))

Submission status: Runtime Error

Solution code:
from math import sqrt
N = int(input())
A = sorted(list(map(int, input().split())))
m = 10**6
dp = [0]*10**6
ans = 0

for a in A:
    for i in range(1, m//a):
        dp[a*i] += 1
for a in A:
    if dp[a] == 1:
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
import sys
from collections import Counter

def ii(): return int(sys.stdin.readline())
def li(): return list(map(int, sys.stdin.readline().split()))

if __name__ == "__main__":
    n = ii()
    a = li()
    c = Counter(a)
    del_list = []
    for k, v in c.items():
        if v >= 2:
            del_list.append(k)
    for k in del_list:
        del c[k]
    a = sorted(c.keys())
    max_a = a[-1]
    if len(a) == 0:
        print(0)
        exit()
    b = [True] * (max_a + 1)
    def sived(x):
        for not_ans in range(x+x, max_a + 1, x):
            b[not_ans] = False
    for i in a:
        if b[i]:
            sived(i)
    ans = 0
    for i in a:
        if b[i]:
            ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
from collections import Counter

def ii(): return int(sys.stdin.readline())
def li(): return list(map(int, sys.stdin.readline().split()))

if __name__ == "__main__":
    n = ii()
    a = li()
    c = Counter(a)
    del_list = []
    for k, v in c.items():
        if v >= 2:
            del_list.append(k)
    for k in del_list:
        del c[k]
    a = sorted(list(c.keys()))
    max_a = a[-1]
    if len(a) == 0:
        print(0)
        exit()
    b = [True] * (max_a + 1)
    def sived(x):
        for not_ans in range(x+x, max_a + 1, x):
            b[not_ans] = False
    for i in a:
        if b[i]:
            sived(i)
    ans = 0
    for i in a:
        if b[i]:
            ans += 1
    print(ans)

Submission status: Runtime Error

Solution code:
def count_sort(arr):
    max_num = max(arr)
    min_num = min(arr)
    count = [0] * (max_num - min_num + 1)
    for ele in arr:
        count[ele - min_num] += 1

    return [ele for ele, cnt in enumerate(count, start=min_num) for __ in range(cnt)]

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

divisible = False
if A_sorted[0] == A_sorted[1]:
  ans = 0
else:
  ans = 1

for i in range(N-1, 0, -1):
  for j in range(0, i):
    if A_sorted[i]%A_sorted[j] == 0:
      divisible = True
      break
  if not divisible:
    ans += 1
  divisible = False


print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
List = list(map(int, input().split()))
res = 0
List.sort()
K = List[N-1]+1
Flag = [1]*K
for i in List:
  if Flag[i] ==1:
    res +=1
    for j in range(i,K,i):
      Flag[j] = 0
    if i == List[List.index(i)+1]:
      res += -1
print(res)

Submission status: Runtime Error

Solution code:
n = int(input())
A = sorted(list(map(int, input().split())))
M = 10**6 + 1
L = [0]*M
ans = 0
for a in A:
    L[a] += 1
    if L[a] == 1:
        # k>=2として k*aは全て不適
        for i in range(2*a, M+1, a):
            L[i] += 2
# flagの数が答え
print(L.count(1))

Submission status: Runtime Error

Solution code:
n = int(input())
A = sorted(list(map(int, input().split())))
M = 2 * 10**5 + 1
L = [0]*M
ans = 0
for a in A:
    L[a] += 1
    if L[a] == 1:
        # k>=2として k*aは全て不適
        for i in range(2*a, M, a):
            L[i] += 2
# flagの数が答え
print(L.count(1))

Submission status: Runtime Error

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

O = A.copy()

for i in A:
    for j in A:
        if i != j:
            if (i%j == 0):
                if i in O:
                    O.remove(i)

ans = len(O)

print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
amax = a[-1]
isok = [True]*(amax+1)
ans = 0

for i in range(n):
    x = a[i]
    if isok[x]:
        if i == 0 and a[i] != a[i+1]:
            ans += 1
        elif i == n-1 and a[i] != a[i-1]:
            ans += 1
        elif a[i] != a[i+1] and a[i] != a[i-1]:
            ans += 1
        orix = x
        while x<=amax:
            isok[x]=False
            x+=orix
print(ans)

Submission status: Runtime Error

Solution code:
def func(n, a):
    mx = max(a)
    x = [0] * (mx + 1) # len(x)
    for i in a:
        x[i] += 1
    for i in range(1, mx + 1):
        if x[i] != 0:
            for j in range(2 * i, mx + 1, i):
                x[j] = 0
        if x[i] > 1:
            x[i] = 0
    return sum(x) # 31401

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

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import itertools
from decimal import *

input = sys.stdin.readline

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N = inputInt()
	A = inputList()

	A.sort()
	refd = [0 for i in range(2*100000 + 1)]
	for i,val in enumerate(A):
		for j in range(val,2*100000 + 1,val):
			if refd[j] >= 2:
				break
			refd[j] += 1

	ans = 0
	for i,val in enumerate(A):
		if refd[val] < 2:
			ans += 1

	print(ans)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import itertools
from decimal import *

input = sys.stdin.readline

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N = inputInt()
	A = inputList()

	A.sort()
	ref = [0 for i in range(4*100000 + 1)]
	for i,val in enumerate(A):
		for j in range(val,2*100000 + 1,val):
			if ref[j] >= 2:
				break
			ref[j] += 1

	ans = 0
	for i,val in enumerate(A):
		if ref[val] < 2:
			ans += 1

	print(ans)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import itertools
from decimal import *

input = sys.stdin.readline

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N = inputInt()
	A = inputList()

	A.sort()
	ref = [0 for i in range(2*100000 + 2)]
	for i,val in enumerate(A):
		for j in range(val,2*100000 + 1,val):
			if ref[j] >= 2:
				break
			ref[j] += 1

	ans = 0
	for i,val in enumerate(A):
		if ref[val] < 2:
			ans += 1

	print(ans)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import itertools
from decimal import *

input = sys.stdin.readline

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N = inputInt()
	A = inputList()

	A.sort()
	ref = [0 for i in range(2*100000 + 1)]
	for i,val in enumerate(A):
		for j in range(val,2*100000 + 1,val):
			if ref[j] >= 2:
				break
			ref[j] += 1

	ans = 0
	for i,val in enumerate(A):
		if ref[val] < 2:
			ans += 1

	print(ans)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()

Submission status: Runtime Error

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

a.sort()


for i in range(n):
    if i == 0:
        if a[i] % a[1] != 0:
                ans += 1
    if i>=1 and a[i] != a[i-1]:
        for j in range(i+1):
            if a[i] % a[j] == 0:
                check += 1
            if check > 2:
                break
        if check == 1:
            ans += 1
        check = 0

print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
A_ = [int(i) for i in input().split(None,n)[:n]]
A = sorted(A)

cand = set()
dup = set()

for a in A:
  if a in cand:
    dup.add(a)
  for c in cand:
    if a % c != 0:
      cand.add(a)
cand -= dup
print(len(cand))

Submission status: Runtime Error

Solution code:
import numpy as np
n = int(input())
a = np.array(list(map(int, input().split())))
ans = 0
 
for i in range(n):
  temp = a[i]
  temp_list = np.array([a[:i]])
  temp_list = np.append(temp_list,a[i+1:])
  
  if np.any(temp%temp_list == 0):
    continue
  else:
    ans += 1
    
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
arr = [int(x) for x in input().split()]
d = {}
for x in arr:
  d[x] = d.get(x,0)+1

mxN = 10**6 + 1
rp = [True]*mxN


for i in range(2,len(rp)):
  if i not in d or not rp[i]:continue
  for j in range(i+i,mxN,i):
    if j in d: rp[j] = False

#reason for tle



for k,v in d.items():
  if v > 1:rp[k] = False

ans = sum([(1 if rp[x] else 0) for x in cset])
print(ans)

Submission status: Runtime Error

Solution code:
# エラトステネスの篩を使う！O(nloglogn)
N = int(input())
A = list(map(int,input().split()))

listA = [0] * 10**6
ans = 0
for i in A:
    for j in range(i,10**6,i):
        if listA[j] == 2:
            continue
        else:
            listA[j] += 1

for i in A:
    if listA[i] == 1:
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
N=int(input())
List=list(map(int,input().split()))
b=[]
q=0
List=sorted(List)
M=List[len(List)-1]/2
while (List[0]<=M and len(List)>1):
    p=List[0]
    for i in range(0,len(List)):
        if List[i]%p!=0:
            b.append(List[i])
    List=b
    b=[]
    q+=1
    M=List[len(List)-1]/2
y=[x for x in set(List) if List.count(x)==1]
q+=len(y)
print(q)

Submission status: Runtime Error

Solution code:
N=int(input())
List=list(map(int,input().split()))
b=[]
q=0
List=sorted(List)
M=List[len(List)-1]/2
while (List[0]<=M and len(List)>1):
    p=List[0]
    for i in range(0,len(List)):
        if List[i]%p!=0:
            b.append(List[i])
    List=b
    b=[]
    q+=1
y=[x for x in set(List) if List.count(x)==1]
q+=len(y)
print(q)

Submission status: Runtime Error

Solution code:
N=int(input())
List=list(map(int,input().split()))
b=[]
q=0
sorted(List)
M=List[len(List)-1]/2
while (List[0]<=M and len(List)>1):
    p=List[0]
    for i in range(0,len(List)):
        if List[i]%p!=0:
            b.append(List[i])
    List=b
    b=[]
    q+=1
y=[x for x in set(List) if List.count(x)==1]
q+=len(y)
print(q)

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
key=max(A)+1 #最大値もrange(a,key,a)で計算させるため
B=[0]*key #0~Aの最大値までのlistを作成
for a in A:
    for b in range(a,key,a):
    B[b]+=1 #aの倍数を全てにBリストで1を足す
ans=0
for a in A:
    if B[a]==1: #自身しか倍数にならなかった物
    ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A_list = list(map(int, input().split()))
M = 2*10**5+1
cnt = [0 for _ in range(M)]

for i in A_list:
    if cnt[i] != 0:
        cnt[i] = 2
        continue
    for j in range(i, M, i): cnt[j] += 1

ans = 0
for k in A_list:
    if cnt[k] == 1: ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
List = list(map(int, input().split()))
res = 0
New_List = sorted(List)
Flag = [1]*N
for i in range(N):
  if Flag[i] ==1:
    for j in range(i+1,N):
      if Flag[j] ==1:
        if New_List[i] == New_List[j]:
          Flag[i] = 0
          Flag[j] = 0
        elif New_List[j] % New_List[i] ==0:
          Flag[j] = 0
        else:
          pass
      elif Flag[j] ==0:
        pass
  else:
    pass
res = Flag.count(1)
print(res)
N = int(input())
List = list(map(int, input().split()))
res = 0
New_List = sorted(List)
Flag = [1]*N
for i in range(N):
  if Flag[i] ==1:
    for j in range(i+1,N):
      if Flag[j] ==1:
        if New_List[i] == New_List[j]:
          Flag[i] = 0
          Flag[j] = 0
        elif New_List[j] % New_List[i] ==0:
          Flag[j] = 0
        else:
          pass
      elif Flag[j] ==0:
        pass
  else:
    pass
res = Flag.count(1)
print(res)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
L = [1] * (max(A) + 1)
ret = 0
dup = list()
for i in range(len(A)):
    if L[A[i]] == 1:
        if A[i] == A[i+1]:
            dup.append(A[i])
            L[A[i]] = 0
        else:
            ret += 1
            num = 2
            while A[i] * num > len(L) - 1 :
                L[A[i] * num] = 0
                num += 1
    
print(ret)

Submission status: Runtime Error

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


l = [0] * max(a)


for i in a:

    c = 2
    while True:
        if i*c-1 >= max(a):
            break
        l[i*c - 1] += 1
        c += 1



ans = 0

for i in set(a):
    if l[i] == 1:
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

N = int(input())
MAXX = 10**6 + 5
num = np.array(input().split(), np.int32)[:]
mark = np.zeros(MAXX, np.int32)

num = np.sort(num)
for n in num:
    if mark[n::n] < 2:
        mark[n::n] += 1

count = 0
for n in num:
    if mark[n] == 1:
        count += 1

print(count)

Submission status: Runtime Error

Solution code:
import numpy as np

n = int(input())
a = [int(x) for x in input().split()]
m = np.zeros(10**6+1, dtype=int)
cnt = 0

for i in a:
    m[::i] += 1
for i in a:
    if m[i] == 1:
        cnt += 1
print(cnt)

Submission status: Runtime Error

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

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

print(count)

Submission status: Runtime Error

Solution code:
import sys

def Not_Divisible(n,p):
    k=0
    for j,b in enumerate(p):
    	for i,a in enumerate(p):
        	if  i != j and a % b == 0:
                k-=1
                break
        k+=1
    return k

if __name__ == '__main__':
    input = sys.stdin.readline
    
    inp1 = input().rstrip().split()
    n = int(inp1[0])

    inp2 = input().rstrip().split()
    p = list(map(int,inp2))
    print(Not_Divisible(n,p))

Submission status: Runtime Error

Solution code:
import sys

def Not_Divisible(n,p):
    k=0
    for i,a in enumerate(p):
        for j,b in enumerate(p):
            if  i != j and a % b == 0:
                k-=1
                break
        k+=1
    return k

if __name__ == '__main__':
    input = sys.stdin.readline
    
    inp1 = input().rstrip().split()
    n = int(inp1[0])

    inp2 = input().rstrip().split()
    p = list(map(int,inp2))
    print(Not_Divisible(n,p)