Problem:


Score : 400 points

Problem Statement

Given is a number sequence A of length N.

Find the number of integers i \left(1 \leq i \leq N\right) with the following property:

For every integer j \left(1 \leq j \leq N\right) such that i \neq j , A_j does not divide A_i.

Constraints

All values in input are integers.

1 \leq N \leq 2 \times 10^5

1 \leq A_i \leq 10^6

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answer.

Sample Input 1

5
24 11 8 3 16

Sample Output 1

3

The integers with the property are 2, 3, and 4.

Sample Input 2

4
5 5 5 5

Sample Output 2

0

Note that there can be multiple equal numbers.

Sample Input 3

10
33 18 45 28 8 19 89 86 2 4

Sample Output 3

5



Sample input:
5
24 11 8 3 16


Sample output:
3

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
from sys import stdin,setrecursionlimit
import heapq,bisect,math,itertools,string,queue,datetime,copy
setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, stdin.readline().split()))

N = int(input())
Als = inpl()

Als.sort()

"""def era(ls):#sort済み
    result = []
    while len(ls)>=1:
        a = ls[0]
        f = False
        for item in ls[1:]:
            if item%a==0:
                ls.remove(item)
        result.append(a)
    print(len(result))"""

def era(ls):
    result = []
    while len(ls)>=1:
        a = ls[0]
        ls = ls[1:]
        f = False
        for item in ls:
            if item==a:
                f = True
            if item%a==0:
                ls.remove(item)
        if not f:
            result.append(a)

    print(len(result))

era(Als)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
cnt=0
for i in range(n):
  for k in range(n-i-1):
    if a[i]%a[i+k+1]==0:
      break
    else:
      if i+k+1!=n-1:
        pass
      else:
        cnt+=1
print(cnt)

Submission status: Wrong Answer

Solution code:

N=int(input())
a_list=list(map(int,input().split()))
count=0

a_list=sorted(a_list, reverse=True)
for i in range(N) :

  flag=True
  for j in range(i+1,N) :
    if i!=j :
      if a_list[i]%a_list[j]==0  :
        flag=False
        break
  if flag :
    count+=1

print(count)

Submission status: Wrong Answer

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

a = sorted(set(a))
a.reverse()
#print(a)
ans = 0

for i in range(len(a)):
    for j in range(len(a)-1,-1,-1):
        #print(i,j)
        if i == j:
            continue
        #print(a[i],a[j])
        if a[i] % a[j] == 0:
            break
        if j == n - 1:
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

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

B = A[:]
B.sort()
l = []
for i, a in enumerate(A):
  flag = False
  for k, b in enumerate(B):
    if a == b:
      if k == len(B)-1 and flag==False:
        l.append(i+1)
      continue

    if a >= b:
      if a % b == 0:
        flag = True
        break
    else:
      if flag==False:
        l.append(i+1)
      break
    
    if k == len(B)-1 and flag==False:
      l.append(i+1)
 

print(len(l))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
ans = 0
for i, a in enumerate(A):
    if i != N-1:
        if a == A[i+1]:
            continue
    if i != 0:
        if a == A[i-1]:
            continue
    flag = True
    for j in range(i):
        if a % A[j] == 0:
            flag = False
            break
        if a + 10 < A[j] ** 2:
            break
    if flag:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=0
ak=[]
cur=a[0]
for i in a[1:]:
	if i==cur:
		continue
	else:
		ak.append(cur)
		cur=i
if n==1 or not a[-2]==a[-1]:
	ak.append(a[-1])
a=ak
while len(a):
	newa=[]
	k=a[0]
	ans+=1
	for i in a[1:]:
		if not i%k==0:newa.append(i)
	a=newa
print(ans)

Submission status: Wrong Answer

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

ans = 0
if not A[0] in A[1:]: ans += 1
for i in range(1, N):
    tmp = True
    for j in range(i):
        if A[i] % A[j] == 0:
            tmp = False
            break
    if tmp: ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys
input = sys.stdin.readline
ipnl = lambda n: [int(input()) for _ in range(n)]
inp = lambda :int(input())
ip = lambda :[int(w) for w in input().split()]

def solve(x,n): 
    s = set(x)
    mx = max(x)
    res = set()
    for i in range(n): 
        for j in range(x[i]*2,mx+1,x[i]): 
            if j in s:
                res.add(j)
    return n-len(res)

n = inp()
x = ip()
if len(set(x)) == 1:
    print(0)
else:
    print(solve(x,n))

Submission status: Wrong Answer

Solution code:
N=int(input())
a = list(map(int, input().split()))
p = []

a.sort()
p.append(a[0])
for i in range(1,N):
    flag = True
    for j in range(len(p)):
        if p[j]**2>a[i]:
            break
        if a[i]%p[j]==0:
            flag =False
            break
    if flag:
        p.append(a[i]) 

print(len(p))

Submission status: Wrong Answer

Solution code:
import numpy as np

def main():
    n = int(input())
    A = list(map(int, input().split()))
    A.sort()
    A = np.array(A, dtype=np.int64)

    if np.all(A == A[0]):
        print(0)
        exit()
    #print(A)

    cnt = np.any(A == A[0])
    memo = [1] * n
    for i in range(n - 1):
        for j in range(i + 1, n):
            if memo[j] == 0:
                break
            if A[j] % A[i] == 0:
                memo[j] = 0
                cnt += 1

    print(n - cnt)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    pA = sorted(A, reverse=True)
    # print(pA)
    cnt = 0
    for i in range(N-1):
        surplus_cnt = 0
        for j in range(i+1,N):
            # print(i,j,pA,cnt)
            if pA[i] % pA[j] == 0:
                surplus_cnt = 0
                break
            else:
                surplus_cnt += 1
        if surplus_cnt > 0:
            cnt += 1
    if len(set(A)) >= 2:
        cnt += 1
    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
if min(a)>max(a)//2:
  print(n)
  exit()
l=[0 for i in range(10**6+1)]
for i in range(n):
  l[a[i]]+=1
d={}
ans=0
for i in range(n):
  x=a[i]
  if x not in d:
    if l[a[i]]==1:
      flag=1
      for j in range(1,int(x**0.5)+2):
        if x%j==0:
          if x!=j and l[j]>0:
            flag=0
            break
          if x!=x//j and x%(x//j)==0 and l[x//j]>0:
            flag=0
            break
      if flag==1:
        ans+=1
        d[x]=1
      else:
        d[x]=0
  else:
    ans+=d[x]
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
ans = [True] * len(A)

dou = [x for x in set(A) if A.count(x) > 1]
A.sort()

for i in range(len(A)):
        if A[i] > 320:
                break
        for j in range(i+1, len(A)):
                if A[j] % A[i] == 0:
                        ans[j] = False


count = 0
for i in ans:
        if i:
                count += 1
print(count -  len(dou))

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)

    if temp!=1:
        arr.append(temp)

    if arr==[]:
        arr.append(n)
    return arr

import math
def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 # 1は素数ではない

    # エラトステネスのふるい
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

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

ps = set(primes(10**6))

""" prime check """
input()
ai=list(map(int,input().split()))
aps = ([p for p in ai if p in ps])
# print(aps)
cs = [c for c in ai if c not in ps]
cs.sort()
# print(cs)
def reduce_multiple(f):
    a = 1
    for f0 in f:
        a *= f0
    return a
  
  
def exists_in_aps(f):
    for f1 in f:
        if f1 in aps:
            return False
    else:
        return True

fs = [factorization(c) for c in cs]
fs = [f for f in fs if exists_in_aps(f) ]
reduce_fs = set([reduce_multiple(f) for f in fs])
# print(fs)
from collections import Counter
prime_num = 0
for p,n in Counter(aps).items():
    if n == 1:
        prime_num += 1

print(prime_num + len(reduce_fs) )

Submission status: Wrong Answer

Solution code:
import copy 

N=int(input())
A=list(map(int,(input().split())))
new_A=list(set(A))
tmp_A = copy.copy(new_A)
count=0

for i in new_A:
  tmp_A.remove(i)
  temp_count=0

  for j in tmp_A:
    if(i%j==0):
      continue
    temp_count+=1

  if(temp_count==N-1):
    count+=1

  tmp_A = copy.copy(new_A)
print(count)

Submission status: Wrong Answer

Solution code:
import bisect

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

st = set(As)

Fs = [0]*N

As.sort()
if N == 1:
  print(1)
  exit()
elif As[0] < As[1]:
  rlt = 1
else:
  rlt = 0
  
for i in range(1,N):
  if As[i] == As[i-1]:
    Fs[i] = 1
    continue
  for j in range(i):
    flag = 0
    if Fs[j] == 1:
      continue
    else:
      if As[i] < 2*As[j]:
        break
      if As[i]%As[j] == 0:
        Fs[i] = 1
        flag = 1
        break
  if flag == 0:
    rlt += 1
        
print(rlt)

Submission status: Wrong Answer

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

ans = 0
for i in range(N):
    if i == 0:
        if N != 1 and A[0] != A[1]:
            ans += 1
    else:
        if all(A[i] % A[i - j] != 0 for j in range(1, i + 1)):
            print(A[i])
            ans += 1
print(ans)

Submission status: Wrong Answer

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

res = 0

for i in range(N - 1):
    boolean = True
    for j in range(i+1, N):
        if A[i] % A[j] == 0:
            boolean = False
            break
    if boolean:
        res += 1
print(res)

Submission status: Wrong Answer

Solution code:
class d:
    def __init__(self, a, i):
        self.a = a
        self.i = i
    def __lt__(self, other):
        return self.a < other.a

    def __gt__(self, other):
        return self.a > other.a


n = int(input())
a = map(int, input().split(' '))
a = list(a)
num_iter = []
for i, ai in enumerate(a):
    myd = d(ai, i+1)
    num_iter.append(myd)

num_iter.sort(reverse=True)

size = len(num_iter)
ans = 0

for i in range(size):
    for j in range(i+1, size):
        # print(num_iter[i].a, num_iter[j].a)
        if num_iter[i].a == num_iter[j].a:
            break
        if  num_iter[i].a % num_iter[j].a == 0:
            ans += 1
            break

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
*A, = map(int, input().split())
A = sorted(A)
checked = [True] * N
ans = 0
for i, a in enumerate(A):
    if not checked[i]: continue
    flag = True
    for j in range(i+1, N):
        if A[j] % a == 0: checked[j] = False; flag = False
    if flag: ans += 1 
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
b = [min(a)]
c = []

for i in range(1,len(a)):
    if a[i] in b:
        if a[i] in c:
            continue
        else:
            c.append(a[i])
        continue
    else:
        b.append(a[i])
        for j in range(len(b)-1):
            if a[i] % b[j] == 0:
                b.pop(-1)
                break
print(len(b)-len(c))

Submission status: Wrong Answer

Solution code:


import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 7)
# ----------

INF = float("inf")
MOD = 10 ** 9 + 7
# ----------

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



if len(set(A)) == 1:
    print(0)
    exit()
if A[0] == A[1] == 1:
    print(0)
    exit()
if A[0] == 1:
    print(N-1)
    exit()


S = set()

for a in A:
    i = 2
    while a * i <= 10 ** 6:
        S.add(a * i)
        i += 1

ans = []
for a in A:
    if not a in S:
       ans.append(a)


D = defaultdict(int)
for a in ans:
    D[a] += 1

L = []
for k, v in D.items():
    if v > 1:
        continue
    L.append(k)


print(len(L))

Submission status: Wrong Answer

Solution code:
import numpy as np
def main():
    N = int(input())
    A = list(map(int, input().split()))
    
    A.sort(reverse=True)
    A = np.array(A, dtype=np.int64)

    #print(A)
    count = 0
    for i, a in enumerate(A):
        #print(a % A[i+1:] != 0)
        if any(a % A[i+1:] == 0):
            continue
        count += 1
    if len(A) > 2 and A[-1] == A[-2]:
        count -= 1

    print(count)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

new_a = [a[0]]

for i in a[1::]:
    flag = 1
    for j in new_a:
        if i % j == 0:
            flag = 0
            break
    if flag:
        new_a.append(i)

print(len(new_a))

Submission status: Wrong Answer

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

N = int(input())
A = list(map(int,input().split()))
A.sort()
B = []
for i in range(A[-1]+1):
    B.append(0)
count = 0
for a in A:
    diva = make_divisors(a)
    del diva[0]
    diva.reverse()
    for divele in diva:
        if B[divele] != 0:
            if divele == a:
                B[divele] = 2
            break
    else:
        B[a] = 1
print(B.count(1))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率

def input(): return sys.stdin.readline()[:-1]
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    A = list(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    
    A.sort()
    ma=A[-1]
    l=[0]*(ma+1)
    
    count=0
    pa=0
    f=0
    for a in A:
        if pa==a:
            if f==1:
                count-=1
                f=0
        elif not l[a]==1:
            count+=1
            f=1
            for i in range(a,ma+1,a):
                l[i]=1
        pa=a
    print(count)
    #print(l)
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    count = int(input())
    integars = sorted(int(x) for x in input().split())
    ans = 0
    # pre = integars[0]
    chosen = True
    for i, x in enumerate(integars):
        if i == 0:
            pre = x
            continue
        if chosen and pre != x:
            ans += 1
        chosen = True
        for j, y in enumerate(integars):
            if i == j:
                break
            if x % y == 0:
                chosen = False
                break
        pre = x
        if chosen and i == count - 1:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
D=defaultdict(int)
N=int(input())
A=list(map(int,input().split()))
n = 10**6
prime = {i for i in range(2,n)}
for i in range(2,n):
    if i in prime:
        for j in range(i*2,n,i):
            if j in prime:
                prime.remove(j)
for x in A:
    D[x]+=1
ans=0
d=[]
K=list(D.keys())
K.sort()
for key in K:
    if D[key]==1:
        if key in prime:
            ans+=1
            d.append(key)
        else:
            if all(key%number!=0 for number in d):
                ans+=1
            d.append(key)
    else:
        d.append(key)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

def main():
    N, *A = map(int, open(0).read().split())

    ctr = Counter(A)
    memo = []
    ans = 0

    for a in sorted(A):
        if a == 1:
            if ctr[a] == 1:
                ans = 1
            break

        if ctr[a] == 1:
            for v in memo:
                if v > int(a ** 0.5):
                    if a % v != 0:
                        ans += 1
                    break
                if a % v == 0:
                    break
            else:
                ans += 1

        memo.append(a)

    print(ans)

    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(rs())
def rs_(): return [_ for _ in rs().split()]
def ri_(): return [int(_) for _ in rs().split()]

N = ri()
A = sorted(ri_())
cnt = 0
tmp = 0
f = 0
ff = 0
for i in range(N):
    for j in range(i):
        if A[i] == A[j]:
            if f == 1:
                cnt += 1
            else:
                f = 1
                cnt += 2
            ff = 1
            break
        elif A[i] % A[j] == 0:
            f = 1
            cnt += 1
            ff = 1
            break
    if ff == 0:
        f = 0
    else:
        ff = 1
print(N - cnt)

Submission status: Wrong Answer

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

for g in range(n):
    temp = a[g]
    loop = False
    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
                if i**cnt in exist:
                    loop=True
                    break
    if loop:
        continue
    else:
        exist.add(a[g])

if len(exist)==1:
    print(0)
else:
    print(len(exist))

Submission status: Wrong Answer

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

a.sort()
a_wk = set()
a_wk.add(a[0])

ans = 0
if n == 1 or a[0] < a[1]:
  ans = 1

for i in range(1, n):
  if a[i] == a[i - 1]:
    continue
  if i < n - 1 and a[i] == a[i + 1]:
    continue
  flag = True
  for _a in a_wk:
    if _a * 2 > a[i]:
      break
    if a[i] % _a == 0:
      flag = False
      break
  if flag:
    ans += 1
    a_wk.add(a[i])

print(ans)

Submission status: Wrong Answer

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

X.sort()
Y=[]
onaji=0
pre=-1
for x in X:

    if x==pre:
        onaji+=1
        pre=-1

    flag=0#warenai

    for y in Y:
        if x!=y and x<2*y:
            break
        if x%y==0:
            flag=1#wareta
            break

    if flag==0:#全部われなかった
        Y.append(x)
        pre=x

print(len(Y)-onaji)

Submission status: Wrong Answer

Solution code:
import sys

import numpy as np

readline = sys.stdin.buffer.readline


def solver(A):
    c = 0
    A = np.array(A)
    while True:
        if len(A) == 0:
            break
        a = A[0]
        A = A[A % a != 0]
        c += 1
    return c


def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    A = list(set(A))

    if len(set(A)) == 1:
        print(0)
    else:
        c = solver(A)
        print(c)

main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
cnt = 0
flag = True
A.sort()
tmp = []
idx1 = 0
isDelete = False
while True:
    for idx2, i in enumerate(A):
        if i == A[idx1] and idx1 != idx2:
            pass
        else:
            if idx1 != idx2:
                if i%A[idx1] != 0:
                    tmp.append(i)
            else:
                tmp.append(i)
    A = tmp.copy()
    tmp = []
    if idx1 >= len(A) - 1:
        break
    idx1 += 1

print(len(A))

Submission status: Wrong Answer

Solution code:
N = int(input())
A_li_org = list(map(int,input().split()))
A_li = sorted(list(set(A_li_org)))
tisai = []
ans = 0
flag = False
for i in A_li:
    for j in tisai:
        if i % j == 0:
            flag = True
            break
    tisai.append(i)
    if not flag:
        ans += 1
    flag = False
if len(A_li) == 1:
    print(0)
else:
    print(ans)

Submission status: Wrong Answer

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

nums.sort()

t = [nums[0]]

if n >= 2 and len(set(nums)) == 1:
    print(0)
else:
    for num in nums:
        is_add = True
        for n in t:
            if num % n == 0:
                is_add = False
                break
        
        if is_add:    
            t.append(num)
          
    print(len(t))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
if len(set(a)) == 1:
  ans = 0
else: 
  for i in range(n):
    k = 1
    for  j in range(0, i):
      if a[i] % a[j] != 0:
        next
      else:
        k = 0
        break
    ans += k
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
from numba import njit

readline = sys.stdin.readline

@njit('i8(i8[:])', cache=True)
def solve(a):
    ans = 0
    while len(a):
        if len(a) != 1:
            if a[0]==a[1]:
                a = a[a != a[0]]
                continue
        ans += 1
        a = a[a % a[0] != 0]
    return ans

n = int(input())
a = np.array(readline().split(), dtype=np.int64)
a.sort()
print(solve(a))

Submission status: Wrong Answer

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

for i in range(n):
    for tmp in arr:
        if a[i] % tmp == 0:
            break
    else:
        arr.append(a[i])

print(len(arr))

Submission status: Wrong Answer

Solution code:
# import sys
# import math #sqrt,gcd,pi
# import decimal
# import queue # queue
# import bisect
# import heapq # priolity-queue
# import time
# from itertools import product,permutations,\
#     combinations,combinations_with_replacement
# 重複あり順列、順列、組み合わせ、重複あり組み合わせ
# import collections # deque
# from operator import itemgetter,mul
# from fractions import Fraction
# from functools import reduce

mod = int(1e9+7)
# mod = 998244353
INF = 1<<50

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

class Prime():
    # コンストラクタ
    # エラストテネスの篩
    def __init__(self,num):
        self.num = num
        self.sieve = [0] * (self.num + 1)
        self.sieve[0] = -1
        self.sieve[1] = -1
        for i in range(2,self.num+1):
            if not self.sieve[i]:
                self.sieve[i] = i
                for j in range(i * i,self.num + 1,i):
                    if not self.sieve[j]:
                        self.sieve[j] = i

    def PrimeFact(self,num = None):
        if num is None:
            num = self.num
        fact = []
        while self.sieve[num] != num:
            fact.append(self.sieve[num])
            num //= self.sieve[num]
        fact.append(num)
        return fact

def main():
    n = int(input())
    a = readInt()
    A = []
    prime = Prime(max(a))
    for i in range(n):
        A.append(set(prime.PrimeFact(a[i])))
    m = {}
    for x in A:
        x = tuple(x)
        if x in m.keys():
            m[x] += 1
        else:
            if not m:
                m[x] = 1
                continue
            z = m.keys()
            for y in z:
                if len(set(x)|set(y))>max(len(set(x)),len(set(y))):
                    m[x] = 1
                    break
                else:
                    m[y] += 1
    ans = 0
    for x in m.keys():
        if m[x]==1:
            ans += 1
    print(ans)
    return

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter

n=int(input())
l=list(map(int,input().split()))
c=Counter(l)
l=sorted([x for x in c])
if l[0]==1: print(1);exit()
sm=0
if len(l)==1: print(0);exit()
for i in range(1,len(l)):
    if c[l[i]]>1:continue
    for j in range(i):
        if l[i]%l[j]==0:
            break
    else:sm+=1
print(sm+1)

Submission status: Wrong Answer

Solution code:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
def get_primes(n=10**6):
    """Return a list of prime numbers n or less"""
    is_prime = [True]*(n+1)
    is_prime[0] = 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]]
from collections import deque
#======================================================#
def main():
    n = II()
    aa = MII()
    aa.sort()
    if len(set(aa)) == 1:
        print(0)
        exit()
    lst = []
    ans = []
    while aa:
        t = aa[0]
        ans.append(t)
        for a in aa[1:]:
            if a%t!=0:
                lst.append(a)
        aa = lst
        lst = []
    print(len(ans))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter

N = int(input())
a_list = [int(_) for _ in input().split()]

a_list = list(sorted(a_list))
c = Counter(a_list)
dup_list = [k for k, v in c.items() if v > 1]

b_list = a_list

ans = []

while b_list != []:
    x = b_list[0]
    a_list = list(filter(lambda z: (z%x != 0 or z==x) and x not in dup_list, a_list))
    b_list.pop(0)

print(len(a_list))

Submission status: Wrong Answer

Solution code:
import math
from collections import defaultdict
n = int(input())
a = list(map(int,input().split()))
a.sort()
num = 10**6+10
input_list = defaultdict(int)
sqrt = math.sqrt(num)

ans = 0
for serial in a:


    if serial >= sqrt:continue

    if input_list[serial] == 1:
        # print(serial)
        continue
    if input_list[serial] == 2:
        # print(serial)
        ans -= 1
        input_list[serial] = 1
        continue
    input_list[serial] = 2
    for s in range(serial*2, num, serial): 
        input_list[s] =1
    ans +=1
# for i in a:
    # print(i,input_list[i])
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
X=set()
def divisor_enu(N):
   temp=[]
   for i in range(2,int(N**0.5)+1):
      if N%i==0:
         while N%i==0:
            N//=i
         if i in X or N in X:
            return None
         else:
            temp.append(i)
   if N != 1:
      X.add(N)
   for k in temp:
      X.add(k)
S=list(map(int,input().split()))
if len(set(S)) == 1:
   print(0)
   exit()
S.sort()
for j in S:
   divisor_enu(j)
print(len(X))

Submission status: Wrong Answer

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

A = list(set(A))
A = sorted(A, reverse=True)
num = 0
N = len(A)
for i in range(N):
    flag = True
    for j in range(i+1, N):
        if A[i] % A[j] == 0:
            flag = False
            break
    if flag == True:
        print(A[i])
        num += 1
print(num)

Submission status: Wrong Answer

Solution code:
import math

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

A.sort()


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

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

count = 0

for i in range(0, N):
    flag = True
    a = A[i]
    g = math.sqrt(a)
    for j in range(0, min(i + 2, N)):
        if (i != j and a % A[j] == 0):
            flag = False
            break
        if (A[j] > g):
            break

    if (flag):
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
### ----------------
### ここから
### ----------------

import sys

def resolve():
    readline=sys.stdin.readline

    #n,m,k=map(int, readline().rstrip().split())
    n=int(readline())
    arr=list(map(int, readline().rstrip().split()))
    if n==1:
        print(0)
        return

    arr.sort()
    #print(arr)
    ans=0
    for i in range(n):
        flg=0
        if i==0:
            if arr[i]!=arr[i+1]:
                ans+=1
            continue
        h=arr[i]//2
        for j in range(0,i):
            if arr[i]%arr[j]==0:
                flg=1
                break
            if arr[j] > h:
                break
        if flg==0:
            ans+=1
    print(ans)
    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Wrong Answer

Solution code:
N = int(input())
#4
A = [int(i) for i in input().split()]
#5 5 5 5
#A = [map(int,input().split()) for i in range(N)]

A.sort(reverse=True)

cnt = 0

for i in range(N):
	flag = 0
	for j in range(i+1,N):
		if A[i] % A[j] == 0:
			flag = 1

	if A[-1] in A[:-1]:
		flag = 1

	if flag == 0:
		cnt += 1
	#print(cnt)

print(cnt)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)
if A[N-1]==A[N-2]:
	S=-1
else:
	S=0
for i in range(N):
	frag = 0
	for j in range(i+1,N):
		if  A[i]%A[j]==0:
			frag=1
			break
	if frag == 0:
		S=S+1
print(S)

Submission status: Wrong Answer

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

a = sorted(set(a))
a.reverse()
print(a)
ans = 0

for i in range(len(a)):
    for j in range(len(a)-1,-1,-1):
        #print(i,j)
        if i == j:
            continue
        #print(a[i],a[j])
        if a[i] % a[j] == 0:
            break
        if j == n - 1:
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jun 14 21:14:26 2020

@author: NEC-PCuser
"""

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

A.sort()


li = []
before_value = 0
next_flg = False
for n in A:
    if len(li) == 0:
        li.append(n)
        next_flg = True
    if before_value == n:
        if li[len(li) - 1] == n:
            li.pop(len(li) - 1)
        next_flg = False
        before_value = n
        continue
    before_value = n
    if next_flg is True:
        next_flg = False
        continue
    for n2 in li:
        if (n % n2 == 0):
            break
        if (n < n2 * 2):
            li.append(n)
            break
    else:
        li.append(n)

print(len(li))