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

max_a = 10**6
ans = [[0,0]*(max_a+1)]

for i in a:
	ans[i][0]+=1
	ans[i][1]+=1
for i in set(a):
	if ans[i][1]>0:
		for j in range(i*2,len(ans),i):
			ans[j][0]+=2

count = 0
for i in ans:
	if i[1]>0 and i[0]==1:
		count+=1

print(count)

Submission status: Runtime Error

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

ai.sort()

sqr_max_val = int(ai[n-1]**0.5)
max_val = ai[n-1]
#print(ai)
ai_ex = [0]*(2*10**5+1)
#ai_ex = [0]*(30)

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

for i in range(n):
    if ai_ex[ai[i]-1] > 1:
        ai_ex[ai[i]-1] = 0
    """
    if ai[i] > sqr_max_val:
        break
    """
    tmp = ai[i]
    baisu = 2
    #print(ai[i])
    while tmp * baisu <=  max_val:
        ai_ex[tmp*baisu-1] = 0
        #print(tmp*baisu)
        baisu += 1

for i in range(100):
    if ai_ex[i] == 1:
        a = 1
        #print(i)

print(sum(ai_ex))
#print(ai_ex)

Submission status: Runtime Error

Solution code:
#ABC170 D
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
a = list(map(int,readline().split()))
a.sort()

if a[0] == a[-1]: # n=1 やサンプル２のような時
  if n > 1:
    print(0)
  else:
    print(1)
  exit()

if a[0] == 1: #１だけは素因数分解するときにバグるので別で処理
  if a[0] == a[1]:
    print(0)
  else:
    print(1)
  exit()
  
def divisorize(fct): # 約数のリストつくるやつ
    b, e = fct.pop()
    pre_div = divisorize(fct) if fct else [[]]
    suf_div = [[(b, k)] for k in range(e + 1)]
    return [pre + suf for pre in pre_div for suf in suf_div]

def factorize(n): #素因数分解
    fct = []
    b, e = 2, 0
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct
 
 
def num(fct):
    a = 1
    for base, exponent in fct:
        a = a * base**exponent
    return a
    
s = set()
for nm,i in enumerate(a):
  c = set()
  fct = factorize(i)
  for div in divisorize(fct): # 約数の集合を作る
      c.add(num(div))

# 積集合をとり、それが空でかつ同じ数字が並んでない時に答えを加算
  if c&s == set() and ((nm < n-1 and a[nm+1] != i) or nm == n-1): 
    ans += 1
  s.add(i) #今まで見た数の集合を更新

print(ans)

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

max_a = 10**6+1
ans = [0]*max_a

for i in a:
	ans[i]+=1

for i in a:
	for j in range(i*2,max_a+1,i):
		ans[j]+=2

print(ans.count(1))

Submission status: Runtime Error

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

lst = sorted(lst)

div = [lst[0]]

if lst[0] != lst[1]:
  ans = [lst[0]]
else:
  ans = []

for i in range(1,n):
  if len(ans) != 0 and lst[i] == ans[-1]: 
    del ans[-1]
  else:
    for x in div:
      if lst[i] % x == 0:
        x = -1
        break
    if x != -1:
      div.append(lst[i])
      ans.append(lst[i])
    
print(len(ans))

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from numba import jit
n = int(input())
li = list(map(int, input().split()))
li.sort()
inf = (10**6)+1
isprime = [False]*(inf+1)
for i in li:
    isprime[i] = True
temp = 0
@jit
for i in li:
    if i == temp:
        isprime[i] = False
    if not isprime[i]:
        continue
    for k in range(i*2, inf+1, i):
        isprime[k] = False
    temp = i
prime_list = []
@jit
for i in range(len(li)):
      if i+1<len(li):
            if li[i] == li[i+1]:
                isprime[li[i]] = False
for i in range(1, inf+1):
    if isprime[i]:
        prime_list.append(i)
print(len(prime_list))

Submission status: Runtime Error

Solution code:
N = int(input())
A = sorted((map(int,input().split())))
A_Max = A[-1]
B = [True]*A_Max+1

for i in range(N):
    if B[A[i]]:
        for j in range(2,A_Max):
            if A[i] * j > A_Max:
                break
            B[A[i] * j] = False

ans = 0
for i in range(N):
    if B[A[i]]:
            B[A[i]] = False
            ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
N=int(input())
#5
A=sorted(map(int,input().split()))
#24 11 8 3 16
B = A.copy()

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

if A[0] == B[1]:
	A[0] = 0

print(sum([1 for a in A if a != 0]))

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
n = max(A)
dp = [True for i in range(n+1)]
p = 2
while (p * p <= n): 
  # If prime[p] is not changed, then it is a prime 
  if (prime[p] == True): 
    # Update all multiples of p 
    for i in range(p * p, n+1, p): 
      prime[i] = False
      p += 1
ans = 0
for num in A:
  if dp[num]:
    ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = sorted((map(int,input().split())))
A_Max = A[-1]
B = [True]*A_Max

for i in range(N):
    if B[A[i]]:
        for j in range(0, A_Max):
            if j < 2:
                continue
            elif A[i]*j > A_Max:
                break
            B[A[i] * j] = False

ans = 0
for i in range(N):
    if B[A[i]]:
            B[A[i]] = False
            ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
import sys
from collections import Counter

stdin = sys.stdin

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

n = ni()
a = na()
a.sort()
cnt = Counter(a)
elem = [True]*(a[-1]+1)

for i in a:
  j = i*2
  while j <= a[-1]+1:
    elem[j] = False
    j += i
ans = 0
for v in a:
  if elem[v] == True and cnt[v] == 1:
    ans += 1
    
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = sorted((map(int,input().split())))
A_Max = A[-1]
B = [True]*A_Max

for i in range(N):
    if B[A[i]]:
        for j in range(2, A_Max):
            if A[i]*j > A_Max:
                break
            B[A[i] * j] = False

ans = 0
for i in range(N):
    if B[A[i]]:
            B[A[i]] = False
            ans += 1
        
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import collections

stdin = sys.stdin

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

n = ni()
a = na()
a.sort()
cnt = collections.Counter(a)


elem = [True]*(a[-1]+1)
for i in a:
  for j in range(i*2,len(elem)+1,i):
    elem[j] = False
ans = 0
for v in a:
  if elem[v] == True and cnt[v] == 1:
    ans += 1
    
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = sorted((map(int,input().split())))
A_Max = A[-1]
B = [True]*A_Max

for i in range(N):
    if B[A[i]]:
        for j in range(2, A_Max):
            if A[i]*j > A_Max:
                break
            B[A[i] * j] = False

ans = 0
for i in range(N-1):
    if B[A[i]]:
        if A[i] == A[i+1]:
            B[A[i]] = False
        else:
            ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
cnt = 0
 
A.sort(reverse=True)
for i in range(N-1):
  for j in range(i+1, N):
    if A[i] % A[j] == 0:
      cnt-=1
      break
  cnt += 1
if A[-1] != A[-2]:
  cnt += 1
print(cnt)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
cnt = 0
 
A.sort(reverse=True)
for i in range(N-1):
  for j in range(i+1, N):
    if A[i] % A[j] == 0:
      cnt-=1
      break
  cnt += 1
if A[-1] != A[-2]:
    cnt += 1
print(cnt)

Submission status: Runtime Error

Solution code:
import sys


readline = sys.stdin.buffer.readline


def solver(A):
    cdef:
        list C
        int upper_lim, cnt, a, i

    upper_lim = A[-1] + 1
    C = [0 for _ in range(upper_lim)]

    for a in A:
        if C[a] > 1:
            continue
        _ = [C[i] + 1 for i in range(a, upper_lim, a)]

    cnt = 0
    for a in A:
        cnt += C[a] == 1

    return cnt


def run():
    _ = int(readline())
    A = list(map(int, readline().split()))

    A = sorted(A)
    ans = solver(A)
    print(ans)


run()

Submission status: Runtime Error

Solution code:
import sys

from numba import njit

from numba.typed import List

readline = sys.stdin.buffer.readline


# def solver(list A):
# cdef:
#     list C
#     int upper_lim, cnt, a, i


@njit
def solver(A):
    upper_lim = A[-1] + 1
    C = [0 for _ in range(upper_lim)]

    for a in A:
        if C[a] > 1:
            continue
        for i in range(a, upper_lim, a):
            C[i] += 1

    cnt = 0
    for a in A:
        cnt += C[a] == 1

    return cnt


def run():
    N = int(readline())
    A = list(map(int, readline().split()))

    A = sorted(A)
    ans = solver(List(A))
    print(ans)


run()

Submission status: Runtime Error

Solution code:
import sys
N = int(input())
A = sorted(list(map(int, sys.stdin.readline().split())))

count = 0

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

Submission status: Runtime Error

Solution code:
N = int(input())
A = sorted((map(int,input().split())))
A_Max = A[-1]
B = [True]*A_Max

for i in range(N):
    if B[A[i]]:
        for j in range(2, A_Max // A[i]+1):
            B[A[i]*j] = False

ans = 0
for i in range(N-1):
    if B[A[i]]:
        if A[i] == A[i+1]:
            B[A[i]] = False
        else:
            ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = sorted((map(int,input().split())))
A_Max = A[-1]
B = [True]*A_Max

for i in range(N):
    if B[A[i]]:
        for j in range(2, A_Max//A[i]+1):
            B[A[i]*j] = False

ans = 0
for i in range(N-1):
    if B[A[i]]:
        if A[i] == A[i+1]:
            B[A[i]] = False
        else:
            ans += 1

print(ans)

Submission status: Runtime Error

Solution code:

import sys
import numpy as np
from collections import Counter


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)

MOD = 10 ** 9 + 7
INF = float("inf")


def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    max = A[-1]
    count = Counter(A)
    S = list(count.keys())
    C = []
    for s in S:
        if count[s] > 1:
            continue
        else:
            C.append(s)

    is_prime = np.ones(max + 1, np.bool)
    for a in A:
        if is_prime[a]:
            is_prime[a * 2 :: a] = 0
        else:
            continue
    answer = 0
    for c in C:
        if is_prime[c]:
            answer += 1
        else:
            continue
    print(answer)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import deque
from sys import exit
N = int(input())
if N == 1:
  print(1)
  exit()
A = list(map(int, input().split()))
ban = {}
D = {}
for a in A:
  if a in D:
    ban.app(a)
  else:
    D.app(a)
D = deque(sorted(list(D)))
ans = 0
while D:
  ini = D.popleft()
  if not ini in ban:
    ans += 1
  if len(D) == 0:
    break
  for i in range(len(D)):
    d = D.popleft()
    if d % ini != 0:
      D.append(d)
print(ans)

Submission status: Runtime Error

Solution code:
n,*a=map(int,open(0).read().split())
a.sort()
for i in range(n):
    for j in range(n):
        if a[j]>＝a[i]:
            break
        if i==j:
            continue
        if a[i]%a[j]==0:
            n-=1
            break
print(n)

Submission status: Runtime Error

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

@jit
def search(N,c):
  count = 0
  for i in range(N):
    b = []
    m = copy.copy(c)
    a = c[i]
    m.pop(i)
    m.sort()
    for j in range(N-1):
      if m[j]>c[i]:
        count+=1
        break
      elif c[i]%m[j]==0:
        break
      elif j == N-2:
        count+=1
      elif c[i]%m[j]!=0:
        continue
      
  return count

print(search(N,c))

Submission status: Runtime Error

Solution code:
M = int(input())
A=list(map(int,input().split()))
A.sort()
ma=A[-1]
is_prime = [True] * (ma + 1)
for i in A:
    if not is_prime[i]:
        continue
    for j in range(i * 2, ma + 1, i):
        is_prime[j] = False
k=[i for i in range(ma + 1) if is_prime[i]]
N=[]
if A[0] !=A[1]:
    N.append(A[0])
for i in range(1,len(A)-1):
    if A[i-1]!=A[i] and A[i]!=A[i+1]:
        N.append(A[i])
if A[len(A)-2] != A[len(A)-1]:
    N.append(A[len(A)-1])
s=set(k) & set(N)
print(len(s))

Submission status: Runtime Error

Solution code:
M = int(input())
A=list(map(int,input().split()))
A.sort()
ma=A[-1]
is_prime = [True] * (ma + 1)
for i in A:
    if not is_prime[i]:
        continue
    for j in range(i * 2, ma + 1, i):
        is_prime[j] = False
k=[i for i in range(ma + 1) if is_prime[i]]
N=[]
if A[0] !=A[1]:
    N.append(A[0])
for i in range(1,len(A)-1):
    if A[i-1]!=A[i] and A[i]!=A[i+1]:
        N.append(A[i])
if A[-2] != A[-1]:
    N.append(A[-1])
s=set(k) & set(N)
print(len(s))

Submission status: Runtime Error

Solution code:
n = int(input())
A = list(map(int, input().split()))
dp = [False]*10**6
A.sort(reverse = True)
for a in A:
    dp[a]=True
    for i in range(2, 10**6//a):
        dp[i*a] = False
print(dp.count(True))

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
    from collections import Counter
    M = max(A) + 1
    B = [True] * (M)
    A = sorted(A)
    C = Counter(A)

    answer = 0
    for a in A:
        if C[a] > 1:
            continue
        elif B[a]:
            answer += 1
            for j in range(a, M+1, a):
                B[j] = False

    print(answer)

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

Submission status: Runtime Error

Solution code:
# O(N*sqrt(A))
n,*a=map(int,open(0).read().split())
from collections import defaultdict, deque
import sympy

dd=defaultdict(set)

for q in a:
    dd[q]=set(sympy.divisors(q))
cnt=0
a.sort()
b=deque(a)
while b:
    p=b.pop()
    if len(dd[p]&set(b))==0:
        cnt+=1
print(cnt)

Submission status: Runtime Error

Solution code:
n=int(input())

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

a.sort()

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

for i in range(1,n):
    flag = True
    for j in range(i):
        if a[i] % a[j] == 0:
            flag = False
            break
        if int(a[i]**0.5)+1 < a[j]:  
            break
    if i == n-1:
        if flag and a[i] != a[i-1]:
            ans += 1
    else:
        if flag and a[i] != a[i-1] and a[i] != a[i+1]:
            ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())

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

a.sort()

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

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

Submission status: Runtime Error

Solution code:
N = int(input())
A = {}
for n in input().split():
  i = int(n)
  A[i] = 0
A.sort()

Submission status: Runtime Error

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

amax = max(a)*(2*10**6)
dp = [True] * (amax) 

a.sort()

for i in range(len(a)):
    if dp[i] :
        for j in range(2,max(a)//a[i]+1):
            dp[a[i] * j] = False
        if a[i] in a[i+1:]:
            dp[a[i]] = False
cnt = 0
print(a)

for ai in a:
    print(dp[ai])
    if dp[ai]:
        cnt += 1

print(cnt)

Submission status: Runtime Error

Solution code:
def main():
    n, *a = map(int, open(0).read().split())
    if n == 1:
        print(1)
        return

    m = max(a) + 1
    l = [0] * m
    for i in a:
        for j in range(i, m, i):
            l[j] += 2
        l[i] -= 1

    ans = sum(a[i] == -1 for i in a)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

amax = max(a)*2
dp = [True] * (amax) 

a.sort()

for i in range(len(a)):
    if dp[i] :
        for j in range(2,math.sqrt(a[i])):
            dp[a[i] * j] = False
        if a[i] in a[i+1:]:
            dp[a[i]] = False

cnt = 0
for ai in a:
    if dp[ai]:
        cnt += 1

print(cnt)

Submission status: Runtime Error

Solution code:
from numba import jit

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

a.sort()

import collections
c = collections.Counter(a)

d=[]
for ck,cv in c.items():
    if cv>=2:
       d.append(ck) 
dset=set(d)
    
aaset=set()

@jit
def dp():
    while True:
        aaset.add(a[0])
        a2=[]
        for i,ai in enumerate(a,1):
            if ai%a[0]!=0:
                a2.append(ai)
        a=a2.copy()
        if len(a2)==0:
          break
    return True

yn=dp()
aaset=aaset-dset    
print(len(aaset))

Submission status: Runtime Error

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

cnt = Counter(p)

ps = set(p)
plst = list(ps)
plst.sort()
temp = plst[:]
jdg = [True]*N
ans = 0
#while temp:
for l, q in enumerate(plst):
    if not jdg[l]: continue

    for j in range(l+1, N):
        if plst[j]%q==0: jdg[j]=False
    if cnt[q] == 1: ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
M=10**6
_,*l=map(int,open(0).read().split())
a=[0]*M
for i in sorted(l):
  a[i]+=1
  if a[i]==1:
    for j in range(2*i,M,i):a[j]+=9
print(a.count(1))

Submission status: Runtime Error

Solution code:
n = int(input())
A = sorted(map(int, input().split()))
nux = A[-1]+1
ans = 0
table = [True]*nux
for i, s in enumerate(A):
    if table[s] == False:
        continue
    if i == n-1:
        ans += 1
    elif A[i+1] != s:
        ans += 1
    b = 1
    while b*s <= nux:
        table[b*s] = False
        b += 1
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
A = sorted(map(int, input().split()))
nux = A[-1]+1
ans = 0
table = [True]*nux
for i, s in enumerate(A):
    if table[s] == False:
        continue
    if i == n-1:
        ans += 1
    if A[i+1] != s:
        ans += 1
    b = 1
    while b*s <= nux:
        table[b*s] = False
        b += 1
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
A = list(map(int, input().split()))
nux = max(A)
B = set(A)
A.sort()
ans = 0
table = [True]*(nux+1)
for ii, s in enumerate(A):
    if table[s] == False:
        continue
    if A[ii+1] != s:
        ans += 1
    i = 1
    while i*s <= nux:
        table[i*s] = False
        i += 1

print(ans)

Submission status: Runtime Error

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

A.sort(reverse=True)
dp = [True] * N

for i in range(N):
    for j in range(i+1, N):
        if dp[i] == False:
            continue
        else:
            if A[i] % A[j] == 0:
                dp[i] = False

if A[-2] == A[-1]:
    dp[-1] = False

print(dp.count(True))

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
M = 100000
cnt = [0]*M
ans = 0
for a in A:
    if cnt[a] != 0:
        cnt[a] = 2
    else:
        for i in range(a, M, a):
            cnt[i] += 1
for a in A:
    if cnt[a] == 1:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
def d170(n,a):
    count=0
    dp=[0 for i in range(max(a)+1)]
    if sa[0]==1:
        if sa[1]==1:
            return 0
        else:
            return 1
    else:
        for x in a:
            if dp[x]!=0:
                dp[x]=2
            else:
                for j in range(x,max(a)+1,x):
                        dp[j]+=1
        for x in sa:
            if dp[x]==1:
                count+=1
        return count
    
n=int(input())
a=list(map(int, input().split()))    
print(d170(n,a))

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
M = 100005
cnt = [0]*M
ans = 0
for a in A:
    if cnt[a] != 0:
        cnt[a] = 2
    else:
        for i in range(a, M, a):
            cnt[i] += 1
for a in A:
    if cnt[a] == 1:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
def d170(n,a):
    count=0
    sa=sorted(a)
    dp=[0 for i in range(max(a)+1)]
    if sa[0]==1:
        if sa[1]==1:
            return 0
        else:
            return 1
    else:
        for x in sa:
            if dp[x]!=0:
                dp[x]=2
            else:
                for j in range(x,max(a)+1,x):
                        dp[j]+=1
        for x in sa:
            if dp[x]==1:
                count+=1
        return count
    
n=int(input())
a=list(map(int, input().split()))    
print(d170(n,a))

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
M = 100005
cnt = [0]*M
ans = 0
for a in A:
    if cnt[a] == 1:
        cnt[a] = 2
    else:
        for i in range(a, M, a):
            cnt[i] += 1
for a in A:
    if cnt[a] == 1:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
def d170(n,a):
    count=0
    sa=sorted(a)
    dp=[0 for i in range(max(a)+1)]
    if sa[0]==1:
        if sa[1]==1:
            return 0
        else:
            return 1
    else:
        for x in sa:
            if dp[x]==0:
                for j in range(x,max(a)+1,x):
                            dp[j]+=1
            elif dp[x]>0:
                dp[x]+=1
        for x in sa:
            if dp[x]==1:
                count+=1
        return count
     
    
n=int(input())
a=list(map(int, input().split()))    
print(d170(n,a))

Submission status: Runtime Error

Solution code:
def d170(n,a):
    count=0
    sa=sorted(a)
    dp=[0 for i in range(max(a)+1)]
    if sa[0]==1:
        if sa[1]==1:
            return 0
        else:
            return 1
    else:
        for x in sa:
            if dp[x]==0:
                for j in range(0,max(a)+1):
                    if j%x==0:
                            dp[j]+=1
            elif dp[x]>0:
                dp[x]+=1
        for x in sa:
            if dp[x]==1:
                count+=1
        return count
     
    
n=int(input())
a=list(map(int, input().split()))    
print(d170(n,a))

Submission status: Runtime Error

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

amax = max(a)*2
dp = [True] * (amax) 

a.sort()

for i in range(len(a)):
    if dp[i] :
        for j in range(2,amax//a[i]):
            dp[a[i] * j] = False
        if a[i] in a[i+1:]:
            dp[a[i]] = False

cnt = 0
for ai in a:
    if dp[ai]:
        cnt += 1

print(cnt)

Submission status: Runtime Error

Solution code:
IN = iter(Input.split('\n')).__next__
def input():
    return IN()

###################################################
from collections import defaultdict


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


def divisor(n):
    div_list = []
    limit = int(n**0.5) + 1
    for div in range(1, limit):
        if n % div == 0:
            div2 = n // div
            div_list.append(div)
            if div != div2:
                div_list.append(div2)
    
    return div_list


        
A_dict = defaultdict(int)
for a in A:
    A_dict[a] += 1

    
ans = n
for a in A:
    divs = divisor(a)
    for div in divs:
        if div == a:
            
            if A_dict[div] >= 2:
                ans -= 1
                break
        else:
            if A_dict[div] >= 1:
                ans -= 1
                break
            

print(ans)

Submission status: Runtime Error

Solution code:
def d170(n,a):
    sa=sorted(a)
    dp=[0 for i in range(max(a)+1)]
    if sa[0]==1:
        if sa[1]==1:
            return 0
        else:
            return 1
    else:
        for x in sa:
            if dp[x]==0:
                for j in range(x,n):
                    if j%x==0:
                            dp[j]+=1
        return dp.count(1)
    
n=int(input())
a=list(map(int, input().split()))    
print(d170(n,a))

Submission status: Runtime Error

Solution code:
def d170(n,a):
    sa=sorted(a)
    dp=[0 for i in range(max(a)+1)]
    if sa[0]==1:
        if sa[1]==1:
            return 0
        else:
            return 1
    else:
        for x in sa:
            if dp[x]==0:
                for j in range(x,n):
                    if j%x==0:
                            dp[j]+1
        return dp.count(1)
    
n=int(input())
a=list(map(int, input().split()))    
print(d170(n,a))