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())
ls = list(map(int,input().split()))
    
Pls = [0] * (10**6+1)

for i in ls:
    Pls[i] += 1

ii = 0
for j in range(len(Pls)):
    if Pls[j] == 0:
        continue
    elif Pls[j] == 1:
        ii += 1
        t = 2*j
        while t <= 10**6+1:
            Pls[t] = 0
            t += j
    else:
        t = 2*j
        while t <= 10**6+1:
            Pls[t] = 0
            t += j

print(ii)

Submission status: Runtime Error

Solution code:
N = int(input())
ls = list(map(int,input().split()))
    
Pls = [0] * (10**6+1)

for i in ls:
    Pls[i] = 1

ii = 0
for j in range(len(Pls)):
    if Pls[j] == 0:
        continue
    else:
        ii += 1
        t = 2*j
        while t <= 10**6+1:
            Pls[t] = 0
            t += j

print(ii)

Submission status: Runtime Error

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

l=[0]*(10**6)
ans=0
#print(l)
for i in a:
    if l[i]==0:
        for j in range(i,10**6,i):
            l[j]+=1
    else:
        l[i]+=1
for i in a:
    if l[i]==1:
        ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
def d170(n,a):
    count=0
    sa=sorted(a)
    dp=[True for i in range(n)]
        return dp.count(True)
    
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=[True for i in range(n)]
    if sa[0]==1:
        if sa[1]==1:
            return 0
        else:
            return 1
    else:
        for i in range(n):
            if dp[i]:
                for j in range(i+1,n):
                    if dp[j]:
                        if sa[j]%sa[i]==0:
                            dp[j]=False
        return dp.count(True)
    
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=[True for i in range(n)]
    if sa[0]==1:
        if 1 in t:
            return 0
        else:
            return 1
    else:
        for i in range(n):
            if dp[i]:
                for j in range(i+1,n):
                    if dp[j]:
                        if sa[j]%sa[i]==0:
                            dp[j]=False
        return dp.count(True)
    
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(list(set(a)))
    if sa[0]==1:
        if 1 in t:
            return 0
        else:
            return 1
    else:
        for i in range(len(sa)) :
            if i>=len(sa):
                break
            else:
                p=sa[i]
                k=[]
                for j in range(i+1,len(sa)):
                     if sa[j]%p==0:
                        k.append(sa[j])
                sa=sorted(list(set(sa)-set(k)))
        return len(set(sa))
    
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(list(set(a)))
    if sa[0]==1:
        if 1 in t:
            return 0
        else:
            return 1
    else:
        for i in range(sa) :
            if i>=len(sa):
                break
            else:
                p=sa[i]
                k=[]
                for j in range(i+1,len(sa)):
                     if sa[j]%p==0:
                        k.append(sa[j])
                sa=sorted(list(set(sa)-set(k)))
        return len(set(sa))
    
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()))
A.sort()

F = [0 for i in range(A[-1]+1)]
for i in A:
  F[i] = 1

c_set = set()
for i in A:
  if F[i] == 0:
    continue
  c_set.add(i)
  for j in range(i, A[-1]+1, i):
    F[j] = 0

ans = len(c_set)
d = 0
d_set = set()
for i in range(N):
  if i == 0:
    if A[i] == A[i+1]:
      d_set.add(A[i])
  elif i < N - 1 and A[i-1] != A[i] and A[i] == A[i+1]:
    d_set.add(A[i])

print( len(c_set - d_set) )

Submission status: Runtime Error

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

MAX_N = max(A)+1
cnt = [0] * MAX_N 

for a in A:
  for i in range(1, MAX_N):
    if cnt[a] <= 2: 
      tmp = a * i
      if tmp > MAX_N: break
      cnt[tmp] += 1
ans = 0
for a in tuple(set(A)):
  if cnt[a] == 1:
    ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
from collections import Counter


n = int(input())
a = [int(x) for x in input().split(' ')]

s = np.array(sorted(set(a)),int)
bl = np.array([True]*n, bool)
for i in range(1, n):
    mod = s[i]
    buf = s[:i][bl[:i]]
    for j in range(len(buf)):
        if mod % buf[j] == 0:
            bl[i] = False
            break
s = set(s[bl])

c = Counter(a)
keys = set([k for k, v in c.items() if v == 1])

print(len(s&keys))

Submission status: Runtime Error

Solution code:
import sys
from numba import njit

@njit(cache+True)
def solve(a,n):
    ava = [0]*a[-1]
    for i in range(n):
        for j in range(n):
            if a[j]%a[i]==0 and ava[a[j]-1]<2:
                ava[a[j]-1] += 1
    return ava.count(1)
 
if __name__=='__main__':
    n = int(sys.stdin.readline().rstrip())
    a = list(map(int,sys.stdin.readline().rstrip().split()))
    a.sort()
    print(solve(a,n))

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
from numba as njit


@njit
def solve(A):
  count = np.zeros(10**6+10, np.int32)
  for x in A:
    if count[x] > 1:
      continue
    else:
      count[::x] += 1
  ret = 0
  for x in A:
    if count[x] == 1:
      rep += 1
  return ret


A = np.array(read().split(),np.int32)
print(solve(A))

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=[0]*10**6

for i in range(n):
  if b[a[i]]==0:#a[i]の1倍にflag
    b[a[i]]=-1
  elif b[a[i]]==-1:#既出のa[i]の1にflag
    b[a[i]]="#"
    
  for j in range(a[i]*2,10**6,a[i]):#a[i]の倍数にflag
    b[j]=1

cnt=0
for i in range(n):
  if b[a[i]]==-1:
    cnt+=1
#print(b)
print(cnt)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.buffer.readline
import collections
import bisect


def divisors(n):
    i = 2
    table = []
	table.append(1)
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return sorted(table)

def BinarySearch(a, x): 
    i = bisect.bisect_left(a, x) 
    if i != len(a) and a[i] == x: 
        return i 
    else: 
        return -1

N = int(input())
A = [int(a) for a in input().split()]
A.sort()
L = collections.Counter(A)

ans = 0
for a in A:
    if L[a] != 1:
        continue
    for d in divisors(a)[:-1]:
        if(BinarySearch(A, d)!=-1):
			break
    else:
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
import sys 
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))

def main():
    n = I()
    a = LI()
    ava = [1]*n

    for i in range(n):
        x = a[i]
        for j in range(i+1,n):
            print(ava)
            if not ava[i] and not ava[j]:
                break
            y = a[j]
            if ava[i]:
                if not x%y:
                    ava[i] = 0
            if ava[j]:
                if not y%x:
                    ava[j] = 0    
    print(ava.count(1))
    return
 
if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.buffer.readline
import collections
from bisect import bisect_left


def divisors(n):
    i = 2
    table = []
	table.append(1)
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return sorted(table)

N = int(input())
A = [int(a) for a in input().split()]
A.sort()
L = collections.Counter(A)

ans = 0
for a in A:
    if L[a] != 1:
        continue
    for d in divisors(a)[:-1]:
        if(BinarySearch(A, d)!=-1):
			break
    else:
        ans += 1

print(ans)

Submission status: Runtime Error

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


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

    # 愚直に行うとO(N^2)となる
    # エラトステネスの篩を真似ると、NlogNで済む
    # 同じ数字が存在している場合は、注意する

    table = [False]*(A[-1]+1)
    ans = 0
    for i in range(N):
        # すでに何かの倍数ならば、考える必要なし
        if table[A[i]]:
            continue
        # 最大値まで見ていく
        for j in range(2, A[-1]//A[i]+1):
            table[A[i]*j] = True

    ans = 0
    for i in range(N):
        if table[A[i]] is False:
            ans += 1
            if i == 0:
                if A[0] == A[1]:
                    ans -= 1
            elif i == N-1:
                if A[N-1] == A[N-2]:
                    ans -= 1
            else:
                if A[i] == A[i-1] or A[i] == A[i+1]:
                    ans -= 1
    print(ans)

    return


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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


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

    # 愚直に行うとO(N^2)となる
    # エラトステネスの篩を真似ると、NlogNで済む
    # 同じ数字が存在している場合は、注意する

    table = [False]*(A[-1]+1)
    ans = 0
    for i in range(N):
        # すでに何かの倍数ならば、考える必要なし
        if table[A[i]]:
            continue
        # 最大値まで見ていく
        for j in range(2, A[-1]//A[i]+1):
            table[A[i]*j] = True

    ans = 0
    for i in range(N):
        if table[A[i]] is False:
            ans += 1
            if i == 0 and A[0] == A[1]:
                ans -= 1
            elif A[i] == A[i-1]:
                ans -= 1
    print(ans)

    return


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
cnt = [0] * (10**6)

for elem in a:
    if elem not in cnt:
        cnt[elem] += 1

unique = []

for i in range((10**6)+1):
    if cnt[i] == 1:
        unique.append(i)

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

for elem in unique:
    for m in range(elem*2, (10**6)+1, elem):
        cnt[m] = 1

ans = 0

a = list(set(a))

for elem in a:
    if cnt[elem] == 0:
        ans+=1

print(ans)

Submission status: Runtime Error

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

INF=A[-1]+1

c=[0]*(INF)
if A[0]==1:
    print(0)
    exit(0)
y=N
for i in range(N):
  if i>=1:
    if A[i]==A[i-1]:
      y-=1
      continue
  if i<=N-1:
    if A[i]==A[i+1]:
      y-=1
      continue      
  if c[A[i]]!=0:
    y-=1
    continue
  else:
    x=A[i]
    while x<INF:
      c[x]+=1
      x+=A[i]
      
print(y)

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

d = defaultdict(int)

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

arr = []
for i in d:
	if d[i]==1:
		arr.append(i)
arr.sort()

if len(arr)==0:
	print(0)
	exit()

#maxa = max(arr)
maxa = 2*(10**5)+1
ans = [0]*(maxa+1)
for i in arr:
	ans[i]=1

for i in arr:
	for j in range(i*2,maxa+1,i):
		ans[j]=0

print(ans.count(1))

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

d = defaultdict(int)

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

arr = []
for i in d:
	if d[i]==1:
		arr.append(i)
arr.sort()

if len(arr)==0:
	print(0)
	exit()

#maxa = max(arr)
maxa = 2*(10**5)+1

ans = [0]*(maxa+1)
for i in arr:
	ans[i]=1

for i in arr:
	if ans[i]!=0:
		for j in range(i*2,maxa+1,i):
			ans[j]=0

print(ans.count(1))

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

d = defaultdict(int)

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

arr = []
for i in d:
	if d[i]==1:
		arr.append(i)
arr.sort()

if len(arr)==0:
	print(0)
	exit()

#maxa = max(arr)
maxa = 2*(10**5)+1

ans = [0]*(maxa+1)
for i in arr:
	ans[i]=1

for i in arr:
	if ans[i]!=0:
		for j in range(i*2,maxa+1,i):
			if j>maxa:
				break
			ans[j]=0

print(ans.count(1))

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

d = defaultdict(int)

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

arr = []
for i in d:
	if d[i]==1:
		arr.append(i)
arr.sort()

if len(arr)==0:
	print(0)
	exit()

#maxa = max(arr)
maxa = 2*10**5+1

ans = [0]*(maxa+1)
for i in arr:
	ans[i]=1

for i in arr:
	if ans[i]!=0:
		for j in range(i*2,maxa+1,i):
			if j>maxa:
				break
			ans[j]=0

print(ans.count(1))

Submission status: Runtime Error

Solution code:
from collections import Counter

def main():
    N = int(input())
    *A, = map(int, input().split())
    A.sort()
    C = Counter(A)

    MAX = 2000005
    T = [0]*MAX

    ans = 0
    for a in A:
        if T[a]:
            continue
        else:
            if C[a] == 1:
                ans += 1
            for i in range(2*a, MAX, a):
                T[i] += 1
    print(ans)

@jit()

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
arr = list(map(int, input().split()))
arr.sort()
m = []
for i in range(n):
    m[arr[i]] = 1
    j=2
    while(j*arr[i] <= arr[n]):
        m[j*arr[i]] = -1
        j += 1
print(m.count(1))

Submission status: Runtime Error

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

B = set(A)

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

check_list = [0] * (10**6)
for i in B:
    for j in range(1, (10**6 // i)):
        check_list[i * j] += 1

count = 0
for i in B:
    if check_list[i] == 1:
        count += 1

print(count)

Submission status: Runtime Error

Solution code:
n = int(input())
arr = list(map(int, input().split()))
arr.sort()
m = []
for i in range(n):
    m[arr[i]] = 1
    for j in range(2,arr[n]+1):
        m[j*arr[i]] = -1
print(m.count(1))

Submission status: Runtime Error

Solution code:
import numpy as np

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

As.sort()

# indexを数値と紐づけるために+1増やした数にする
check = np.zeros(10**6+1)

answer = 0

# 与えられた数列の小さいものから順にループ
for i in range(length):
    if check[As[i]] == 0:
        # 与えられた数値の倍数すべてに1を立てる
        # checkは0始まりのため、0と倍数要素に1が立つ
        check[::As[i]] = 1
        
        # 同じ数字が複数ある場合はカウントさせない
        if As[i] != As[i + 1]:
            answer = answer + 1

print(answer)

Submission status: Runtime Error

Solution code:
n = int(input())
arr = list(map(int, input().split()))
arr.sort()
m = []
for i in range(n):
    m[arr[i]] = 1
    for j in range(2,arr[n]):
        m[j*a[i]] = -1
print(m.count(1))

Submission status: Runtime Error

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

dp = {i: 0 for i in range(1, dp+1)}

ans = 0
for i in range(n):
    if dp[a[i]] == 1:
        continue

    if i == n - 1 or a[i] != a[i+1]:
        ans += 1

    prime += a[i]
    while prime <= maxa:
        dp[prime] = 1
        prime += a[i]
    
print(ans)

Submission status: Runtime Error

Solution code:
sucl =[]
for i in range(0,int(N)):
  T=True
  for j in range(0,int(N)):
    if T== False:
      break
    if A[i]<A[j]:
      break
    if A[i] % A[j]==0:
      if i==j:
        pass
      else:
        T=False
        
  if T==True:
    sucl.append(i)
print(len(sucl))

Submission status: Runtime Error

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

    max_dp = max(A) + 1
    dp = [0] * max_dp

    for a in A:
        if dp[a] >= 2:
            continue
        dp[a] += 1
        for i in range(a << 1, max_dp, a):
            dp += 2
    print(np.sum(dp == 1))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N = int(input())
a_list = [int(i) for i in input().split()]
count = 0
for i in a_list:
    flag_list = [i % j for j in a_list]
    if flag_list.count(0) = 1 :
        count += 1
    
print(count)

Submission status: Runtime Error

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

N = int(input())

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

AList.sort()

dp = [0] *  (AList[-1] + 1)

for i in AList:
    dp[i] += 1
    
    if dp[i] == 1:
        for p in range(2 * i, len(dp), i):
            dp[j] += 2

print(dp.count(1))

Submission status: Runtime Error

Solution code:
n = int(input())
A, = map(int, input().split())
maxA = max(A)
# C[a] = A内のaの個数
C = {a: 0 for a in A}
for a in A:
    C[a] += 1
# D[a]=1: Aにaより小さいaの約数が存在する
D = {a: 0 for a in A}
for a in A:
    if C[a] > 0:
        t = 2
        while a * t <= maxA:
            D[a * t] = 1
            t += 1
ans = 0
for a in A:
    if C[a] == 1 and D[a] == 0:
        ans += 1
print(ans)

Submission status: Runtime Error

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

n = int(input())
a = [int(x) for x in input().split()]
maxval = 10 ** 6
has_prime_factor = [0] * (maxval+1)
has_prime_factor[0] = 2
has_prime_factor[1] = 2
for i in range(n+1):
    if a[i] == 1:
        continue
    if has_prime_factor[a[i]] > 1:
        continue
    for k in range(a[i], maxval+1, a[i]):
        has_prime_factor[k] += 1

result = sum(has_prime_factor[v] <= 1 for v in a)
print(result)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from bisect import *
from heapq import *
up=2*10**5
maxi=10**10
kind=[heapify([]) for i in range(up)]

class segtree:
    x_unit=maxi # 要素として入れられる最大値
    x_func=min
    def __init__(self,n):
        self.n=n
        self.x=[self.x_unit]*(2*n)
    def build(self, seq):
        for i,j in enumerate(seq, start=self.n):  # n番目からseqをx配列に移していく
            self.x[i] = j
        for i in range(self.n-1, 0, -1):
            self.x[i] = self.x_func(self.x[i*2], self.x[i*2+1])
            # セグ木トーナメント表の左右を比較
            # 例えばn=8の時、seq[4]はx[12]に、seq[5]はx[13]に入っている
            # さらにx[14]とx[15]の間に来るのはx[7]、x[12]とx[13]の間に来るのはx[6]
            # x_funcに従って値を取得
    def set_val(self,i,j): # 1点更新
        i += self.n
        self.x[i]=j
        while i>1:
            i//=2 # 更新後、木の上へと登っていくついでに更新
            self.x[i]=self.x_func(self.x[i*2], self.x[i*2+1])
    def fold(self,l,r): # 区間[l, r)の最小値などを取得 
        l+=self.n
        r+=self.n
        val_l=self.x_unit
        val_r=self.x_unit
        while l<r:
            if l & 1: # lが奇数
                val_l=self.x_func(val_l,self.x[l])
                l+=1 # 偶数に調節
            if r & 1: # rが奇数
                r-=1 # 開区間なので1個前は偶数番目の要素
                val_r=self.x_func(val_r,self.x[r])
            l //= 2
            r //= 2
        return self.x_func(val_l,val_r)

n,q=map(int, input().split())
shozoku=[-1]*n
rating=[0]*n
for i in range(n):
    a,b=map(int, input().split())
    heappush(kind[b-1],a)
    shozoku[i]=b-1
    rating[i]=a
#print(kind)
seg=segtree(up)
root=[maxi for i in range(up)]

for i in range(up):
    if kind[i]!=[]:
        rate=kind[i][-1]
        root[i]=rate
seg.build(root)

for i in range(q):
    c,d=map(int, input().split())
    c-=1
    d-=1
    if rating[c]==kind[shozoku[c]][-1] and len(kind[shozoku[c]])==1:
        kind[shozoku[c]]=heapify([])
        seg.set_val(shozoku[c], 2<<30)
    elif rating[c]==kind[shozoku[c]][-1]:
        kind[shozoku[c]]=kind[shozoku[c]][:-1]
        seg.set_val(shozoku[c], kind[shozoku[c]][-1])
    else:
        ind=bisect_right(kind[shozoku[c]],rating[c])
        kind[shozoku[c]]=kind[shozoku[c]][:ind-1]+kind[shozoku[c]][ind:]
    heappush(kind[d], rating[c])
    seg.set_val(d, kind[d][-1])
    shozoku[c]=d
    print(seg.x[1])

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
B = [0] * (2 * 10 ** 5 + 1)
M = max(A)

for a in A:
	B[a] += 1