Problem:


Score : 400 points

Problem Statement

Given is a number sequence A of length N.

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

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

Constraints

All values in input are integers.

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

1 \leq A_i \leq 10^6

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answer.

Sample Input 1

5
24 11 8 3 16

Sample Output 1

3

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

Sample Input 2

4
5 5 5 5

Sample Output 2

0

Note that there can be multiple equal numbers.

Sample Input 3

10
33 18 45 28 8 19 89 86 2 4

Sample Output 3

5



Sample input:
5
24 11 8 3 16


Sample output:
3

Submission status: Runtime Error

Solution code:
import math
from collections import deque
from collections import defaultdict
import itertools as it

#自作関数群
def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	if len(res)==0:
		res = [n]
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):#階乗
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):#コンビネーション
	if n<r:
		return 0
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
def combmod(n,r,mod):
	return (fact(n)/fact(n-r)*pow(fact(r),mod-2,mod))%mod
def printQueue(q):
	r=copyQueue(q)
	ans=[0]*r.qsize()
	for i in range(r.qsize()-1,-1,-1):
		ans[i] = r.get()
	print(ans)
class UnionFind():
	def __init__(self, n):
		self.n = n
		self.parents = [-1]*n

	def find(self, x): # root
		if self.parents[x]<0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self,x,y):
		x = self.find(x)
		y = self.find(y)

		if x==y:
			return

		if self.parents[x]>self.parents[y]:
			x,y = y,x

		self.parents[x]+=self.parents[y]
		self.parents[y]=x

	def size(self,x):
		return -1*self.parents[self.find(x)]

	def same(self,x,y):
		return self.find(x)==self.find(y)

	def members(self,x): # much time
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i)==root]

	def roots(self):
		return [i for i,x in enumerate(self.parents) if x<0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()} # 1~n
def bitArr(n):#ビット全探索
	x = 1
	zero = "0"*n
	ans = []
	ans.append([0]*n)
	for i in range(2**n-1):
		ans.append(list(map(lambda x:int(x),list((zero+bin(x)[2:])[-1*n:]))))
		x+=1
	return ans;
def arrsSum(a1,a2):
	for i in range(len(a1)):
		a1[i]+=a2[i]
	return a1
def maxValue(a,b,v):
	v2 = v
	for i in range(v2,-1,-1):
		for j in range(v2//a+1): #j:aの個数
			k = i-a*j
			if k%b==0:
				return i
	return -1
def copyQueue(q):
	nq = queue.Queue()
	n = q.qsize()
	for i in range(n):
		x = q.get()
		q.put(x)
		nq.put(x)
	return nq
def get_sieve_of_eratosthenes(n):
	data = [2]
	#data = [0,0,0]
	for i in range(3,n+1,2):
		data.append(i)
		data.append(0)
	for i in range(len(data)):
		interval = data[i]
		if interval!=0:
			for j in range(i+interval,n-1,interval):
				data[j] = 0
	ans = [x for x in data if x!=0]
	#ans = data[:]
	return ans

n = readInt()
a = readInts()

a.sort()
maxa = max(a)+1
for i in a:
	if a.count(i)>=2:
		a.remove(i)
		while i in a:
			a.remove(i)

maxa = max(a)+1

ans = [0]*maxa
for i in a:
	ans[i] = 1



for j in a:
	if ans[j]==0:
		pass
	for i in range(j*2,10**6+1,j):
		if i>maxa-1:
			break
		ans[i] = 0

print(ans.count(1))

Submission status: Runtime Error

Solution code:
#import numpy as np
import sys
#from collections import deque
#import copy


def xnxn(n=0, flag="v"):
    """
    args:
        int n: a number of lows to read
    example:
        input   1
        retrun  1

        input   1 2 3
        return  [1,2,3]
        input   1 2 3
                4 
        return  [[1,2,3],
                [4]]
    """
    if n == 0:
        temp = list(map(int, input().split()))
        if len(temp) == 1:
            if flag == "l":
                return temp
            else:
                return temp[0]
        elif len(temp) > 1:
            return temp
    else:
        temp = [list(map(int, input().split())) for _ in range(n)]
        return temp


def sp_xnxn(n=0):
    """
    args:
        int n: a number of lows to read
    example
        input   1
        retrun  [1]

        input   123
        return  [1,2,3]

        input   123
                4 
        return  [[1,2,3],
                [4]]
    """
    if n == 0:
        return [int(k) for k in xsxs()]
    else:
        return [[int(k) for k in xsxs()] for _ in range(n)]


def xsxs(n=0):
    """
    args:
        int n: a number of lows to read 
    example:
        input   AA
        retrun  AA

        input   A BBB CC
        return  ["A","BBB","CC"]

        input   A BB CCC
                D
        return  [["A","BBB","CC"],
                ["D"]]
    """
    if n == 0:
        temp = list(input().split())
        if len(temp) == 1:
            return temp[0]
        elif len(temp) > 1:
            return temp
    else:
        return [list(input().split()) for _ in range(n)]


def sp_xsxs(n=0):
    """
    args:
        int n: a number of lows to read 
        example:
            input   A
            retrun  ["A"]

            input   ABC
            return  ["A","B","C"]

            input   ABC
                    D
            return  [["A","B","C"],
                    ["D"]]
    """
    if n == 0:
        return [s for s in xsxs()]
    else:
        return [[s for s in xsxs()] for _ in range(n)]


# def gcd(a, b):

#     if a < b:
#         a, b = b, a
#     while True:
#         r = a % b
#         if r == 0:
#             return b
#         else:
#             a = b
#             b = r


n = xnxn()
a = xnxn()

a.sort()


dp = [0] * n
dp[0] = 0
so = [a[0]]


for i in range(1, n):
    c = 1
    dp[i] += dp[i-1]
    for k in so:
        if a[i] % k == 0:
            c = 0
            break
    if c == 1:
        dp[i] += 1
        so.append(a[i])

print(dp[n-1])

Submission status: Runtime Error

Solution code:
import numpy as np

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

A_sorted=np.sort(A)
result=[]
a=A_sorted[0]
while A_sorted.size>0:
    a=A_sorted[0]
    if A_sorted.size==1:
        result.append(a)
        break
    A_sorted=A_sorted[1:]
    result.append(a)
    A_sorted=A_sorted[A_sorted%a!=0]
print(len(result))

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
import math
import itertools
import collections

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

A.sort()

prime = set()
pa = set()
ans = 0

for i , a in enumerate(A):
    if a == 1 and A[i+1] != 1:
        print(1)
        sys.exit()
    elif a == 1 and A[i+1] == 1:
        print(0)
        sys.exit()

    if a in pa or a in prime:
        continue

    psf = False
    for i in range(2,int(math.sqrt(a))+1):
        if a % i == 0 :
            j = a // i
            if i in prime or i in pa or j in prime or j in pa:
                psf = True
                break
    if psf is True:
        continue

    if i == N-1:
        ans += 1
    elif A[i] != A[i+1]:
        prime.add(a)
        ans += 1
    else:
        prime.add(a)

print(ans)

Submission status: Runtime Error

Solution code:
import sys
import collections

def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
def TI(): return tuple(map(int,input().split()))
def RN(N): return [input().strip() for i in range(N)]


def main():
    
    N = II()
    A = LI()
    #As = sorted(A, reverse=True)
    As = A.sort(reverse=True)
    ans = N
    c = collections.Counter(As)

    if N == 1:
        print(0)
    elif len(set(A)) == 1:
        print(0)
    elif c[1] != 0:
        if c[1] == 1:
            print(1)
        else:
            print(0)
    else:
        for i in range(N-1):
            k = N-1
            if c[As[i]] >= 2:
                ans -= 1
                if i == N-2:
                    ans -= 1
            else:
                for j in range(N):
                    if k == i:
                        break
                    elif As[i] % As[k] == 0:
                        ans -= 1
                        break

                    k -= 1

        print(ans)


if __name__ == "__main__":
	main()

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
import math
from functools import reduce
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        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 = lcm_list(A)
F = factorization(n)
count = 0
for i,j in F:
  for k in range(j):
    i += i
    if i in A:
      count += 1

print(count)

Submission status: Runtime Error

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

for i in range(n-1):
    if a[i]==a[i+1]:
        b+=1
nl=[]
while 1:
    p=a.pop(a[1])
    for i in a:
        if i%p!=0:
            nl.append(i)
    nl.append(p)
    if len(a)==len(nl):
        print(len(a)-b)
        exit()
    a=nl[::]

Submission status: Runtime Error

Solution code:
def resolve():
    import bisect
    import math
    n = int(input())
    a = list(map(int, input().split()))
    a1 = {}
    for i in range(len(a)):
        if a[i] in a1:
            a1[a[i]] += 1
        else:
            a1[a[i]] = 1
    a = sorted(list(a1.keys()))
    ans = [1]*len(a)

    if len(a) != 1:
        for i in range(len(a)):
            if a[i] > a[-1]/a[0]:
                break
            if ans[i] == 1:
                for j in range(i+1, n):
                    if a[j] % a[i] == 0:
                        ans[j] = 0
    ans1 = 0
    for j in range(len(a)):
        if ans[j] == 1 and a1[a[j]] == 1:
            ans1 += 1
    print(ans1)
resolve()

Submission status: Runtime Error

Solution code:
# D - Not Divisible

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


if a[0]==a[i]:
    b[0]=0
    b[0]=0

b = [1]*n
for i in range(n):
    for j in range(i):
        #print(i,j)
        #print(a[i], "%", a[j] )
        if a[i]==a[j]:
            b[i]=0
            b[j]=0
            break
        elif a[i]%a[j]==0:
            b[i]=0
            break

#---check
#print(b)

print(sum(b))

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())
b = set(list(map(int,input().split())))
total = 0
if len(b)==1:
    print(0)
else:
    for j in range(len(b)):
        f = set(b)-set([b[j]])
        g = set(make_divisors(b[j]))
        if f&g == set():
            total += 1
    print(total)

Submission status: Runtime Error

Solution code:
a=[input() for i in range(2)]
a1=int(a[0])
a2=a[1].split()
p=[int(i) for i in a2]
c=0

for i in range(len(p)):
	mod=[p[i]%p[j] for j in range(len(p)) if i!=j]
	
	if min(mod)!=0:
		c+=1

print(c)

Submission status: Runtime Error

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

a = list(set(a))
a = sorted(a, reverse=True)
ans = 0
count = 0

if len(a) != 1:
    for x in range(0, n-1):
        for y in range(x+1, n):
            if a[x] % a[y] == 0:
                break
            else:
                count += 1

        if count == n - x-1:
            ans += 1
        count = 0
    print(ans + 1)
else:
    print(0)

Submission status: Runtime Error

Solution code:
n=int(input())
A=sorted(map(int,input().split()))
L=[A[0]]
if n==0:
    print(0)
else:
    c=0
    if A[0]!=A[1]:
        c=1
    for i in range(n-1):
        flag=0
        for l in L:
            if A[i+1]%l==0:
                flag=1
                break

        if flag==0:
            L.append(A[i+1])
            c+=1
    print(c)

Submission status: Runtime Error

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

d_num = a

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

Submission status: Runtime Error

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

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

new_num_list = list(set(num_list))
new_num_list.sort()

if len(new_num_list) = 1:
  ans = 0
else:
  ans = 1

count = 0

for index_1, num_1 in enumerate(num_list):
  for index_2, num_2 in enumerate(num_list):
    if index_1 > index_2:
      if num_1 % num_2 != 0:
        count += 1
  
  if count == index_1:
    ans += 1

  count = 0

print(ans)

Submission status: Runtime Error

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

import numpy as npz

ans = 0
for i in range(N):
    if A.count(A[i]) == N:
        ans = 0
        break
        break
    c = list(A[i]%np.array(A))
    if c.count(0) == 1:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
array = list(map(int, input().strip().split()))
array.sort()
ans = N
a = [True] * N
i = 0
for i in range(len(array)):
    j = i + 1
    while j < len(array):
        if (array[j] % array[i] == 0 or array[j] == array[i]):
            array.pop(j)
            ans -= 1
            if j == len(array) -1:
                break
        else:
            j += 1
if (array[len(array)-1] == array[len(array)-2]):
    ans -= 1
if (array[0] == array[1]):
    ans -= 1
print(ans)

Submission status: Runtime Error

Solution code:
def resolve():
    n=int(input())
    a = list(map(int, input().split()))
    a.sort()
    if a[0]==a[-1]:
        print(0)
    else:
        ans=1
        b=[a[0]]
        c=0
        ansm=()
        for i in range(1, n):
            k=a[i]
            for j in b:
                if j==k:
                    ansm.append(j)
                if k%j==0:
                   c=1
                   break
            if c == 0:
                b.append(k)
                ans+=1
            c=0
        print(ans-len(ansm))
resolve()

Submission status: Runtime Error

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

A.sort()
count = 0
B = [0] * (10**6)

for i in range(N):
    B[A[i]] = 1

for i in range(N):
    flag = 1
    X = A[i]
    for j in range(1,int(X**0.5)+1):
        if X % j == 0:
            if B[j] == 1:
                flag = 0
            if (j != X // j) and (j != 1):
                if B[X//j] == 1:
                    flag = 0
    if i != N-1:
        if X == A[i+1]:
            flag = 0
    if i != 0:
        if X == A[i-1]:
            flag = 0

    if flag == 1:
        count += 1

print(count)

Submission status: Runtime Error

Solution code:
N = int(input())
A = sorted(list(map(int, input().split())))
A = [x for x in set(A) if l.count(x) > 1]
if len(A) == 1:
    print(0)
    exit()
B = A
flag == 0
for i in range(N):
    C = []
    flag = 0
    for j in range(len(B)):
        if B[j] == A[i]:
            if flag == 0:
                C.append(B[j])
                flag = 1
        elif B[j] < A[i]:
            C.append(B[j])
        elif B[j] // A[i] != 0 and B[j] % A[i] != 0:
            C.append(B[j])
    B = C

Submission status: Runtime Error

Solution code:
input()
nums = [int(s) for s in input().split(" ")]
nums.sort(reverse=True)
count = 0

for i in range(len(nums) - 1):
    flag = 0
    for j in range(1, len(nums) - i):
        if(nums[i] == nums[i - 1]):
            flag = 1
        print("{0} % {1} = {2}".format(nums[i], nums[i + j], nums[i]%nums[i + j]))
        if nums[i]%nums[i + j] == 0:
            flag = 1
    if flag == 0:
        count = count + 1
if(nums[-1] == nums[-2]):
    print(count)
else:
    print(count + 1)

Submission status: Runtime Error

Solution code:
import sympy
n = int(input())
numlist = sorted(list(map(int,input().split())))

counter = 0
print(numlist)
for i in range(n):
    temp = set(numlist[i+1:])
    divs = set(sympy.divisors(numlist[i]))
    if len(temp-divs) == len(temp):
        counter += 1
print(counter)

Submission status: Runtime Error

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

nums.sort()

if n == 1:
    print(1)
    exit()

if nums[0] == 1:
    print(1)
    exit()

ans_list = [nums[0]]

from sympy import divisors, divisor_count
import bisect

subtract = 0
temp = -1
for i in range(1, n):
    if nums[i] == nums[i-1] and nums[i] != temp:
        subtract += 1
        temp = nums[i]
        continue

    valid = True
    divi = divisors(nums[i])
    for d in divi:
        pos = bisect.bisect_left(ans_list, d)
        if pos < len(ans_list) and ans_list[pos] == d:
            # 割り切れた
            valid = False
            break

    if valid:
        ans_list.append(nums[i])
    
ans = len(ans_list) - subtract

print(ans)
# print(ans_list)

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  for(int i = 0; i < n; i++){
    scanf("%d", &a[i]);
  }
  
  sort(a.begin(), a.end());
  vector<int>::iterator it = a.begin();

  while(1){
    if(++it == a.end()) break;
    for(vector<int>::iterator its = it; its != a.end(); ++its){
      if(*its % *it == 0){
        its = a.erase(its);
      }
    }
    ++it;
  }
  cout << a.size() << endl;
}

Submission status: Runtime Error

Solution code:
#!/usr/bin/env pypy3

from numba import njit


@jit(nopython=True, parallel=True, nogil=True)
def divisors(n):
    res = set()
    for i in range(1, n + 1):
        if i * i > n:
            return res
        d, m = divmod(n, i)
        if m == 0:
            res.add(i)
            res.add(d)
    return res


def count_nondivisors(n, bs):
    ctr = {b: 0 for b in bs}
    for b in bs:
        ctr[b] += 1
    ds = {k: sum(ctr.get(k, 0) for k in divisors(k)) for k in ctr.keys()}
    num_div_elems_table = [ds[bs[i]] for i in range(n)]
    res = sum(num_div_elems_table[i] == 1 for i in range(n))
    return res


def main():
    n = int(input())
    bs = [int(b) for b in input().split()]
    res = count_nondivisors(n, bs)
    print(res)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import heapq as hp
n = int(input())
a = list(map(int, input().split()))
hp.heapify(a)
ans = 0
while len(a) > 0:
    b = hp[0]
    if b in a:
         ans += -1
    a = [i for i in a if i % b != 0]
    ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
from sys import stdin

n = [int(x) for x in stdin.readline().rstrip().split()]
P = [int(x) for x in stdin.readline().rstrip().split()]

rest_lists = []

P.sort()

def return_filtered(div, rl):
    new = []
    protect = True
    for tgt in rl:
        if protect and tgt == div:
            new.append(tgt)
            protect = False
        elif tgt == div and len(new) >0:
            new.pop()
        elif not tgt % div == 0:
            new.append(tgt)
    print(new)
    return new

new_list = P
k = 0
while True:
    if len(new_list) == 0:
        break
    k += 1
    if 1+k > len(new_list):
        break
    new_list = return_filtered(new_list[1+k], new_list)

print(len(new_list))

Submission status: Runtime Error

Solution code:
def main():
  from collections import deque,defaultdict
  import sys
  input = sys.stdin.readline

  def min_kinder(kinder_max):
    ret = float('inf')
    for x in kinder_max:
      if x==0:
        continue
      else:
        ret = min(ret,x)
    return(ret)
  N,Q = map(int,input().split())
  AB = [list(map(int,input().split())) for _ in range(N)]
  CD = [list(map(int,input().split())) for _ in range(Q)]
  kinder = [defaultdict(int) for _ in range(2*10**5 + 5)]
  kinder_max = [0] * (2*10**5 + 5)
  kinder_num = [0] * (2*10**5 + 5)

  for a,b in AB:
    kinder[b][a] += 1
    kinder_max[b] = max(kinder_max[b], a)
    kinder_num[b] += 1

  equality = min_kinder(kinder_max)
  for c,d in CD:
    a,b = AB[c-1]
    AB[c-1][1] = d
    kinder[b][a] -= 1
    kinder[d][a] += 1
    kinder_num[b] -= 1
    kinder_num[d] += 1
    
    if kinder[b][a]==0:
      kinder[b].pop(a)

    if (kinder_max[b]==equality)or(kinder_max[d]==equality):
      judge = True
    else:
      judge = False

    if kinder_max[b]==a:
      if kinder[b][a]!=0:
        pass
      else:
        if kinder_num[b]==0:
          kinder_max[b] = 0
        else:
          x = 0
          for key,value in kinder[b].items():
            if value<=0:
              continue
            else:
              x = max(x,key)
          kinder_max[b] = x

    kinder_max[d] = max(kinder_max[d], a)

    if judge:
      equality = min_kinder(kinder_max)

    print(equality)
    
main()

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
if A[0] == A[1]:
    n = 1
    o = 1
    x = 0
    while n <= N-1:
        m = 0
        while m <= n-1:
            a = A[n]/A[m]
            if a.is_integer() == False:
                x += 1
            else:
                o += 1
                break
            m += 1
        n += 1
else:
    n = 1
    o = 0
    x = 0
    while n <= N-1:
        m = 0
        while m <= n-1:
            a = A[n]/A[m]
            if a.is_integer() == False:
                x += 1
            else:
                o += 1
                break
            m += 1
        n +=1
print(N-o)

Submission status: Runtime Error

Solution code:
import collections

n = int(input())
p = list(map(int,input().split()))
p.sort(reverse=True)
count=0
a = collections.Counter(p)

if len(a) >1 and a[p[n]] == 1:
    count +=1
for i in range(len(p)):
    if a[1] >=1:
        break
    if a[p[i]]>1:
        continue
    for j in reversed(range(i+1,len(p))):
        if p[i]< p[j]*2 and not p[i]==p[j]:
            count +=1
            break
        if p[i]%p[j] ==0:
            break
        if j == i+1:
            count +=1
if count >=1:
    print(count)
else:
    print(count)

Submission status: Runtime Error

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

ac = A.count(1)
if ac == 1:
    print(1)
    exit()
if ac >= 2:
    print(0):
    exit()

num = [0]*1000005
for a in A:
    num[a] += 1

b = [False]*1000005
seen = [False]*1000005
cnt = 0
A = list(set(A))
A.sort()
for a in A:
    if seen[a]:
        continue

    seen[a] = True
    if b[a] == False:
        cnt += 1
        if num[a] > 1:
            cnt -= 1

    for i in range(a, 1000005, a):
        b[i] = True
print(cnt)

Submission status: Runtime Error

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



cnt = Counter(A)
A.sort()
ans = 0
P = [0] * (10**6+1)
#print(cnt)
for a in A:
    if P[a]==0
        for i in range(10**7):
            x = a*i
            if x>10**6:
                break
            P[x] = 1
        if cnt[a]==1:
            ans +=1

print (ans)

Submission status: Runtime Error

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

def main():
    import bisect
    n = int(input())
    A = list(map(int,sys.stdin.readline().rstrip().split()))


    A.sort()
    ans = 0
    a_max = A[-1]
    note = [True]*(a_max+1)
    for j in n:
        a = A[j]
        if note[a]:
            for i in range(a,a_max+1):
                if i%a==0:
                    note[i] = False
            ans+=1

        
    
    print(ans)
main()

Submission status: Runtime Error

Solution code:
import sympy

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

count = 0
for i in range(N):
    temp = sympy.divisors(A[i])
    data = A
    data[i] = 0
    if set(temp) & set(data):
        count += 1



print(N-count-1)

Submission status: Runtime Error

Solution code:
import numpy as np

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

arr=np.array(lis, float)
arro=np.outer(arr,1/arr)
tf= arro==np.array(arro,dtype='int64')
#print(tf)
#print(np.sum(tf, axis=1))

print(sum(np.sum(tf, axis=1)==1))

Submission status: Runtime Error

Solution code:
import collections

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

c = collections.Counter(A_list)
sorted_list = sorted(A_list)

count = 0

for i_index in range(N):
    i = sorted_list[i_index]
    for j in sorted_list[:i_index]:
        jmemo = j
        print(i, j)
        if i % j == 0:
            break
    else:
        if c[str(i)] == 0
            count+= 1
print(count)

Submission status: Runtime Error

Solution code:
#map(int,input().split())
#int(x) for x in input().split()
#for _ in range(int(input())):
n=int(input())
l=[int(x) for x in input().split()]
v=set()
l.sort(reverse=True)
d={}
for i in range(n):
	if l[i] in d:
		d[l[i]]+=1
	else:
		d[l[i]]=1
if 1 in d:
	if d[1]>1:
		print(0)
	else:
		print(1)
	exit()

for i in range(n):
	c=0
	for j in range(n-1,-1,-1):
		if l[i]<l[j]:
			break
		if  i==j:
			continue
		if l[i]%l[j]==0:
			c=1
			#print(l[j],l[i])
			break
	if c==0:
		ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split())) 
b = sorted(a)
res = 0
for i in range(n):
    for j in range(0,i):
#         if i == j:
#             pass
        if (b[i] == b[j]) or (b[i]%b[j] == 0):
            break
    else:
        res += 1
print(res)

Submission status: Runtime Error

Solution code:
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    N = int(input())
    A = list(map(int, input().split()))

    #output
    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]

    answer = 0
    for i in range(N):
        temp_list = make_divisors(A[i])
        temp1 = temp_list[:-1]
        temp2 = temp_list[-1]
        if len(A[A == temp2]) > 1:
            answer += 1
        for t in temp1:
            if t in A:
                answer += 1
                break

    print(N - answer)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline


def f(a):
    for i in range(n-1):
        b[i] = a[i] % a[i+1]
    return b


n, *a = map(int, read().split())

b = [0] * n

a = sorted(a, reverse=True)
z = 0

while a[len(a)] == 0:
    a = f(a)
    z += 1

print(z-1)

Submission status: Runtime Error

Solution code:
import sympy
#sympy.divisors(10**9)
n = int(input())

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

a.sort(reverse = True)

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

if len(set(a)) == 1:
    print(0)
else:
    
    
    ans = 0

    for i in range(n):
        target = make_divisors(a[i])
        if len(set(target) & set(a)) == 1:
            ans += 1

    print(ans)

Submission status: Runtime Error

Solution code:
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return sorted(divisors, reverse=True)


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

if N == 1:
    print(1)
    
A = sorted(A)
check_list = [0] * (10**6 + 1)

for a in A:
    check_list[a] = 1

cnt = 0
prev_val = -1
next_val = A[1]
for i in range(len(A)):
    if len(A) - 1 == i:
        if prev_val == A[i]:
            continue        
        prev_val = A[i]
    else:
        if next_val == A[i]:
            continue
        next_val = A[i + 1]
    divisors = make_divisors(A[i])[1:-1]
    check_ok = True
    for d in divisors:
       if check_list[d] == 1:
           check_ok = False
    if check_ok == True:
        cnt += 1
print(cnt)

Submission status: Runtime Error

Solution code:

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

d_num = a

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

Submission status: Runtime Error

Solution code:
"""
Created on Sun Jun 14 21:51:57 2020

@author: arisa
"""
from sympy import isprime

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

count = 0
for i in range(N):
    if isprime(A[i]) == False:
        j = 0
        for j in range(N):
            if i != j and A[i] % A[j] == 0:
                count += 1
                break
            j += 1
    i +=1
    
print(N - count)

Submission status: Runtime Error

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

count = 0

for n in range(N):
  if A.count(A[n]) != 1:
    A = [a for a in A if a != A[n]]

for n in range(len(A)):
  flg = True
  tmp = [a for a in A if a != A[n]]
  for m in tmp:
    if A[n]%m == 0:
      flg = False
  if flg == True: count += 1

print(count)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env pypy3

from numba import njit


@jit(nopython=True, parallel=True, cache=True, nogil=True)
def divisors(n):
    res = set()
    for i in range(1, n + 1):
        if i * i > n:
            return res
        d, m = divmod(n, i)
        if m == 0:
            res.add(i)
            res.add(d)
    return res


def count_nondivisors(n, bs):
    ctr = {b: 0 for b in bs}
    for b in bs:
        ctr[b] += 1
    ds = {k: sum(ctr.get(k, 0) for k in divisors(k)) for k in ctr.keys()}
    num_div_elems_table = [ds[bs[i]] for i in range(n)]
    res = sum(num_div_elems_table[i] == 1 for i in range(n))
    return res


def main():
    n = int(input())
    bs = [int(b) for b in input().split()]
    res = count_nondivisors(n, bs)
    print(res)


if __name__ == '__main__':
    main()