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:
from collections import Counter
n = int(input())
A = list(map(int,input().split()))
lst = []
for k,v in Counter(A).items():
    if v==1:
        lst.append(k)
if len(lst)==0:
    print(0)
elif 1 in lst:
    print(1)
else:
    lst.sort()
    ans = 0
    mx = max(lst)+10
    er = [False] + [True]*mx
    for l in lst:
        if er[l]:
            ans += 1
            i = 0
            while True:
                er[i*l] = False
                i += 1
                if i*l > mx:
                    break
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
A = list(map(int,input().split()))
lst = []
for k,v in Counter(A).items():
    if v==1:
        lst.append(k)
if len(lst)==0:
    print(0)
elif 1 in lst:
    print(1)
else:
    lst.sort()
    ans = 0
    mx = max(lst)+1
    er = [False] + [True]*mx
    for l in lst:
        if er[l]:
            ans += 1
            i = 0
            while True:
                er[i*l] = False
                i += 1
                if i*l > mx:
                    break
    print(ans)

Submission status: Wrong Answer

Solution code:
#170D
def main():
    import sys
    #from collections import deque
    N = int(sys.stdin.readline())
    A = list(map(int, sys.stdin.readline().split()))
    A = list(set(A))
    A.sort()
    #A = deque(A)
    def era(A):
        if len(A)==1:
            print(0)
            return
        for i in range(len(A)):
            for j in range(len(A)-1, i, -1):
                if A[j] % A[i]==0:
                    #print(A[j], A[i])
                    A.pop(j)
        print(len(A))
                    
                
    
    era(A)


if __name__=='__main__':
    main()

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()
a.sort()

max_a = a[-1]
ans = [0]*(max_a+1)

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

print(ans.count(1))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = sorted(map(int, input().split()), reverse=True)
cnt = 0

if N == 1:
    print(1)
else:
  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: 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):
        a=A[i+1]
        flag=0
        for l in L:
            if a==L[-1]:
                flag=1
                break
            if a%l==0:
                flag=1
                break
        if flag==0:
            L.append(a)
            c+=1
    print(c)

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()
a.sort()

#max_a = 10**6
max_a = a[-1]
ans = [0]*(max_a+1)

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

print(ans.count(1))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = set(map(int, input().split()))
a_max = max(a)
lst = [0] * (a_max + 1)
cnt = 0

if len(a) <= 1:
    print(0)
else:
    for i in a:
        if lst[i] >= 2:  # 配列中のカウントが2以上なら以降の処理を省略
            continue
        else:
            for j in range(a_max // i + 1):  # Aiの倍数にインクリメント(配列の上限はa[-1])
                lst[i * j] += 1
    for i in a:
        if lst[i] == 1:
            cnt += 1
    print(cnt)

Submission status: Wrong Answer

Solution code:
#170D
def main():
    import sys
    #from collections import deque
    N = int(sys.stdin.readline())
    A = list(map(int, sys.stdin.readline().split()))
    A = list(set(A))
    A.sort()
    #A = deque(A)
    def era(A):
        if len(A)==1:
            print(0)
            return
        for i in range(len(A)):
            for j in range(len(A)-1, i, -1):
                if A[j] % A[i]==0:
                    #print(A[j], A[i])
                    A.pop(j)
        print(len(A))
                    
                
            
        
    
    era(A)




if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = set(map(int, input().split()))
a_max = max(a)
lst = [0] * (a_max + 1)
cnt = 0

if len(a) <= 1:
    print(0)
else:
    for i in a:
        if lst[i] >= 2:  # 配列中のカウントが2以上なら以降の処理を省略
            continue
        else:
            for j in range(1, a_max // i + 1):  # Aiの倍数にインクリメント(配列の上限はa[-1])
                lst[i * j] += 1
    for i in a:
        if lst[i] == 1:
            cnt += 1
    print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
Alist = list(map(int,input().split(" ")))
count = 0
while True:
    p = min(Alist)
    Alist = [i for i in Alist if i != p]
    if Alist == [] and count==0:
        break
    if p not in Alist:
        Alist = [i for i in Alist if i % p != 0]
        count += 1
    if Alist == []:
        break    
print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = set(map(int, input().split()))
a_max = max(a)
lst = [0] * (a_max + 1)
cnt = 0
if len(a) == 1:
    print(0)
else:
    for i in a:
        if lst[i] >= 2:  # 配列中のカウントが2以上なら以降の処理を省略
            continue
        else:
            for j in range(1, a_max// i + 1):  # Aiの倍数にインクリメント(配列の上限はa[-1])
                lst[i * j] += 1
    for i in a:
        if lst[i] == 1:
            cnt += 1
    print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = [int(i) for i in input().split()]
s = set(s)
for i in s:
	for j in s:
		if i == j or i%j == 0:
			s.remove(i)
			s.add(-i)
			break
l = [i for i in s if i >= 0]
print(len(l))

Submission status: Wrong Answer

Solution code:
N=input()
A=sorted(map(int,input().split()))
M=A[-1]+1
B=[0]*M
for i in A:
  for j in range(i,M,i):
    B[j]+=1
print(B.count(1))

Submission status: Wrong Answer

Solution code:
import itertools
import collections
from functools import lru_cache

import sys
input = sys.stdin.readline
LOCAL = len(sys.argv) > 1 and sys.argv[1] == 'LOCAL'


def dprint(*args):
  if LOCAL:
    print(*args)


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


# https://note.nkmk.me/python-prime-factorization/

@lru_cache(maxsize=None)
def prime_factorize(n):
  a = []
  while n % 2 == 0:
    a.append(2)
    n //= 2
  f = 3
  while f * f <= n:
    if n % f == 0:
      a.append(f)
      n //= f
    else:
      f += 2
  if n != 1:
    a.append(n)
  return a

a.sort()

if 1 in a:
  for i, e in enumerate(a):
    if e != 1:
      break
  if i == 1:
    print(1)
  else:
    print(0)
  
  # print(int(a.count(1)==1))
  exit()

# a=set(a)

dprint('a', '=', a)

p = {tuple(prime_factorize(e)) for e in a}

# p.sort()

dprint('p', '=', p)

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

ans = 0
for e in a:
  f = tuple(prime_factorize(e))
  dprint('f', '=', f)
  # if len(f) == 1:
  #   ans += 1
  #   dprint('ans++', f)
  #   continue
  valid = True
  for r in range(1, len(f) + 1):
    dprint('r', '=', r)
    for com in itertools.combinations(f, r=r):
      dprint(com)
      if com == f:
        continue
      # if p[bisect.bisect_left(p, com)] == com:
      if com in p:
        valid = False
  if valid:
    ans += 1
    dprint('ans++', f)

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = [int(i) for i in input().split()]
s = set(s)
for i in s:
	for j in s:
		if i == j or i%j == 0:
			s.remove(i)
			s.add(-i)
			break
l = [i for i in s if i >= 0]

Submission status: Wrong Answer

Solution code:
#import sys
#import numpy as np
import math
#import itertools
#from fractions import Fraction
#import itertools
from collections import deque
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
#import bisect
n=int(input())
if n==1:
  print(1)
  exit()
a=list(map(int,input().split()))
a.sort()
m=max(a)
a=set(a)
d=[0]*m
for i in a:
    if d[i-1]==1:
        continue
    for j in range(2,m+1):
        if i*j>m:
            break
        d[i*j-1]=1
ans=len(a)
if ans==1:
  print(0)
  exit()
for i in a:
    if d[i-1]==1:
        ans-=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()
a.sort()

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

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

print(ans.count(1))

Submission status: Wrong Answer

Solution code:
#import sys
#import numpy as np
import math
#import itertools
#from fractions import Fraction
#import itertools
from collections import deque
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
#import bisect
n=int(input())
a=list(map(int,input().split()))
m=max(a)
a=set(a)
d=[0]*m
for i in a:
    if d[i-1]==1:
        continue
    for j in range(2,m+1):
        if i*j>m:
            break
        d[i*j-1]=1
ans=len(a)
for i in a:
    if d[i-1]==1:
        ans-=1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = input()
A = A.split(' ')

total = 0
for i in range(N):
    chk = -1
    for j in range(N):
        if (i != j) and (int(A[i]) % int(A[j]) == 0):
            chk = 1
            print(A[i], A[j])
            break
        else:
            continue
        break

    if chk == 1:
        total += 1
print(N - total)

Submission status: Wrong Answer

Solution code:
import itertools
import collections

import sys
input = sys.stdin.readline
LOCAL = len(sys.argv) > 1 and sys.argv[1] == 'LOCAL'


def dprint(*args):
  if LOCAL:
    print(*args)


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


# https://note.nkmk.me/python-prime-factorization/


def prime_factorize(n):
  a = []
  while n % 2 == 0:
    a.append(2)
    n //= 2
  f = 3
  while f * f <= n:
    if n % f == 0:
      a.append(f)
      n //= f
    else:
      f += 2
  if n != 1:
    a.append(n)
  return a


if 1 in a:
  if a.count(1) == 1:
    print(1)
  else:
    print(0)
  # print(int(a.count(1)==1))
  exit()

# a = [k for k, v in collections.Counter(a).items() if v == 1]

dprint('a', '=', a)

p = {tuple(prime_factorize(e)) for e in a}

# p.sort()

dprint('p', '=', p)

ans = 0
for f in p:
  dprint('f', '=', f)
  if len(f) == 1:
    ans += 1
    dprint('ans++', f)
    continue
  valid = True
  for r in range(1, len(f)):
    dprint('r', '=', r)
    for com in itertools.combinations(f, r=r):
      dprint(com)
      # if p[bisect.bisect_left(p, com)] == com:
      if com in p:
        valid = False
  if valid:
    ans += 1
    dprint('ans++', f)

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import itertools
import collections

import sys
input = sys.stdin.readline
LOCAL = len(sys.argv) > 1 and sys.argv[1] == 'LOCAL'


def dprint(*args):
  if LOCAL:
    print(*args)


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


# https://note.nkmk.me/python-prime-factorization/


def prime_factorize(n):
  a = []
  while n % 2 == 0:
    a.append(2)
    n //= 2
  f = 3
  while f * f <= n:
    if n % f == 0:
      a.append(f)
      n //= f
    else:
      f += 2
  if n != 1:
    a.append(n)
  return a


if 1 in a:
  if a.count(1) == 1:
    print(1)
  else:
    print(0)
  # print(int(a.count(1)))
  exit()

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

dprint('a', '=', a)

p = {tuple(prime_factorize(e)) for e in a}

# p.sort()

dprint('p', '=', p)

ans = 0
for f in p:
  dprint('f', '=', f)
  if len(f) == 1:
    ans += 1
    dprint('ans++', f)
    continue
  valid = True
  for r in range(1, len(f)):
    dprint('r', '=', r)
    for com in itertools.combinations(f, r=r):
      dprint(com)
      # if p[bisect.bisect_left(p, com)] == com:
      if com in p:
        valid = False
  if valid:
    ans += 1
    dprint('ans++', f)

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

All = set(A)
count, ans = 0, 0

for i in A:
    division = [i]
    split = All - set(division)
    count = 0
    for j in split:
        if(i % int(j) != 0):
            count = count + 1
            if(count == len(split)):
                ans = ans + 1
                break
print(ans)

Submission status: Wrong Answer

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

All = set(A)
count, ans = 0, 0

for i in A:
    division = [i]
    split = All - set(division)
    count = 0
    for j in split:
        if(i % int(j) != 0):
            count = count + 1
            if(count == len(split)):
                ans = ans + 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()
a.sort()

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

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

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

print(ans.count(1))

Submission status: Wrong Answer

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

All = set(A)
count, ans = 0, 0

for i in A:
    division = [i]
    split = All - set(division)
    count = 0
    for j in split:
        if(i % int(j) != 0 and i != int(j)):
            count = count + 1
            if(count == len(split)):
                ans = ans + 1

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
A=list(map(int,input().split()))
A.sort()
t=0
e=[True]*1000001
for i in range(n-1):
    if A[i] == A[i+1]:
        e[A[i]]=False
for a in A:
    if e[a]==False:
        continue
    b=a*2
    while b < 1000001:
        e[b]=False
        b+=a
for a in A:
    if e[a]:
        t+=1
print(t)

Submission status: Wrong Answer

Solution code:
#import sys
#import numpy as np
import math
#import itertools
#from fractions import Fraction
#import itertools
from collections import deque
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
#import bisect
n=int(input())
if n==1:
  print(1)
  exit()
a=list(map(int,input().split()))
m=max(a)
d=[0]*m
for i in a:
    for j in range(2,m+1):
        if i*j>m:
            break
        d[i*j-1]=1
a=set(a)
ans=len(a)
if ans==1:
  print(0)
  exit()
for i in a:
    if d[i-1]==1:
        ans-=1
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
import collections

import sys
input = sys.stdin.readline
LOCAL = len(sys.argv) > 1 and sys.argv[1] == 'LOCAL'


def dprint(*args):
  if LOCAL:
    print(*args)


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


# https://note.nkmk.me/python-prime-factorization/


def prime_factorize(n):
  a = []
  while n % 2 == 0:
    a.append(2)
    n //= 2
  f = 3
  while f * f <= n:
    if n % f == 0:
      a.append(f)
      n //= f
    else:
      f += 2
  if n != 1:
    a.append(n)
  return a

if 1 in a:
  if a.count(1) == 1:
    print(1)
  else:
    print(0)
  # print(int(a.count(1)))
  exit()

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

dprint('a', '=', a)

p = {tuple(prime_factorize(e)) for e in a}

# p.sort()

dprint('p', '=', p)

ans = 0
for f in p:
  dprint('f', '=', f)
  if len(f) == 1:
    ans += 1
    dprint('ans++', f)
    continue
  valid = True
  for r in range(1, len(f) + 1):
    dprint('r', '=', r)
    for com in itertools.combinations(f, r=r):
      dprint(com)
      # if p[bisect.bisect_left(p, com)] == com:
      if com == f:
        continue
      if com in p:
        valid = False
  if valid:
    ans += 1
    dprint('ans++', f)

print(ans)

Submission status: Wrong Answer

Solution code:
#import sys
#import numpy as np
import math
#import itertools
#from fractions import Fraction
#import itertools
from collections import deque
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
#import bisect
n=int(input())
if n==1:
  print(1)
  exit()
a=list(map(int,input().split()))
m=max(a)
d=[0]*m
for i in a:
    for j in range(2,m+1):
        if i*j>m:
            break
        d[i*j-1]=1
a=set(a)
ans=len(a)
if ans==1:
  print(0)
  exit()
for i in a:
    if d[i-1]==1:
        ans-=1
print(ans)
print(d)

Submission status: Wrong Answer

Solution code:
n=int(input())
A=list(map(int,input().split()))
Q=[True]*n
A.sort()
t=0
e=[True]*1000001
for i in range(n-1):
    if A[i] == A[i+1]:
        e[A[i]]=False
for a in A:
    if e[a]==False:
        continue
    b=a*2
    while b < 1000001:
        e[b]=False
        b+=a
for a in A:
    if e[a]:
        t+=1
print(t)

Submission status: Wrong Answer

Solution code:
import itertools
import collections

import sys
input = sys.stdin.readline
LOCAL = len(sys.argv) > 1 and sys.argv[1] == 'LOCAL'


def dprint(*args):
  if LOCAL:
    print(*args)


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


# https://note.nkmk.me/python-prime-factorization/


def prime_factorize(n):
  a = []
  while n % 2 == 0:
    a.append(2)
    n //= 2
  f = 3
  while f * f <= n:
    if n % f == 0:
      a.append(f)
      n //= f
    else:
      f += 2
  if n != 1:
    a.append(n)
  return a


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

dprint('a', '=', a)

p = {tuple(prime_factorize(e)) for e in a}

# p.sort()

dprint('p', '=', p)

ans = 0
for f in p:
  dprint('f', '=', f)
  if len(f) == 1:
    ans += 1
    dprint('ans++', f)
    continue
  valid = True
  for r in range(1, len(f) + 1):
    dprint('r', '=', r)
    for com in itertools.combinations(f, r=r):
      dprint(com)
      # if p[bisect.bisect_left(p, com)] == com:
      if com == f:
        continue
      if com in p:
        valid = False
  if valid:
    ans += 1
    dprint('ans++', f)

print(ans)

Submission status: Wrong Answer

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

dp = [0]*(10**6)
count = [0]*(10**6)
for i in a:
  count[i-1] += 1
  for j in range(i*2, 10**6, i):
    dp[j-1] = 1
ans = 0

for i in a:
  if count[i-1] == 1 and dp[i-1] == 0:
    ans +=1
    
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

dp = [False] * (A[-1] + 1)
for a in A:
    dp[a] = True

for idx, a in enumerate(A):
    if idx == 0:
        continue
    if A[idx] == A[idx - 1]:
        dp[a] = False
    for j in range(2, A[-1]//a + 1):
        dp[a * j] = False

count = 0
for d in dp:
    if d:
        count += 1
print(count)