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 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)]; L[0] = 0; L[1] = 0
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 += L[i] ; c = 2
		while i * c <= num - 1:
			L[i * c] = 0; c += 1


print(ans)

Submission status: Wrong Answer

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

while len(a) > 2:
    if a[0] % a[1] == 0:
        a.pop(0)
    else:
        break

if len(a) == 2:
    if a[0] % a[1] == 0:
        print("0")
        exit()
    elif a[1] % a[0] == 0:
        print("1")
        exit()

idx = 0
for i in a:
    tmp = 0
    for j in range(idx+1,len(a)):
        if a[j-tmp] % i == 0:
            a.pop(j-tmp)
            tmp += 1
    idx += 1

print(len(a))

Submission status: Wrong Answer

Solution code:
from collections import Counter
# from numba import jit

def main():
    n = int(input().strip())
    L = list(map(int, input().strip().split()))
    seen = Counter()
    # ans=0
    
    for x in L:
        seen[x]+=1
    
    def loop():
        ans=0
        for x in L:
            if seen[x]>1 or x!=1 and 1 in seen:
                continue
        
            tmp=2
            while tmp**2<=x:
                if x%tmp and (tmp in seen or x/tmp in seen):
                    break
                tmp+=1
            else:
                ans+=1
        return ans
    print(loop())
if '__main__' == __name__:
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter

input()
c = Counter(map(int, input().split()))
r = 0
for k, v in c.items():
  if v == 1:
    i = 1
    while i * i <= k:
      if k % i == 0 and  (i in c or k // i in c):
        break
      i += 1
    else:
      r += 1
print(r)

Submission status: Wrong Answer

Solution code:
N = int(input())
AList = list(map(int, input().split()))
if AList.count(AList[0]) == N:
  print(0)
  exit()
ansList = []
while AList:
  minNum = min(AList)
  ansList.append(minNum)
  AList = list(filter(lambda X: X % minNum != 0, AList))
print(len(ansList))

Submission status: Wrong Answer

Solution code:
import copy
n = int(input())
a = list(map(int,input().split()))
a.sort()
b = a.copy()
test = [i for i in range(1,n)]
if n > 1:
    if a[0] == a[1]:
        b[0] = 0 

for i in range(n):
    for j in test:
        if b[j] % a[i] == 0:
            b[j] = 0
            test.remove(j)
    if test.count(i+1) != 0:
        test.remove(i+1)


print(n - b.count(0))

Submission status: Wrong Answer

Solution code:
import sys
import heapq

ri = lambda: int(sys.stdin.readline())
rl = lambda: list(map(int, sys.stdin.readline().split()))

def heapsort(iterable):
  h = []
  for value in iterable:
    heapq.heappush(h, value)
  l = []
  for _ in range(len(h)):
    l.append(heapq.heappop(h))
  return l

n = ri()
li = rl()
dic = {}
for w in li:
    if w in dic:
        dic[w] += 1
    else:
        dic[w] = 1
li1 = []
li2 = []
for k, v in dic.items():
    if v > 1:
        li1.append(k)
    else:
        li2.append(k)
li1 = heapsort(li1)
li2 = heapsort(li2)
le1 = len(li1)
le2 = len(li2)
cnt = 0
for i in range(le2):
    li2i = li2[i]
    flag = 0
    for j in range(i):
        li2j = li2[j]
        if li2j > li2i**0.5:
            for k in range(le1):
                li1k = li1[k]
                if li1k > li2i**0.5:
                    flag = 1
                    break
                if li2i % li1k == 0:
                    break
            else:
                flag = 1
            break
        if li2i % li2j == 0:
            break
    else:
        for k in range(le1):
            li1k = li1[k]
            if li1k > li2i**0.5:
                flag = 1
                break
            if li2i % li1k == 0:
                break
        else:
            flag = 1
    if flag:
        cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
divs = [a[0]]
idx=1
v = a[0]
while v<10**3 and idx<n:
  if all([a[idx]%d!=0 for d in divs]):
    divs.append(a[idx])
  v = a[idx]
  idx += 1
ans = 0
for i in range(n):
  if all(a[i]!=d and a[i]%d!=0 for d in divs):
    ans += 1
if len(divs)==1:
  print(0)
else:
  print(ans+len(divs))

Submission status: Wrong Answer

Solution code:
import math
import collections
n = int(input())
a = [int(i) for i in input().split()]
dic = collections.defaultdict(int)
for i in range(n):
    dic[a[i]] += 1
a = [i for i in dic.keys() if dic[i] == 1]
a.sort()

ls = [0] * (10**6)
for i in range(len(a)):
    tmp = a[i]
    cnt = 2
    while True:
        tmp = a[i] * cnt
        if tmp > 10**6:
            break
        ls[tmp-1] = 1
        cnt += 1

ans = 0
if len(a):
    for i in range(len(a)):
        if ls[a[i]-1] == 0:
            ans += 1
    print(ans)
else:
    print(0)

Submission status: Wrong Answer

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

MAX_VAL = 2*10**6
prime = [1] * (MAX_VAL+1)
prime[0] = prime[1] = 0
for i in range(2, int(MAX_VAL**0.5)+1):
    if prime[i]:
        for k in range(2*i, MAX_VAL+1, i):
            prime[k] = 0

res = []
for i in range(n):
    prev = a[i-1] if i > 0 else -1
    next = a[i+1] if i < n-1 else -1
    if a[i] == prev or a[i] == next:
        continue
    if prime[a[i]]:
        res.append(a[i])
        continue

    for v in res:
        if a[i] % v == 0:
            break
    else:
        res.append(a[i])

print(len(res))

Submission status: Wrong Answer

Solution code:
import heapq
N = int(input())
a = list(map(int,input().split()))
Answer = []
heapq.heapify(a)
i=0 # リストを優先度付きキューへ
while a != []:
    p = heapq.heappop(a)
    Answer.append(p)
    if True:
        box =[]
        for j in range(len(a)):
            for k in range(len(Answer)):
                if a[j]%Answer[k] == 0:
                    break
                if k == len(Answer)-1:
                    box.append(a[j])
            if a[j] in Answer:
                Answer.remove(p)
            if j == len(a)-1:
                a = box
    i += 1
print(len(Answer))

Submission status: Wrong Answer

Solution code:
import bisect

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

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

N = int(input())
A = [int(i) for i in input().split()]

A = set(A)
A = list(A)
A.sort()

cnt = 0
for a in A:
    numlist = make_divisors(a)
    div = 0
    for x in numlist:
        if index(A, x) != -1:
            div += 1
    if div != 1:
        cnt += 1
if cnt == 0:
  print(0)
else:
  print(len(A) - cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
A_ = [int(i) for i in input().split()]
A=list(set(A_))
if len(A_)>len(A) and len(A)==0:
    print(0)
else:
    A.sort()
    A.reverse()
    times = 0
    for n,i in enumerate(A):
        flag = 0
        for j in list(range(n-1,n))+list(range(n+1,len(A))):
            if A[j]<=i:
                if i%A[j]==0:
                    flag = 1
                    break
        if flag == 0:            
            times+=1   
            
    print(times)

Submission status: Wrong Answer

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

m=max(A)
ans_list=A

counter=0

for i in range(1,m+1):
    if i in A:
        ans_list=list(filter(lambda x:x%i!=0 or x==i,ans_list))
        tmp=ans_list
        ans_list=set(ans_list)
        if len(ans_list)!=len(tmp):
            counter+=1

        # print(ans_list)

print(len(ans_list)-counter)

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(set(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
        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())
a = list(map(int,input().split()))
 
s = 0
u = -1
for i in a:
    t = 0
    for j in a:
        if j != i and i % j == 0:
            t += 1
    if j != i and t == 0:
        s += 1
print(s)

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
alist = list(map(int,input().split()))
alist.sort()
alist = np.array(alist)
nlist = alist.copy()

ans = 0
while True:
  alist = alist[alist%alist[0] != 0]
  ans += 1
  if len(alist) == 0:
    break
  
print(ans)

Submission status: Wrong Answer

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

li.sort(reverse=True)
ans = []
kotae = 0
print(li)
for i in range(a):
    for j in range(i + 1, a):
        if not li[i] % li[j] == 0:
            ans.append(i)
    if ans.count(i) == a - i - 1:
        kotae += 1
    count = 0
print(kotae)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
ans = [0]*(10**6+1)
mul = set()
for i in range(N):
	if ans[A[i]] == 0:
		ans[A[i]] = 1
		p = A[i]*2
		while p <= 10**6:
			ans[p] = -1
			p += A[i]
	elif ans[A[i]] == 1:
		A[i] = 2

q = 0	
for i in range(10**6+1):
	if ans[i] == 1:
		q += 1
print(q-len(mul))

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:
    if not ng[i]:
        ans += 1
        for j in range(1, 200000//i):
            ng[i*j] = 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import time


s = time.time()
def make_divisors_exist(n):
    #divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            if exists[i]:
                if i != n:
                    return True
            #divisors.append(i)
            i2 = n // i
            if i != i2: # choufuku
                if exists[i2]:
                    if i2 != n:
                        return True
                #divisors.append(i2)

    # divisors.sort()
    #return divisors
    return False



input = raw_input
input()
As_0 = map(int, input().split(" "))

out = 0

counter = Counter(As_0)
As = counter.keys()

max_A = max(As)
exists = [False] * (max_A + 1)

timeover = False
for A in As:
    exists[A] = True

s = time.time()
for A1, num in counter.items():
    e = time.time()
    tdiff = e-s

    if tdiff >= 1.888:
        #print(tdiff)
        break

    if num >= 2:
        continue
    
    exist = make_divisors_exist(A1)

    if not exist:
        out += 1

print(out)

Submission status: Wrong Answer

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

for i in range(N-1):
  for j in range(1+i, N):
    if A[j] > 500000:
      continue
    if A[j] in s:
      continue
    if A[j] % A[i] == 0:
      s.add(A[j])

l = tuple(filter(lambda x: x not in s, A))
print(len(l))

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

def isDiv(x, y):
  if x % y == 0:
    return True
  else:
    return False

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

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

if A[0] == 1 and A[1] == 1:
  print(N)
  exit()
if A[0] == 1 and A[1] != 1:
  print(N - 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 isDiv(x, y):
      cnt -= 1
      break
print(cnt)

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
tmp = set()
for i in a:
	tmp.add(i)

a = list(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**6+1,j):
		if i>maxa-1:
			break
		ans[i] = 0

print(ans.count(1))

Submission status: Wrong Answer

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

count=0
for i in l:
  for j in l:
    if i%j==0:
      if i!=j:
        count+=1
        break
      
print(n-count)

Submission status: Wrong Answer

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

A.sort(reverse=True)
S=0
b=4
if len(set(A)) == 1:
        print(int(0))

else:
    for i in range(N):
        for j in range(i+1,N):
            if A[i]%A[j]==0:
                break
            if j==4:
                S += 1
    print(int(S+1))

Submission status: Wrong Answer

Solution code:
import sys
import math


def get_prims():
    primes = [2]
    max = math.ceil(math.sqrt(10**6+1))
    for i in range(3, max, 2):
        for j in primes:
            if i % j == 0:
                break
        else:
            primes.append(i)
    return (primes)


def main():
    N = int(input())
    A = list(map(int, input().split()))
    prims = get_prims()
    ans = 0
    for i in range(0, len(A)):
        if A[i] in prims:
            ans += 1
        else:
            for j in range(0, len(A)):
                if i != j and A[i] % A[j] == 0:
                    break
            else:
                ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a_list = sorted(list(set(map(int, input().split()))))
if len(a_list) < 2:
    print(0)
else:
    count = 1
    for i in range(1, len(a_list)):
        flag = True
        target = a_list[i]

        for child in a_list[:i]:
            if (child > target//2):
                break
            if (target%child == 0):
                flag = False
                break
        if flag:
            count += 1
    print(count)

Submission status: Wrong Answer

Solution code:
from collections import Counter
# from numba import jit

def main():
    n = int(input().strip())
    L = list(map(int, input().strip().split()))
    seen = Counter()
    ans=0
    
    for x in L:
        seen[x]+=1
    
    def loop():
        ans=0
        for x in L:
            if seen[x]>1 or x!=1 and 1 in seen:
                continue
        
            tmp=2
            while tmp**2<=x:
                if x%tmp and (tmp in seen or x/tmp in seen):
                    break
                tmp+=1
            else:
                ans+=1
        return ans
    print(loop())
if '__main__' == __name__:
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int,input().split()))
ans = 0
B = A
A.sort()
if [i for i in A if i % A[0] != 0] == []:
  print(0)
elif A[0] == 1:
    print(1)
else:
 while True:
  try:
    A = [i for i in A if i % A[0] != 0]
  except IndexError:
    print(len(B))
    break
  else:
    if B == A:
      print(ans)
      break
    else:  
      ans +=1
      B = A

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
flag = 0
for i in range(N):
  if is_prime(i) == True:
    for j in range(N):
      if i != j:
        if A[i] == A[j]:
          flag = 1
          break
    if flag == 0:
      ANS += 1
    flag = 0
print(ANS)

Submission status: Wrong Answer

Solution code:
from collections import Counter

input()
c = Counter(map(int, input().split()))
r = 0
for k, v in c.items():
  if v == 1:
    i = 2
    while i * i <= k:
      if k % i == 0 and  (i in c or k // i in c):
        break
      i += 1
    else:
      r += 1
print(r)

Submission status: Wrong Answer

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

import numpy as np

ans = 0
for i in range(N):
    c = list(A[i]%np.array(A))
    if A.count(A[i]) == N:
        ans = 0
        break
    if c.count(0) == 1:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
l = int(input())
n = [int(i) for i in input().split()]
u = n.copy()

n.sort()
u.sort(reverse=True)

counter = 0

for i in range(l):
  if n.count(n[i]) >= 2:
      counter += 1
      pass
  else:
    for j in range(l):
      if u[i] == n[j]:
        pass
      elif u[i] % n[j] == 0:
        counter += 1
        break
      else:
        pass

print(l - counter)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
A = Counter((list(map(int, input().split(' ')))))
ans = 0
pre= 10**6+1
for i in sorted(A.keys(),reverse=True):
    flg = True
    if A[i] > 1:
        continue
    for j in range(pre,min(int(pow(i,0.5))+2,pre)):
        if not i%j:
            if A[j] and i != j:
                flg = False
                break
            if j != i//j and A[i//j] and i//j != i:
                    flg = False
                    break
    if flg:
        ans += 1
    pre = i
print(ans)

Submission status: Wrong Answer

Solution code:
import math
from itertools import combinations

n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
pen = 0
nex = n-1
count = 2
ans = 0
com = list(combinations(a,2))

if  len(list(set(a))) == 1:
    print("0")
    exit()

for i in range(len(com)):
    pen -= 1

    if com[i][0]%com[i][1] == 0 and pen < 1:
        ans += 1
        pen = nex

    nex -= 1
    if nex < 1:
        nex = n-count
        count += 1

print(n-ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import time


s = time.time()
def make_divisors_exist(n):
    #divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            if exists[i]:
                if i != n:
                    return True
            #divisors.append(i)
            i2 = n // i
            if i != i2: # choufuku
                if exists[i2]:
                    if i2 != n:
                        return True
                #divisors.append(i2)

    # divisors.sort()
    #return divisors
    return False



input = raw_input
input()
As_0 = map(int, input().split(" "))

out = 0

counter = Counter(As_0)
As = counter.keys()

max_A = max(As)
exists = [False] * (max_A + 1)

timeover = False
for A in As:
    exists[A] = True

s = time.time()
for A1, num in counter.items():
    e = time.time()
    tdiff = e-s

    if tdiff >= 1.88:
        #print(tdiff)
        break

    if num >= 2:
        continue
    
    exist = make_divisors_exist(A1)

    if not exist:
        out += 1

print(out)

Submission status: Wrong Answer

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

for i in range(N):
    if i > 10 ** 3:
        c += 1
        continue
    if i < N - 1:
        p = A[i + 1]
        if A[i] == A[i + 1]:
            B.add(A[i])
            continue
    Z = True
    for b in B:
        if A[i] % b == 0:
            Z = False
            break
    if Z:
        c += 1
        if A[i] <= 10 ** 3:
            B.add(A[i])

else:
    print(c)

Submission status: Wrong Answer

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




given_list_sort = sorted(given_list, reverse=True)
given_list_sort = list(set(given_list_sort))
length_ = len(given_list)
length_sort = len(given_list_sort)

count = 0
flag = False

for i in range(length_sort):
    ele_1 = given_list_sort[i]
    for j in range(length_sort):
        ele_2 = given_list_sort[j]
        # print(ele_1, ele_2)
        if (i < j) and (ele_1 % ele_2 != 0):
            continue
        else:
            flag = True
    if flag == False:
        count += 1


# print(count)
print(count)

Submission status: Wrong Answer

Solution code:
import numpy as np
N=int(input())
alist=list(map(int, input().split()))

alist.sort()
#print(alist)
ans=0
for i in range(1,N):
    a=alist[i]
    aaa=[a]*i
    x=np.array(aaa)
    y=np.array(alist[0:i])
    amari=x%y
    if list(amari).count(0)==1:
        ans+=1
print(ans)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

A.sort()
A2 = copy.copy(A)
i=0
while(i<len(A2)):
  for j in range(1,N-i):
    if A[i+j] % A[i] == 0:
      if A[i+j] in A2:
        A2.remove(A[i+j])
  i +=1
print(len(A2))

Submission status: Wrong Answer

Solution code:
from collections import deque as dq
import sys
input = sys.stdin.readline


def main():
    n = int(input())
    A = [int(i) for i in input().split()]
    ans = 1
    A.sort()
    A = dq(A)


    while A:
        start = A.popleft()
        if not A:
            break
        ans += 1
        A = dq([a for a in A if a % start != 0])

    print(ans)

    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

d_num = a

div = []
a_set = list(set(a))
flag = False
if len(a_set) == 1:
    print(0)
else:
    for i in range(len(a_set)):
        flag = False
        # for j in range(len(div)):
        #     if(a_set[i]%div[j] == 0):
        #         d_num -= 1
        #         flag = true
        #         break
        if flag == False:
            div.append(a_set[i])
    print(1)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
b = []
for i in range(1,len(a)):
    if a[i-1]!=a[i]: b.append(a[i-1])
if a[n-1]!=a[n-2]: b.append(a[n-1])
if len(b)==0:
    print("0")
else:
    c = [0]*(max(b)+1)
    for i in range(len(b)):
        j = 2
        while b[i]*j<=max(b):
            c[b[i]*j-1]+=1
            j+=1
    ans = 0
    for i in b:
        if c[i-1]==0:
            ans+=1
    print(ans)

Submission status: Wrong Answer

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

import numpy as np
from collections import Counter


N = int(input())
A = np.array(readline().split(), dtype=np.int64)
A = np.random.randint(1, 10 ** 6, 2 * 10 ** 5)
count = Counter(A)
A = np.array([
    a for a, c in count.items() if c == 1
])

if len(A) != 0:
    A = np.sort(A)

i = 0
while True:
    if len(A) == 0:
        break
    pre = A
    a = A[i]
    A = np.delete(A, np.where((A % a == 0) & (A != a)))
    i += 1
    if i >= len(A):
        break

print(len(A))

Submission status: Wrong Answer

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

ans = 0 
a.sort(reverse=True)

for i in range(n-1):
    fl = 0
    for j in range(i+1,n):
        if i != j:
            if a[i] % a[j] == 0:
                fl += 1
                break
        else:
            fl +=1
    if fl == 0:
        ans += 1
        
print(ans)

Submission status: Wrong Answer

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

a.sort()
li = [True] * (10**6 + 10)
ans = 0

for i in range(n):
    if not li[a[i]]:
        continue
    li[a[i]] = False
    if i < n-1:
        if a[i+1] == a[i]:
            continue
    ans += 1
    tmp = a[i]
    while tmp < len(li):
        li[tmp] = False
        tmp += a[i]

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from sys import stdin
import numpy as np
input = stdin.readline

N = int(input())
A_list = list(map(int, input().split()))
ans_list =np.ones(N)

for i in range(N):
    for j in range(i+1,N):
        if A_list[i] %  A_list[j] == 0:
            ans_list[i] = 0
        elif(A_list[j] %  A_list[i] == 0):
            ans_list[i] = 0
print(int(np.sum(ans_list)))

Submission status: Wrong Answer

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

ans = []
que = deque(sorted(a))
x = que.popleft()
que.append(x)

while que:
    if len(que) == 1:
        ans.append(que.pop())
        break
    nx = que.popleft()
    if x == nx:
        ans.append(x)
        x = que.popleft()
        que.append(x)
        continue
    if nx % x != 0:
        que.append(nx)

if a.count(a[0]) == n:
    print(0)
else:
    print(len(ans))

Submission status: Wrong Answer

Solution code:
import math

def make_prime_list_2(num):
    if num < 2:
        return []

    # 0のものは素数じゃないとする
    prime_list = [i for i in range(num + 1)]
    prime_list[1] = 0 # 1は素数ではない
    num_sqrt = math.sqrt(num)

    for prime in prime_list:
        if prime == 0:
            continue
        if prime > num_sqrt:
            break

        for non_prime in range(2 * prime, num, prime):
            prime_list[non_prime] = 0

    return [prime for prime in prime_list if prime != 0]

prime = make_prime_list_2(10**6) + [1]

n = int(input())
l = list(map(int,input().split()))
#print(n)
#print(l)

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


l_2 = []
ans = 0
for _ in l:
    if _ in prime:
        ans += 1
    else:
        l_2.append(_)
tmp = len(l_2)
#print(l_2, ans, tmp)

for i in range(tmp):
    for j in range(n):
        if l_2[i] != l[j]:
            if l_2[i] % l[j] == 0:
                break
    else:
        ans += 1

print(ans)