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:
n = int(input())
A = list(map(int,input().split()))
ans = 0
B = A
A.sort()
if A[0] == 1:
  print(1)
elif [i for i in A if i % A[0] != 0] == []:
  print(0)
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:
from collections import Counter, deque

def prime_decomposition(n):
    i = 2
    tank = []
    while i * i <= n:
        while n%i == 0:
            n /= i
            tank.append(i)
        i += 1
    if n > 1:
        tank.append(int(n))
    return tank

def sieve(n):
    is_prime = [True]*(n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]:
            continue
        else:
            for j in range(i*2, n+1, i):
                is_prime[j] = False
    return [i for i in range(n+1) if is_prime[i]]

n = int(input())
A = list(map(int,input().split()))
A = sorted(A)
c = Counter(A)
lst = []
for k,v in c.items():
    if v==1:
        lst.append(k)
if len(lst)==0:
    print(0)
elif 1 in lst:
    print(1)
else:
    que = deque(lst)
    cnt = 0
    while que:
        cnt += 1
        i = que.popleft()
        tmp = [j for j in que if j%i!=0]
        que = deque(tmp)
    print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
flag = 0
ans = 0
if A.count(A[0]) == 1:
  ans += 1
for i in range(1,N):
  flag = 0
  for j in range(i):
    if A[j]!=0 and A[i] % A[j] == 0:
      flag = 1
      break
  if flag == 0:
    ans += 1
  else:
    A[i] = 0

print(ans)

Submission status: Wrong Answer

Solution code:
# /usr/bin/python3
# -*- coding: utf-8 -*-
from queue import Queue
from queue import LifoQueue as Stack
from math import sqrt, floor, ceil, log2, log10, pi
from fractions import gcd
from itertools import permutations, combinations
from operator import itemgetter
from functools import cmp_to_key

# from numpy import gcd


INF=1001001001
__MOD__=(10**9)+7
yn = 'YNeos'
judge = False
cnt = 0
ans = None


def lcm(a, b):
    return (a*b) // gcd(a,b)

def intinput():
    return int(input())

def mulinputs():
    return map(int,input().split())

def lineinputs(func=intinput):
    datas = []
    while True:
        try:
            datas.append(func())
        except EOFError:
            break
    return datas

class ModInt():
    def __init__(self, x):
        self.__x = (x % __MOD__)
    def __add__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x + other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x + other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __radd__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x + self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x + self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __sub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x - other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x - other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rsub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x - self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x - self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __mul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rmul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __truediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rtruediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __pow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(self.__x, other.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(self.__x, other.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")
    def __rpow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(other.__x, self.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(other.__x, self.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")

    def __modinv(self, m=__MOD__):
        a = self.__x
        if a == 0:
            raise ZeroDivisionError()
        if gcd(a, m) != 1:
            raise Exception("%sの逆数は求まりません。" % a)
        b, u, v = m, 1, 0
        while b != 0:
            t = a//b;
            a -= t*b
            a, b = b, a
            u -= t * v
            u, v = v, u
        u %= m
        if u < 0:
            u += m
        return u
    def __int__(self):
        return self.__x
    def __str__(self):
        return str(self.__x)



if __name__ == '__main__':
    N = intinput()
    ds = set(mulinputs())

    if len(ds) <= 1:
        print(0)
        exit()
    ds = list(ds)
    ds.sort()
    if ds[0] == 1:
        print(0)
        exit()
    p = []
    # while ds:
    l = int(sqrt(len(ds)))
    for _ in range(l):
        if not ds:
            break
        tmp = ds.pop(0)
        p.append(tmp)
        ds = [ d for d in ds if d % tmp != 0]

    # 出力
    print(len(p)+len(ds))

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
a = np.array(list(map(int, input().split())))
aa = np.sort(a)
ans = 0
while len(aa):
    aa = np.delete(aa, np.where(aa % aa[0] == 0))
    ans += 1
if np.count_nonzero(a == a[0]) == n:
    print(0)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
df = [0]*n

for i in range(n-1):
  if a[i]==a[i+1]:
    df[i]=1
    df[i+1]=1

b=[-1]*n
bn=0
for i in range(n):
  if df[i] == 0:
    b[bn]=a[i]
    bn+=1

i = 0
for i in range(bn-1):
  if b[i] != -1:
    for j in range(i+1,bn):
      if b[j] == -1:
        continue
      if b[j] % b[i] == 0:
        b[j] = -1

ans=0
for i in range(len(b)):
    ans += 1 if b[i] != -1 else 0

print(ans)

Submission status: Wrong Answer

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

def calc():
    n = int(input())
    a = [int(x) for x in input().split()]
    k = [0] * n
    cnt = 0
    for i in range(n):
        for j in range(i):
            if i == j:
                continue
            if k[i] == 0 and a[i] % a[j] == 0:
                cnt += 1
                k[i] = 1
            if k[j] == 0 and a[j] % a[i] == 0:
                cnt += 1
                k[j] = 1
    print(cnt)

calc()

Submission status: Wrong Answer

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

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


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()
    del divisors[0]
    return divisors

#昇順
ai.sort()
min_ai = ai[0]

for i in range(n):
    num_li[ai[i]] += 1

ans = 0
    
for i in range(n):
    if num_li[ai[i]] > 1:
        continue
    #print(ai[i])
    flag = True
    div = make_divisors(ai[i])
    #print(div)
    #print(div)
    for j in range(len(div)):
        if div[j] < min_ai:
            break
        #if div[j] == ai[i]:
        #    continue
        #print(div[j],div)
        if num_li[div[j]] > 0:
            flag = False
            break
    if flag == True:
        ans += 1
    #exit()
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
li = list(map(int,input().split()))
li.sort()
if li[0] == 1:
    print(1)
    exit()
if len(set(li)) == 1:
    print(0)
    exit()
for i in range(10^5):
    li.append(1122887)
count = 0
a = 0
for i in range(n):
    if li[i] == 1122887:
        break
    j = i + 1
    while True:
        if li[j] == 1122887:
            break
        if li[j] == li[i]:
            a += 1
        if li[j] % li[i] == 0:
            li.remove(li[j])
            count += 1
        else:
            j += 1
print(n - count - 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()

if a.count(a[0])==n:
	print(0)
	exit()

maxa = max(a)+1

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



for j in a:
	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:
def main():
  n, = list(map(int, input().split()))
  aa = sorted(map(int, input().split()))
  if 1 in aa:
    print(1)
    exit()
  
  
  for i in range(len(aa)):
    x = aa[i]
    for j in range(i+1, len(aa)):
      y = aa[j]
      if x > 1 and y > 1:
        if y == x:
          aa[i] = 1
          aa[j] = 1
        if y % x == 0:
          aa[j] = 1
        
  print(sum(1 for a in aa if a > 1))
    
  
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

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


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]

_a = set(A)
cnt = 0
for i in range(N):
    div = make_divisors(A[i])
    if len(set(A) & set(div)) > 1:
        cnt += 1
print(N-cnt)

Submission status: Wrong Answer

Solution code:
import sys, math, itertools, collections, bisect 
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8') 
inf = float('inf') ;mod = 10**9+7 
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
if A.count(A[0]) == len(A):
    print(0)
    exit()
for i in range(n):
    chk = True
    if A.count(A[i]) >= 2:
        pass
    else:
        for j in range(i+1, n):
            if A[i] % A[j] == 0:
                chk = False
                break
        if chk == True:
            ans += 1
        else:
            pass
print(ans)

Submission status: Wrong Answer

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

n = int(input())
li = list(map(int,input().split()))
li2 = li[:]
li2.sort(reverse=True)
ans = 0

if len(set(li)) == 1:
    ans = 0
else:
    for i,num in enumerate(li2,1):
        temp = 0
        j_list = li2[i:]
        for j in j_list:
            if num % j == 0:
                break
            else:
                temp += 1
        if temp == n - i:
            ans += 1
print(ans)

Submission status: Wrong Answer

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

A = sorted(A)


from collections import Counter
C = Counter(A)

if all([c > 1 for c in C.values()]):
    print(0)
else:
    F = [1 for _ in range(N)]
    for i, a in enumerate(A):
    #    print()
    #    print(i, a)
        for j in range(i+1, N):
            if A[j]%a == 0:
                F[j] *= 0
    #        print(A[j], A[j]%a)
    #    print(F)
    print(F.count(1))

Submission status: Wrong Answer

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

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

avg = sum(A)/len(A)
if avg == A[0]:
	print(0)
else:
	ans = 0
	for i in range(N):
		if is_prime(A[i]):
			ans += 1
		else:
			for j in range(N):
				if i != j:
					if A[i] % A[j] == 0:
						break
				if j == N - 1:
					ans += 1
	print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
A =  list(map(int,input().split()))
def make_divisors(n):
    """
    約数列挙
    :param n:
    :return:
    """
    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]

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

cnt = 0
for a  in A:
    # print(a , A)
    if a not in A:
        continue
    A_length=len(A)
    yakusu= set(make_divisors(a))
    # print(yakusu)
    _A = A - yakusu
    if A_length -1 > len(_A):
        continue
    cnt +=1
print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
D =[]
E =[]
for i in A:
    for j in A:
        #print(i,j)
        if i != j:
            if i % j == 0:
                #print(i,j)
                D.append(i)


for k in range(N):
    if A[k] not in D:
        E.append(A[k])

#print(D)
#print(E)
#print(len(E))

if len(D) == 0:
    print(0)

else:
    print(len(E))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(4100000)
import math
INF = 10**9
import fractions

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

    A.sort()
    ans = len(A)
    if n == 1:
        print(1)
        return
    for i in range(n):
        for j in range(n):
            ri = -i-1
            r = A[ri]
            l = A[j]
            if (ri!=-n and r == A[ri-1]) or (i!=n-1 and r == A[ri+1]):
                ans -= 1
                break
            if n+ri == j:
                break
            if r % l == 0:
                ans -= 1
                break
            if l >= r**(1/2):
                break
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
from collections import Counter
import sys

input=sys.stdin.readline

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

#O(nlogn)
A.sort()

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


cnt= 0 if len(A)>1 and A[0]!=A[1] else -1

while len(A)>0:
  #iの先頭要素を取り出す
  a = A[0]
  #aで割り切れるやつは削除する
  A = [a_ for a_ in A if a_ % a != 0]
  cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
def LI(): return list(map(int, input().split()))
def I(): return map(int, input().split())
  
def main():
  m = int(input())
  a = LI()
  ans = 0
  n = max(a)
  num = [True]*(n+1)
  num[0] = False
  a.sort()
  for i in range(m):
    if (i != m-1 and a[i]==a[i+1]) or (i != 0 and a[i]== a[i-1]): num[a[i]] = False
    for j in range(a[i]*2, n+1, a[i]):
      num[j] = False
  print(num)
  for aa in a:
    if num[aa]:
      ans += 1
  print(ans)

if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[int(i) for i in input().split()]
ok=False
ans=0
val=a[-1]
for i in range(1,n):
    if a[n-i-1]==a[n-i]:
        ok=True
    if val%a[n-i-1]!=0:
        if a[n-i-1]!=a[n-i]:
            ans+=1
        else:
            ok=True
    val*=a[n-i-1]
if ok:
    print(ans)
else:
    print(n-ans)

Submission status: Wrong Answer

Solution code:
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

  
n = int(input())
a_list = list(sorted(list(map(int,input().split()))))
sosuu = []
hukusuu = []

for i in range(len(a_list)-1,0,-1):
  if a_list[i] == a_list[i-1]:
    hukusuu.append(i)
    hukusuu.append(i-1)
    
hukusuu = sorted(list(set(hukusuu)),reverse=True)
for i in hukusuu:
  a_list.pop(i)

if len(a_list) == 0:
  print(0)
else:
  a_list = sorted(a_list)
  while 1:
    if len(a_list) == 0:
      break
    num = a_list.pop(0)
    iranai = False
    for i in sosuu:
      if num % i == 0:
        iranai = True
        break
      elif num < i*2:
        break
    if iranai == False:
      sosuu.append(num)

  print(len(sosuu))

Submission status: Wrong Answer

Solution code:
N=int(input())
L=list(map(int,input().split()))
a=0
b=N
if 1 in L:
  print(0)
else:
  for i in L:
    for j in L:
      if i!=j and i%j==0:
        a+=1
        if a>=1:
          b=b-1
  print(b)

Submission status: Wrong Answer

Solution code:
n = int(input())

from collections import defaultdict

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

d = defaultdict(int)

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

count = 0

d = sorted(d.items(), reverse=True)
wm = d[0][0]

while len(d):
    a, c = d.pop()
    if c == 1:
#         print(f'count {a=}, {c=}, {count=}, {d=}')
        count += 1
    if a == 1:
        break
    if len(d):
        m = d[0][0]
    else:
        m = a - 1
    if a * 2 <= m and a * a <= wm:
        d = [elm for elm in d if elm[0] % a]
    else:
        d = [elm for elm in d if elm[1] == 1]
        count += len(d)
        break

print(count)

Submission status: Wrong Answer

Solution code:
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
N = int(input())
A = list(map(int, input().split()))
A.sort()
a = A[-1]
P = set(primes(a))
ans = []
for i in range(N):
    a = A[i]
    if a in P:
        ans.append(a)
    else:
        if all([a % gen != 0 for gen in ans]) == True:
            ans.append(a)
print(len(ans))

Submission status: Wrong Answer

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
import math
from copy import deepcopy
import queue
import numpy as np
# sympy as syp(素因数分解とか)
Mod = 1000000007
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1] 
for i in range(2, 10**5 + 1):
    fact.append((fact[-1] * i) % Mod)
    inv.append((-inv[Mod % i] * (Mod // i)) % Mod)
    factinv.append((factinv[-1] * inv[-1]) % Mod)
    
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n - r] % p
    
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[y] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

def main():  #startline-------------------------------------------
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    prime = [1] * n
    for i in range(n):
        if prime[i] == 1:
            for j in range(i+1, n):
                if a[j] % a[i] == 0:
                    prime[j] = 0

    ans = sum(prime)
    print(ans if ans != 1 else 0)



if __name__ == "__main__":
    main() #endline===============================================

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    from collections import defaultdict
    N = int(input())
    A = []
    C = defaultdict(int)
    for i in map(int, input().split()):
        if C[i] == 0:
            A.append(i)
        C[i] += 1
    A.sort()
    X = []
    ans = 0
    if C[1] > 1:
        print(0)
        sys.exit()
    elif C[1] == 1:
        print(1)
        sys.exit()
    for a in A:
        for x in X:
            if a % x == 0:
                break
            if X[0] * x > a:
                if C[a] == 1:
                    ans += 1
                X.append(a)
                break
        else:
            if C[a] == 1:
                ans += 1
            X.append(a)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from math import sqrt, gcd, ceil, log
from bisect import bisect
from collections import defaultdict, Counter
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))

# sys.setrecursionlimit(10**6)



def solve():
	n = int(input()); arr= Counter(read())
	lis = sorted(arr.keys())
	# print(lis)
	ans = 0
	for i in range(len(lis)):
		
		if arr[lis[i]] == 0:
			pass
		elif arr[lis[i]] > 1:
			arr[lis[i]] = 0
		else:
			ans += 1
			for j in range(i+1, len(lis)):
				if lis[j]%lis[i] == 0:
					arr[lis[j]] = 0
	print(ans)



	# arr.sort()
	# k = 0
	# if arr[0] == arr[1]:
	# 	k = 1
	# 	while k < n and arr[k] == arr[0]:
	# 		arr[k] = 0
	# 		k += 1
	# 	arr[0] = 0
	# ans = 0
	# # print(arr)
	# for i in range(k, n):
	# 	if arr[i]:
	# 		ans += 1
	# 		for j in range(i+1, n):
	# 			if arr[j]%arr[i] == 0:
	# 				arr[j] = 0
	# print(ans)








if __name__ == "__main__":
	solve()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
iter = 0
"""
for i in a:
  lst = [i%j for j in a]
  if lst.count(0) == 1:
    iter = iter + 1
"""

#a.sort()
for i in a:
  lst = list(filter(lambda x: x<i, a))
  lst = [i%j for j in lst]
  if lst.count(0) == 0:
    iter = iter + 1
print(iter)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort(reverse=True)
c = 0
a = list(set(a))
n = len(a)

for i in range(n):
  for j in range(n-i-1):
  
    if a[i]%a[-(1+j)]==0:
      c +=1
      break
#      print(i,j)
print(n,c)
if n == 1:
  print("0")
else:
  print(n-c)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
df = [0]*n

for i in range(n-1):
  if a[i]==a[i+1]:
    df[i]=1
    df[i+1]=1

b=[-1]*n
bn=0
for i in range(n):
  if df[i] == 0:
    b[bn]=a[i]
    bn+=1
print(b)
i = 0
for i in range(bn-1):
  if b[i] != -1:
    for j in range(i+1,bn):
      if b[j] == -1:
        continue
      if b[j] % b[i] == 0:
        b[j] = -1

ans=0
for i in range(len(b)):
    ans += 1 if b[i] != -1 else 0

print(ans)

Submission status: Wrong Answer

Solution code:
import math
import sys
 
def isPrime(n):
  if n == 2:
    return True
  if n % 2 == 0:
    return False
  
  # nの平方根まで計算する
  m = math.floor(math.sqrt(n)) + 1
  for p in range(3, m, 2):
      if n % p == 0:
        return False
  return True


n=int(input())
As = list(map(int, input().split()))
i=0
j=0
count =0
if As.count(1)==1:
    print(1)
    sys.exit()
if As.count(1)>=2:
    print(0)
    sys.exit()
for a in As:
    if As.count(a)>=2:
        i+=1
        continue
    elif isPrime(a):
        count+=1
        i+=1
        continue
    elif a==min(As):
        continue
    for b in As:
        if a<b:
            if j==n-1:
                count+=1
                break
            else:
                j+=1
                continue
        if i!=j:
            if a%b==0:
                break
            elif j==n-1:
                count+=1
        elif j==n-1:
            count+=1
        j+=1
    i+=1
    j=0

print(count)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=list(map(int,input().split()))
l.sort()
b=l[-1]
r=[]
for i in range(n):
	x=l[i]
	for j in range(x*2,b+1,x): 
		if(j in l):
			r.append(j)
        	
m=len(set(r))
if(m==0):
  print(0)
else:
  print(n-m)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
ans=0
dup = [x for x in set(A) if A.count(x) > 1]

A=set(A)
for i in range(len(dup)):
    A.remove(dup[i])


A=sorted(set(A))

if A==0:
    print(0)
else:
    for i in range(len(A)):
        k=0
        for j in range(i):
            if A[i]%A[j]==0:
                k=1
                break


        if k==0:
            
            ans+=1
    print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
p = [a[0]]
for i in range(1,n):
    v = 1
    for j in range(len(p)):
        if a[i] % a[j] != 0 and a[i] < 2*a[j]:
            break
        if a[i] % a[j] == 0:
            v = 0
            break
    if v == 1:
        p.append(a[i])
ans = len(p)
for i in range(n-2):
    if a[i] == a[i+1] and a[i+1] != a[i+2] and a[i] in p:
        ans -= 1
if n > 1:
    if a[-1] == a[-2] and a[-1] in p:
        ans -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
import copy
n = int(input())
li = list(map(int,input().split()))
set1 = set()
ban = set()
for i in li:
    if i not in set1:
        set1.add(i)
    else:
        ban.add(i)
set2 = copy.copy(set1)
cnt = 0
for i in set1:
    set2.remove(i)
    flg = False
    if i in ban:
        flg = True
    else:
        for j in set2:
            if flg:
                break
            if i != j:
                if i % j == 0:
                    flg = True
    if not flg:
        cnt += 1
        set2.add(i)
print(cnt)

Submission status: Wrong Answer

Solution code:
def readInt():
    return list(map(int,input().split()))
    
n = int(input())
a = readInt()
a.sort(reverse=True)
ans = 0
# print(set(a))
# print(a)
if len(set(a))==1:
    print(0)
else:
    for i in range(n):
        judge = True
        for j in range(i+1,n):
            # print(a[i]%a[j])
            if a[i] % a[j] == 0:
                judge = False
        # print('/')
        if judge:
            ans += 1
    print(ans)

Submission status: Wrong Answer

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

if 2 in row_ary:
  row_ary = [x for x in set(row_ary) if x % 2 == 1]
  row_ary.append(2)

ary = [x for x in set(row_ary) if row_ary.count(x) == 1]


ary.sort(reverse=True)

del_list_index = []

print(ary)

for i in range(len(ary)):
    for j in range(i+1, len(ary)):
        if ary[i] % ary[j] == 0:
            del_list_index.append(i)

for index in sorted(set(del_list_index), key=del_list_index.index,reverse=True):
	ary.pop(index)

print(len(ary))