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:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
a=list(map(int,input().split()))
# n=10**5
# a=[i for i in range(2,10**5+2)]
# print(len(a))
a.sort()
cnt=Counter(a)
p=set()
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

for i in range(n):
    if cnt[a[i]]!=1:
        continue
    tmp=make_divisors(a[i])
    for j in tmp:
        if j in p:
            break
    else:
        p.add(a[i])
print(len(p))

Submission status: Wrong Answer

Solution code:
import math

def isPrime(n):
  if n == 1:
    return False
  for k in range(2, int(math.sqrt(n)) + 1):
    if n % k == 0:
      return False
  return True

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

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

if A[0] == 1 and A[1] == 1:
  print(0)
  exit()
if A[0] == 1 and A[1] != 1:
  print(1)
  exit()

for i in range(N):
  x = A[i]
  if isPrime(x):
    if i - 1 >= 0:
      if x == A[i - 1]:
        cnt -= 1
        continue
    if i + 1 < N:
      if x == A[i + 1]:
        cnt -= 1
        continue
    continue
    
  for j in range(i):
    y = A[j]
    if x % y == 0:
      cnt -= 1
      break
print(cnt)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import math
 
def is_prime(n):
    if n == 1: return False
 
    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
 
    return True
  
N= int(input())
A = input().split()
ANS = 0
for i in range(N):
  C = A[i]
  if A.count(C) == 1:
    if is_prime(i) == True:
      ANS += 1
print(ANS)

Submission status: Wrong Answer

Solution code:
FAST_IO = 0
if FAST_IO:
    import io, sys, atexit
    read = iter(sys.stdin.read().splitlines()).next
    sys.stdout = _OUTPUT_BUFFER = io.BytesIO()
    @atexit.register
    def write():
        sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
else:
    read = raw_input
readint = lambda: int(read())
readlist = lambda: map(int, read().split())

####
from collections import Counter
def solve(N, A):
    MAXV = 10 ** 6
    count = Counter(A)
    touch = [False] * (MAXV + 1)
    ans = 0
    for x in sorted(count):
        if count[x] == 1 and not touch[x]:
            ans += 1
            for y in xrange(2 * x, MAXV + 1, x):
                touch[y] = True
    return ans
            
    

print solve(readint(), readlist())

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
ok=[0]*(a[-1]+1)
for i in range(n):
  ok[a[i]]+=1
for i in range(n):
  if ok[a[i]]>1:
    ok[a[i]]=0
  elif ok[a[i]]:
    j=a[i]
    while 1:
      j += a[i]
      if j > a[-1]:
        break
      ok[j]=0
    
print(sum(ok))

Submission status: Wrong Answer

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

exist_in_input = [0 for _ in range(10**6 + 1)]
if_can_divide = [0 for _ in range(10**6 + 1)]

counter = 0
for i in range(1, 10**6+1):
    if exist_in_input[i] == 0:
        continue

    if if_can_divide[i] == 1:
        continue
    else:
        counter += 1

    for j in range((10**6+1) // (i + 1)):
        if_can_divide[j*i] = 1

print(counter)

Submission status: Wrong Answer

Solution code:
N  =int(input())
X = [int(i) for i in input().split()]
Y = sorted(X)
count=0
# print(Y)
ANS=[]
for i in  range(N):
    for j in range(N):
        if Y[i]!=Y[j]:
            if Y[i]%Y[j]==0:
                if Y[i] not in ANS:
                    ANS.append(Y[i])
                    # print("i",Y[i])
                    # print("j",Y[j])
                # ANS.append(Y[j])
         
for i in range(len(ANS)):
    if ANS[i] in Y:
        # print(ANS)
        count=count+1

print(count)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict

def get_prime_factors(n):
    dd = defaultdict(lambda: 0)
    if n > 1:
        i = 2
        while i * i <= n:
            if n % i == 0:
                dd[i] += 1
                n /= i
                i = 2
            else:
                i += 1
        dd[n] += 1
    return dd

def factor_with(n, A):
    idx = 0
    orig_n = n
    i = A[idx]

    while i * i <= n or idx >= len(A):
        i = A[idx]

        if A[idx] == orig_n:
            idx+= 1
        elif n % i ==0:
            n /= i
            idx = 0
        else:
            idx += 1
    return n

    
def solve(N: int, A: "List[int]"):
    
    A = sorted(list(A))
    
    count = 0
    divs = []
    for i in range(len(A)):
        f = True

        if i + 1 < len(A):
            if A[i-1] == A[i] or A[i] == A[i+1]:
                continue
        else:
            if A[i-1] == A[i]:
                continue
               

        for div in divs:
            if A[i] % div == 0:
                f = False
                break
        if f:
            divs.append(A[i])

    count = len(divs)

        
    # dd = defaultdict(lambda: (0, 10**6+1))
    
    # for a in A:
    #     d = get_prime_factors(a)

    #     flag = True
    #     for prime, value in d.items():
    #         dd_val, dd_mn = dd[prime]
            
    #         if a % dd_mn==0:
    #             flag = False
    #             break

    #         dd[prime] = (dd_val + value, min(dd_mn, a))

    #     if flag:
    #         count+= 1

    print(count)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main1():
    N=int(input())
    A=list(map(int,input().split()))
    A.sort()
    ans=[0]*(10**6)
    for i in  range(len(A)-1):
        if ans[i]>=2:
            continue
        if A[i]!=A[i+1]:
            ans[i]+=1
        for j in range(A[i]*2,10**6,A[i]):
                ans[j]=2
    print(ans.count(1))
main1()

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
#n=2*10**5
#a=[i+2 for i in range(0,n)]
a.sort()
aa={}
for i in range(0,a[-1]+1):
  aa[i]=0
if a[0]==a[n-1]:
  print(0)
elif a[0]==1:
  print(1)
else:
  ans=0
  while len(a)!=1:
    now=a.pop(0)
    if aa[now]==0:
      ans+=1
      new=0+now
      while a[-1]>=now:
        aa[now]=1
        now+=new
  if aa[a[0]]==0:
    ans+=1
  print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split(" ")))
c = 0
A = sorted(A)
for i in range(N):
  judge = True
  for j in range(i):
    if A[i]%A[j] == 0:
      judge = False
      break
  if judge:
    c += 1
print(c)

Submission status: Wrong Answer

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

A = sorted(A)[::-1]
A_lst = []
A_flug = dict()
for i, value in enumerate(A):
    if i == 0:
        A_flug[value] = False
        A_lst.append(value)
    else:
        if A_lst[-1] != value:
            A_flug[value] = False
            A_lst.append(value)
        else:
            A_flug[value] = True

# print(A_lst)
ans = 0
for i, value in enumerate(A_lst):
    if A_flug[value]:
        continue
    else:
        flug = True
        for j in range(2, value):
            if j in A_flug:
                if j ** 2 > value:
                    break
                else:
                    if value % j == 0:
                        flug = False
                        break
            else:
                if j ** 2 > value:
                    break
                else:
                    if value % j == 0:
                        if value // j in A_flug:
                            flug = False
    #         print(i, value, j, flug)
    # print(i, value, flug)
    if flug: ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import Counter
def input():
    return sys.stdin.readline()[:-1]
def main():
    N = int(input())
    A = sorted(list(map(int,input().split())))
    U = [0]*(max(A)+1)
    for e in A:
        U[e] += 1
    ans = 0
    for e in A:
        if U[e] == 1:
            f = 1
            for k in range(2,math.floor(math.sqrt(e))+1):
                if e % k == 0:
                    if U[k] >= 1 or U[e//k] >= 1:
                        f = 0
                        break
            if f == 1:
                ans += 1
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#D
import collections
n=int(input())
a_list=list(map(int,input().split()))
a_list=collections.Counter(a_list)
a_list=[a_list.keys()]
a_list.sort()
j_list=[a_list[0]]
if len(a_list)==1:
    ans=0
elif 1 in a_list:
    ans=1
else:
    ans=1
    for i in a_list:
        for j in j_list:
            if i%j ==0:
                break
        else:
            ans+=1
            j_list.append(i)
            #print(i)
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
n=int(input())
As=list(map(int, stdin.readline().split()))
As.sort()
primes=[]
answers=[]


primes.append(100003)
# answers.append(As[0])
# for a in As:
#     if a > 1:     
#         primes.append(a)
#         break
last=0


found=True

for a in As:
    if last == a:
        if found == False:
            answers.pop(-1)
        last=a
        found=True
        continue

    for p in primes:
        if a % p == 0 :
            found=True
            break
        else:
            found=False

    if found==False:
        if a!=1:
            primes.append(a)
        answers.append(a)
        last=a

    else:
        last=a

print (len(answers))

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
a=list(map(int,input().split()))
# n=10**5
# a=[i for i in range(2,10**5+2)]
# print(len(a))
a.sort()
cnt=Counter(a)
p=set()
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

for i in range(n):
    if cnt[a[i]]!=1:
        continue
    tmp=make_divisors(a[i])
    for j in tmp:
        if j in p:
            break
    else:
        p.add(a[i])
print(len(p))

Submission status: Wrong Answer

Solution code:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

num = 10 ** 6 + 1 #適当に値を入れる
L = [0 for i in range(num)]
ans = 0
N = int(input())
A = getlist()
for i in range(N):
	L[A[i]] += 1

for i in range(10 ** 6 + 1):
	if L[i] >= 2:
		L[i] = 0

for i in range(num):
	if L[i] == 1:
		ans += 1 ; c = 2
		while i * c <= num - 1:
			L[i * c] = 0; c += 1

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    A = sorted(A)
    if N > 1 and A[0] != A[1]:
        cnt = 1
    elif N == 1:
        cnt = 1
    else: 
        cnt = 0
    
    for i in range(1, len(A)):
        for j in range(0, i):
            if A[i] % A[j] == 0:
                break 
            if A[j] > int(A[i]**0.5):
                cnt += 1
                break 
        else:
            cnt += 1


    print(cnt)

    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# D - Not Divisible
import numpy as np
from collections import Counter

N = int(input())
A = list(int(a) for a in input().split())
c = Counter(A)
ng = set([i[0] for i in c.items() if i[1] >= 2])

A.sort()
A = np.array(A)
Ac = np.copy(A)
ans = 0
for i in range(N):
    if Ac[i] == 0:
        continue
    elif A[i] not in ng:
        ans += 1
    cur = A[i]
    while cur <= 10**6:
        ng.add(cur)
        cur += cur

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline
    from collections import Counter

    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    counter_A = Counter(A)
    flag = [True] * 1000001

    count = 0
    for i in A:
        if counter_A[i] > 1:
            continue
        if flag[i]:
            count += 1
        multiple = i
        while multiple < 1000001:
            flag[multiple] = False
            multiple += i

    print(count)


main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

a = list(set(a))
a = sorted(a)
dic = defaultdict(lambda: False)

n = len(a)
count = 0 

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


for i in range(n):
    ai = a[i]
    if dic[ai]:
        count+=1
    else:
        for j in range(1,a[n-1]):
            dic[j*ai] = True
print(n-count)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def main(N, a):
    a.sort()
    if a[0] == 1:
        if len(a) > 1:
            if a[1] == 1:
                return 0
        return 1
    i = 0
    while True:
        num = a[0]
        if 2 > len(a):
            return len(a)+i
        while True:
            if num == a[1]:
                a = [i for i in a if i != num]
                if 2 > len(a):
                    return len(a)+i
                num = a[0]
            else:
                break
        if num*2 > a[len(a)-1]:
            a = [i for i in a if i % num != 0]
            return len(a)+i+1
        a = [i for i in a if i % num != 0]
        i = i+1


N = int(input())
a = list(map(int, input().split()))
print(main(N, a))

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()
maxa = max(a)+1
d = defaultdict(int)
for i in a:
	d[i]+=1
tmp = []
for i in d:
	if d[i]==1:
		tmp.append(i)
a = tmp[:]



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



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

print(ans.count(1))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
#N, K = map(int, input().split())
# 文字列の入力
N = int(input())
#開業されたN個要素を受け付ける
A_list = list(map(int, input().split()))
sorted_A_list = sorted(A_list)

ans = 0

#print(sorted_A_list)

for i in range(N):
    ans = ans+1
    if not i == N-1:
        if sorted_A_list[i] == sorted_A_list[i+1]:
            ans = ans-1
            continue
    for j in range(i):
        if sorted_A_list[i]/2 < sorted_A_list[j]:
            break
        if sorted_A_list[i]%sorted_A_list[j] == 0:
            ans = ans-1
            #print(sorted_A_list[i])
            break

print(ans)

Submission status: Wrong Answer

Solution code:
#D
import collections
n=int(input())
a_list=list(map(int,input().split()))
a_list.sort()
a_list=collections.Counter(a_list)
a_list=[a_list.keys()]
j_list=[a_list[0]]
if len(a_list)==1:
    ans=0
elif 1 in a_list:
    ans=1
else:
    ans=1
    for i in a_list:
        for j in j_list:
            if i%j ==0:
                break
        else:
            ans+=1
            j_list.append(i)
            #print(i)
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
A=sorted(A)
B=A[::-1]
# if Counter(A)[A[0]]>1:
#     ans=0
# else:
#     ans=1
#     print(1)
ans=0
for i in range(N):
    for j in range(N-i-1):
        if i!=N-j-1 and B[i]%A[j]==0:
            break
    else:
        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()
maxa = max(a)+1
d = defaultdict(int)
for i in a:
	d[i]+=1
tmp = []
for i in d:
	if d[i]==1:
		tmp.append(i)
a = tmp[:]

print(a)


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



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

print(ans.count(1))

Submission status: Wrong Answer

Solution code:
if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))

    a.sort()

    count = 0
    for ite1, i in enumerate(a):
        b = [_ for _ in a if _ < i]
        for ite2, j in enumerate(b):
            if i%j == 0:
                break
            elif ite2 == len(b)-1:
                count += 1

    if len(a) > 0 and len(set(a))!=1:
        count += 1

    print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split(" ")))
c = 0
A = sorted(A)
judge = True
for i in range(N):
  for j in range(i):
    if A[i]%A[j] == 0:
      judge = False
  if judge:
    c += 1
print(c)

Submission status: Wrong Answer

Solution code:
N = input()
A=list(map(int,input().split()))
B=list(set(A))
C= sorted(B,reverse=True)
l = len(C)
cho = [0] * l
for i in range(l):
    cho[i] = A.count(C[i])

flg = [0] * l

if l == 1:
    print(0)
    exit()



for i in range(l):
    for j in range(l):
        if i != j and C[i] % C[j] == 0:
            flg[i] = 1


for i in range(l):
    if cho[i] > 1:
        flg[i] = 1

cnt = flg.count(0)

print(cnt)

Submission status: Wrong Answer

Solution code:
#D
import collections
n=int(input())
a_list=list(map(int,input().split()))
a_list.sort()
a_list=collections.Counter(a_list)
a_list=[a_list.keys()]
j_list=[a_list[0]]
if len(a_list)==1:
    ans=0
elif 1 in a_list:
    ans=1
else:
    ans=1
    if a_list[0]==a_list[1]:
        ans-=1
    for i in a_list:
        for j in j_list:
            
            if i in j_list:
                break
            if i%j ==0:
                break
        else:
            ans+=1
            j_list.append(i)
            #print(i)
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict

def get_prime_factors(n):
    dd = defaultdict(lambda: 0)
    if n > 1:
        i = 2
        while i * i <= n:
            if n % i == 0:
                dd[i] += 1
                n /= i
                i = 2
            else:
                i += 1
        dd[n] += 1
    return dd

def factor_with(n, A):
    idx = 0
    orig_n = n
    i = A[idx]

    while i * i <= n or idx >= len(A):
        i = A[idx]

        if A[idx] == orig_n:
            idx+= 1
        elif n % i ==0:
            n /= i
            idx = 0
        else:
            idx += 1
    return n

    
def solve(N: int, A: "List[int]"):
    
    A = sorted(list(A))
    A = [a for a in A if a != 1]
    if len(A) <= 1:
        print(0)
        return
    
    count = 0
    divs = []
    for i in range(len(A)):
        f = True

        if i + 1 < len(A):
            if A[i-1] == A[i] or A[i] == A[i+1]:
                continue
        else:
            if A[i-1] == A[i]:
                continue
               

        for div in divs:
            if A[i] % div == 0:
                f = False
                break
        if f:
            divs.append(A[i])

    count = len(divs)

        
    # dd = defaultdict(lambda: (0, 10**6+1))
    
    # for a in A:
    #     d = get_prime_factors(a)

    #     flag = True
    #     for prime, value in d.items():
    #         dd_val, dd_mn = dd[prime]
            
    #         if a % dd_mn==0:
    #             flag = False
    #             break

    #         dd[prime] = (dd_val + value, min(dd_mn, a))

    #     if flag:
    #         count+= 1

    print(count)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
pi = [int(i) for i in input().split()]

res = {}

sorted_p = sorted(pi)
for p in sorted_p:
    flag = True
    for div in res.keys():
        if p == div:
            flag = False
            res.pop(p)
            break
        elif div > (p/2):
            break
        elif p % div == 0:
            flag = False
            break
    if flag:
        res[p] = 1

res_count = 0
if N == 1:
    res_count = 1
elif len(res) != 1:
    for v in res.values():
        res_count += v

print(res_count)

Submission status: Wrong Answer

Solution code:
import math
import sys
import itertools
from math import gcd
from math import sqrt
from sys import stdin
def input() : return stdin.readline().rstrip()
def mips():
    return map(int,input().split())
def ii():
    return int(input())
sys.setrecursionlimit(10**9)

def is_prime(n):
   if n == 1:
       return False
   i = 2
   while i*i <= n:
       if n % i == 0:
           return False
       i += 1
   return True
def factorization(n):
   arr = []
   temp = n
   for i in range(2, int(-(-n**0.5//1))+1):
       if temp%i==0:
           cnt=0
           while temp%i==0:
               cnt+=1
               temp //= i
           arr.append(i**cnt)
   if temp!=1:
       arr.append(temp)
   if arr==[]:
       arr.append(n)
   arr.append(n)
   return arr
import copy
N = ii()
A = [el for el in mips()]
ans = N
L = [0 for _ in range(max(A)+1)]
Table = dict()
for el in A:
    q = set(factorization(el))
    L[el] = list(q)
for el in A:
    New = copy.deepcopy(L)
    New[el] = 0
    New = list(filter((0).__ne__, New))
    P = sum(New,[])
    if [c for c in P if c in L[el]] != []:
        ans -= 1
print(ans + 1)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
a.sort()
ng = [0] * 2000000
ans = 0
for i in a:
    for j in range(1, 200000//i):
        ng[i*j] += 1
for i in a:
    if ng[i]==1:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

import math

def is_prime(n): # O(sqrt(N))
    if n == 1: return False
    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True

def count_num(n, l):
    cnt = 1
    for i in range(1, len(l)):
        if l[i] != n:
            return cnt
        cnt += 1
    return cnt

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr

ans = 0
i = 0
while i < N:
    cnt_n = count_num(A[i], A[i:])
    if cnt_n != 1:
        i += cnt_n
        continue
    if A[i] == 1 or is_prime(A[i]):
        ans += 1
        # print('+1:', A[i])
        i += 1
        continue
    
    # not prime
    # flag = True
    # for num in A[:i]:
    #     if math.gcd(num, A[i]) != 1:
    #         i += 1
    #         flag = False
    #         break
    # judge
    flag = True
    for num in A[:i]:
        if A[i] % num == 0:
            flag = False

    if flag:
        # print("+1. x:", A[i])
        ans += 1
    i += 1

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline
    from collections import Counter

    N = int(input())
    A = list(map(int, input().split()))
    counter_A = Counter(A)
    flag = [True] * 1000001

    count = 0
    for i in sorted(counter_A.keys()):
        if counter_A[i] > 1:
            continue
        if flag[i]:
            count += 1
        multiple = i
        while multiple < 1000001:
            flag[multiple] = False
            multiple += i
            
    print(count)


main()