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: Wrong Answer

Solution code:
def divisor(n):
    d = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            d.append(i)
            if i ** 2 == n:
                continue
            d.append(n // i)
    return d

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

dup = [x for x in set(A) if A.count(x) > 1]
A_dif = set(A) - set(dup)

cnt = 0
for a in A_dif:
    tmp = set(divisor(a)) & set(A_dif)
    if len(tmp) == 1: cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
import collections


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

    A.sort()
    a_max = A[-1]
    dp = [True] * a_max
    r = 0
    sames = 0

    C = collections.Counter(A)
    for v in C.values():
        if v > 1:
            sames += 1

    A = set(A)

    for a in A:
        if dp[a - 1]:
            r += 1
            tmp_a = a
            while tmp_a < a_max + 1:
                tmp_a += a
                if tmp_a > a_max:
                    break
                else:
                    dp[tmp_a - 1] = False

    print(max(0, r - sames))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    n=int(input())
    a=list(map(int,input().split()))
    adic={}
    for i in range(n):
        if a[i] in adic:
            adic[a[i]]+=1
        else:
            adic[a[i]]=1
    ans=0
    a=list(set(a))
    maxa=max(a)
    dp=[True for i in range(maxa+1)]
    for i in a:
        if dp[i] and adic[i]==1:ans+=1
        j=i+i
        while j<=maxa:
            dp[j]=False
            j+=i
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import collections


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

    A.sort()
    a_max = A[-1]
    dp = [True] * a_max
    r = 0
    sames = 0

    C = collections.Counter(A)
    for v in C.values():
        if v > 1:
            sames += 1

    A = set(A)

    for a in A:
        if dp[a - 1]:
            r += 1
            tmp_a = a
            while tmp_a < a_max + 1:
                tmp_a += a
                if tmp_a > a_max:
                    break
                else:
                    dp[tmp_a - 1] = False

    print(r - sames)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import collections


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

    A.sort()
    a_max = A[-1]
    dp = [True] * a_max
    r = 0
    sames = 0

    C = collections.Counter(A)
    for v in C.values():
        if v > 1:
            sames += v

    for a in A:
        if dp[a - 1]:
            r += 1
            tmp_a = a
            while tmp_a < a_max + 1:
                tmp_a += a
                if tmp_a > a_max:
                    break
                else:
                    dp[tmp_a - 1] = False

    print(r - sames)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

for elem in a:
    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: Wrong Answer

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 A.count(A[i])>=2:
      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: Wrong Answer

Solution code:
n=int(input())
A=sorted(map(int,input().split()))
L=[A[0]]
if n==1:
    print(1)
else:
    c=0
    if A[0]!=A[1]:
        c=1
    for i in range(n-1):
        #print(str(A[i+1])+'だよ')
        flag=0
        for l in L:
            #print(l)
            if A[i+1] in L:
                flag=1
                break
            if A[i+1]%l==0:
                #print(str(l)+'でわれちゃったから抜けるね')
                flag=1
                break
            if l>=int(A[i+1]**0.5+1):
                #print(str(l)+'おおきくなっちゃったから抜けるね')
                break
        if flag==0:
            L.append(A[i+1])
            c+=1
    print(c)
    #print(L)

Submission status: Wrong Answer

Solution code:
# def getDivisor(num):
#     divisors = []

#     for i in range(1, num + 1):
#         if num % i == 0:
#             divisors.append(i)

#     return divisors


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

#     A.sort()
#     B = [0] * 10**6
#     r = 0
#     sames = set()

#     A = set(A)

#     for a in A:
#         isAppendable = True
#         isSame = False
#         for p in getDivisor(a):
#             if B[p - 1] == 1:
#                 isAppendable = False
#                 break
#             if p == a and not (B[p - 1] == 2):
#                 sames.add(p)
#                 isSame = True

#         if isAppendable:
#             r += 1
#             if isSame:
#                 B[a - 1] = 2
#             else:
#                 B[a - 1] = 1

#     print(r)


# if __name__ == '__main__':
#     main()
import collections


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

    A.sort()
    a_max = A[-1]
    dp = [True] * a_max
    r = 0
    sames = 0

    C = collections.Counter(A)
    for v in C.values():
        if v > 1:
            sames += v

    for a in A:
        if dp[a - 1]:
            r += 1
            tmp_a = a
            while tmp_a < a_max + 1:
                tmp_a += a
                if tmp_a > a_max:
                    break
                else:
                    dp[tmp_a - 1] = False

    print(r - sames)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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: Wrong Answer

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    n=int(input())
    a=list(map(int,input().split()))
    a=list(set(a))
    a.sort()
    if len(a)==1:
        print(0)
        exit()
    ans=0
    maxa=max(a)
    dp=[True for i in range(maxa+1)]
    for i in a:
        if dp[i]:ans+=1
        j=i+i
        while j<=maxa:
            dp[j]=False
            j+=i
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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-2:
    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: Wrong Answer

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    n=int(input())
    a=list(map(int,input().split()))
    a=list(set(a))
    a.sort()
    if len(a)==1:
        print(0)
        exit()
    ans=0
    maxa=max(a)
    dp=[True for i in range(maxa+1)]
    for i in a:
        if dp[i]:
            ans+=1
            j=i+i
            while j<=maxa:
                dp[j]=False
                j+=i
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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 A[i]<=INF-2:
    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: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

n = int(input())
a = [int(x) for x in input().split()]
a.sort()
max_a = max(a)
is_True = [1]*(max_a + 1)
for i in a:
    if is_True[i]:
        for j in range(2*i, max_a + 1, i):
            is_True[j] = False
cnt = 0
for i in a:
    if is_True[i]:
        cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
a_list = list(map(int,input().split()))
a_list = sorted(a_list)
flag  = [0]*n


ans = 0
m = max(a_list)
b_list = [0]*(m+1)
for i in a_list:
    b_list[i] = 1
for i in a_list:
    if b_list[i] == 1:
        ans += 1
        
    for j in range(i , m+1 ,i):
        b_list[j]+= 1
print(ans)

Submission status: Wrong Answer

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 = []
remain = set()
for i in d:
	if d[i]==1:
		arr.append(i)
	else:
		remain.add(i)

arr.sort()

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

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

for i in arr:
	if ans[i]:
		for j in range(i*2,len(ans),i):
			ans[j]=0

tyo = 0

for i in remain:
	if ans[i]==1:
		tyo+=1

print(ans.count(1)-tyo)

Submission status: Wrong Answer

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 = 10**6+1
ans = [0]*(maxa+1)
for i in arr:
	ans[i]=1

for i in arr:
	if ans[i]:
		for j in range(i*2,len(ans),i):
			ans[j]=0

print(ans.count(1))

Submission status: Wrong Answer

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 = 10**6+1
ans = [0]*(maxa+1)
for i in arr:
	ans[i]=1

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

print(ans.count(1))

Submission status: Wrong Answer

Solution code:
import time
n = int(input())
a = list(map(int,input().split()))
a.sort(reverse=True)
uniq_a = set(a)

count = 0
for i in uniq_a:
  count-=(a.count(i)-1)


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

Submission status: Wrong Answer

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,len(ans),i):
		ans[j]=0

print(ans.count(1))

Submission status: Wrong Answer

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,len(arr),i):
		ans[j]=0

print(ans.count(1))

Submission status: Wrong Answer

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: Wrong Answer

Solution code:
d=[0]*8**7
for i in[*open(0)][1].split():d[int(i)]+=1
i=r=0
while i<1e6:
 i+=1;r+=d[i]==1;j=i
 while j<1e6:j+=i;d[j]&=d[i]<1
print(r)

Submission status: Wrong Answer

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

'''

'''

n = int(input())
a = list(map(int, input().split()))
largest = max(a)
#largest = arr[-1]
div = [1] * (largest+1)
count = 0
arr = []
# remove duplicates
for i, v in enumerate(a):
    if i < (n-1) and a[i+1] == v:
        div[v] = 0
    else:
        arr.append(v)

arr.sort()

for num in arr:
    if div[num]:
        count += 1

    for d in range(num, largest+1, num):
        div[d] = 0

print(count)

Submission status: Wrong Answer

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

'''

'''

n = int(input())
a = list(map(int, input().split()))
largest = max(a)
#largest = arr[-1]
div = [1] * (largest+1)
count = 0
arr = []
# remove duplicates
for i, v in enumerate(a):
    if i < (n-1) and a[i+1] == v:
        div[v] = 0
    else:
        arr.append(v)

arr.sort()

for num in arr:
    if div[num]:
        count += 1

    for d in range(2*num, largest+1, num):
        div[d] = 0

print(count)

Submission status: Wrong Answer

Solution code:
# D - Not Divisible
def main():
    N, *A = map(int, open(0).read().split())
    lim = max(A) + 1
    dp = [-1] * lim
    for a in A:
        dp[a] += 1
        if dp[a]:
            continue
        for i in range(a * 2, lim, a):
            dp[i] = 0
    print(sum(dp[a] == 0 for a in A))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N =input()
A = list(map(int, input().split()))
N=int(N)
s=0
A2 = [-1] #重複
LS =[-1]
for i in range(0,N):
  k=1
  P =A[i]
  if P in A2:
    pass
  else:
    while P*k<=10^6:
      LS.append(P*k)
      k+=1
    A2.append(P)
for j in range(0,N):
  if A[j] in A2:
    pass
  else:
    if LS.count(A[j]) ==1:
      s+=1
      
print(s)