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 copy
from collections import Counter

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

counter = Counter(seq)
candidate = set(seq)

for k, v in counter.items():
    if v > 1:
        candidate.remove(k)
count = 0

for i, x in enumerate(sorted(candidate)):
    for y in copy.copy(candidate):
        if x == y:
            continue
        if y % x == 0:
            candidate.remove(y)

print(len(candidate))

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
L=sorted(A)
for i in L:
    for j in L[L.index(i)+1:]:
        if j%i==0:
            L.pop(L.index(j))
        else:
            None
print(len(L))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
count = 0
notdiv = [0]*n
for i in range(n):
    x = 0
    for j in range(n):
        if notdiv[j] == 1 or i == j:
            continue
        if a[i]%a[j] == 0:
            break
        if a[j]%a[i] == 0:
            x = 1
        if j == n-1:
            count +=1
            if x == 0:
                notdiv[i] = 1
print(count)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import math

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


A = sorted(A)

dd = 0
set_a = set(A)
for sa in set_a:
    if A.count(sa > 1):
        dd += 1

queue = []


for a in A:

    in_queue = True

    for q in queue:
        if a % q == 0:
            in_queue = False

    if in_queue:
        queue.append(a)


print(len(queue)-dd)

Submission status: Wrong Answer

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

def main():
    ans = 0
    if N == 1:
        print(1)
        return
    else:
        if A[0] != A[1]:
            ans += 1
    for i in range(1, N):
        flag = True
        for j in range(i):
            if A[i]%A[j] == 0:
                flag = False
                break
        if flag:
            ans += 1
    print(ans)
main()

Submission status: Wrong Answer

Solution code:
N=int(input())
hitoketa=[]
count=0
A=list(map(int,input().split()))
A.sort()
for i in range(min(1000,N)):
    hitoketa.append(A[i])
for i in range(len(hitoketa)):
    for j in range(len(hitoketa)):
        if hitoketa[i]%hitoketa[j]==0 and hitoketa[i]!=hitoketa[j]:
            hitoketa[i]=10**7+1
#hitoketa.sort()
#print(hitoketa)
hitoketa_set=set(hitoketa)
for i in A:
    for j in hitoketa_set:
        if i != j and i%j==0:
            count+=1
            continue
print(count)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
from collections import Counter

input = sys.stdin.readline


def S():
    return input().rstrip()


def I():
    return int(input())


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


n = I()
al = list(MI())

al.sort()
f = set()
c = Counter(al)

for k, v in c.items():
    if v > 1:
        f.add(k)

half = al[n - 1] / 2

ans = np.array(al)
c = 0
for a in al:
    if a > half:
        print(c + len(set(al) - f))
        exit()
    if a in f:
        continue
    f |= set(ans[ans % a == 0])
    c += 1

Submission status: Wrong Answer

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

answers = 0
ng_list = []

for i, a in enumerate(A):
    if i in ng_list:
        continue
    for j, b in enumerate(A):
        if j in ng_list:
            continue
        if i == j:
            continue
        ng_new = []
        if a % b == 0:
            ng_new.append(i)
        if b % a == 0:
            ng_new.append(j)
        if ng_new:
            ng_list += ng_new
            break
print(N - len(set(ng_list)))

Submission status: Wrong Answer

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

sum = 0

while True:
    X = A.pop(0) #左端をとる
    
    i = len(A)
    for Y in reversed(A):
        i -= 1

        if Y%X == 0:
            A.pop(i)

    if NG.count(X) == 0:
        sum += 1

    if len(A) == 0:
        break

print(sum)

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 < 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])

print(c)

Submission status: Wrong Answer

Solution code:
from itertools import product

N = int(input())
A = list(map(int, input().split()))
# N = 10
# A = list(map(int, "33 18 45 28 8 19 89 86 2 4".split()))
ans = set(A)

B = list(ans)

while True:
    for ai, aj in product(B, A):
        if ai == aj:
            continue
        if ai % aj == 0:
            if ai in ans:
                ans.remove(ai)
                break
        if aj % ai == 0:
            if aj in ans:
                ans.remove(aj)
                break
    if len(B) == len(ans):
        break
    B = list(ans)
print(len(ans))

Submission status: Wrong Answer

Solution code:
from collections import Counter

def main():
  n, = list(map(int, input().split()))
  aa = sorted(map(int, input().split()))
  cc = Counter(aa)
  
  res = 0
  while aa:
    x = aa[0]
    c = cc[x]
    if c > 1:
      aa = aa[c:]
      continue
    res += 1
    aa = [a for a in aa[1:] if a % x]
  print(res)
    
  
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

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

a.sort(reverse=True)

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

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
results = []
if A[0]==A[-1]:
  print(0)
else:
  while(A):
    a = A.pop(0)
    if a in A:
      A = [i for i in A if i!=a]
    else:
      results.append(a)
    AA = [i for i in A if i%a!=0]
    A = AA
  print(len(results))

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
n = int(input())
a = list(set(map(int, input().split())))
a.sort()

if len(a) == 1:
    print(0)
else:
    ans = 1
    ans_list = [a[0]]
    for i in range(1, len(a)):
        check = a[i]
        ok = True
        for j in ans_list:
            if check % j == 0:
                # ans_list.append(check)
                ok = False
                break
        if ok:
            ans_list.append(check)
    # print(ans)
    print(len(ans_list))

Submission status: Wrong Answer

Solution code:
def resolve():
    import sys
    input = sys.stdin.readline
    # 整数 1 つ
    n = int(input())
    # 整数複数個
    # a, b = map(int, input().split())
    # 整数 N 個 (改行区切り)
    # N = [int(input()) for i in range(N)]
    # 整数 N 個 (スペース区切り)
    A = list(map(int, input().split()))
    # 整数 (縦 H 横 W の行列)
    # A = [list(map(int, input().split())) for i in range(H)]

    if n == 1:
        print(1)
    else:
        A.sort()
        if A[0] == 1:
            if A[1] == 1:
                print(0)
            else:
                print(1)
        elif len(list(set(A))) == 1:
            print(0)
        else:
            cnt = 0
            for i in range(n):
                flag = False
                for j in range(n-i-1):
                    if A[n-1-i] % A[j] == 0:
                        flag = True
                        break
                if flag == False:
                    cnt += 1
            print(cnt)

resolve()

Submission status: Wrong Answer

Solution code:
from numba import jit
N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)
ans=0
if len(set(A))==1:
    print(0)
    exit()

@jit
def solve(a,n):
    ans=0
    for i in range(n):
        k=0
        for j in range(i+1,n):
            if a[i]!=a[j]:
                if a[i]%a[j]!=0:
                    k+=1
        if k==max(0,n-1-i):
            ans+=1
    return ans
print(solve(A,N))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
ans = 0
def check(s):
    count = 0
    for j in range(n-1):
        if s%a[j+1] == 0 and s != a[j+1]:
            count = 1
            return count
    else:
        return count

for i in range(n):
    ans += check(a[i])
if ans == 0:
    print(ans)
else:
    print(n-ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import bisect
N = int(input())
A = list(map(int,input().split()))

cnt = Counter(A)
A.sort()
ans = 0
for i in range(len(A)):
    if cnt[A[i]] > 1:
        continue
    idx = bisect.bisect_left(A, pow(A[i],0.5))
    J = min(idx+1,i)
    ok = True
    for j in range(J):
        if A[i] % A[j] == 0:
            ok = False
    if ok:
        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 = []
li2 = []
before_value = 0
next_flg = False
for n in A:
    if len(li) == 0:
        li.append(n)
        li2.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 li2:
        if (n % n2 == 0):
            break
        if (n < n2 * 2):
            li2.append(n)
            li.append(n)
            break
    else:
        li2.append(n)
        li.append(n)

print(len(li))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = input().split()
a = [int(i) for i in a]
a.sort(reverse=True)


if n == 1:
    print(0)
else:
    if a[-1] == a[-2]:
        cnt = 0
    else:
        cnt = 1
    for i in range(n-1):
        flg = False
        for j in reversed(range(i+1,n)):
            if a[i] % a[j] == 0:
                flg = True
                break
        if flg == False:
            cnt += 1
    print(cnt)

Submission status: Wrong Answer

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

a.sort(reverse=True)
print(a)
ans=n
for i in range(n):
    if i==n-1:
        if a[i]==a[i-1]:
            ans-=1
    for j in range(i+1,n):
        if a[i]%a[j]==0:
            ans-=1
            break
print(ans)

Submission status: Wrong Answer

Solution code:
import collections

n= int(input())
a= list(map(int, input().split()))
a=collections.Counter(a)
a=a.most_common()
b=[]
for i in range(len(a)):
    if a[i][1]==1:
        b.append(a[i][0])

v=[0]*(pow(10,7)+1)
b.sort()
ans=0
for i in b:
    if v[i]==0:
        ans+=1
        x = pow(10, 7) // i
        for j in range(1,x + 1):
            v[i*j]=1
print(ans)

Submission status: Wrong Answer

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

a.sort()
na = np.array(a)
#for i in na:
cnt = 0
while cnt < len(a):
    #na = na[na % i != 0]
    tmp = na[0]
    na = na[na % a[cnt] != 0]
    #print(na)
    na = np.append(na, tmp)
    #print(na)
    cnt +=1


ans = len(set(na))
if ans == 1:
    print(0)
    exit()

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
hitoketa=[]
count=0
A=list(map(int,input().split()))
A.sort()
for i in range(min(100,N)):
    hitoketa.append(A[i])
for i in range(len(hitoketa)):
    for j in range(len(hitoketa)):
        if hitoketa[i]%hitoketa[j]==0 and hitoketa[i]!=hitoketa[j]:
            hitoketa[i]=10**7+1
#hitoketa.sort()
#print(hitoketa)
hitoketa_set=set(hitoketa)
for i in A:
    for j in hitoketa_set:
        if i != j and i%j==0:
            count+=1
            continue
print(count)

Submission status: Wrong Answer

Solution code:
num=int(input())
date0=list(map(int, input().split(" ")))
date0=set(date0)
date0=sorted(date0)
if len(date0)==1:
    print(0)
else:
    i=0
    b=0
    c=0
    while i<len(date0)-1:
        for j in range(len(date0)-i-1):
            if date0[j+i+1]%date0[i]==0:
                date0[j+i+1]=0
                b+=1
                if date0[i+1]==date0[i]:
                    c=1
        if b>0:
            for k in range(b):
                date0.remove(0)
            b=0
            k=0
        if c==1:
            del date0[i]
            i-=1
        i+=1
    print(len(date0))

Submission status: Wrong Answer

Solution code:
n=int(input())
*a,=map(int, input().split())
a.sort()
b=[1]*n
for i in range(n):
    if not b:
        continue
    for j in range(i+1,n):
        if a[j]%a[i]==0:
            b[j]=0
print(sum(b))

Submission status: Wrong Answer

Solution code:
import math

n = int(input())
aL = sorted(list(map(int, input().split(" "))))

ans = n
for i in range(n - 1, -1, -1):
    for j in range(i):
        if aL[j] * 2 > aL[j]:
            break
        if aL[i] % aL[j] == 0:
            ans -= 1
            break

d = set()
for a in aL:
    d.add(a)
if len(d) == 1 and n != 1:
    print(0)
    exit()

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

n = int(input())
A = sorted(map(int, input().split()))
c = Counter(A)
flag = [False] * n
for i in range(n):
    if c[A[i]] > 1:
        flag[i] = True
    if flag[i] == False:
        for j in range(i+1, n):
            if A[j] % A[i] == 0:
                flag[j] = True
print(flag.count(False))

Submission status: Wrong Answer

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

cnt = 0
for i in range(n):
    flg = False
    for j in range(i+1,n):
        if i==j:
            continue
        if a[i] % a[j] == 0:
            flg=True
    cnt += 0 if flg else 1
print(cnt)

Submission status: Wrong Answer

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

for i in a:
  if len([j for j in a if i%j == 0 and i != j]) == 0:
    cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    answer = n
    chk = [0 for _ in range(a[-1] + 1)]
    for aa in a:
        chk[aa] += 1
    if a[0] == 1:
        answer = 0 if chk[1] - 1 else 1
    else:
        for i in range(a[-1] + 1):
            if chk[i] == 1:
                for j in range(2 * i, a[-1] + 1, i):
                    answer -= chk[j]
                    chk[j] = 0
            else:
                answer -= chk[i]
        answer = max(answer, 0)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import itertools
from operator import mul
from functools import reduce

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

count = 0

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

for i in range(0, N):
    if A[i] in A[:i] or A[i] in A[i+1:]:
        continue
    factors = prime_factorize(A[i])
    flag = False
    for j in range(1, len(factors)):
        fac = list(itertools.combinations(factors, j))
        for f in fac:
            elm = reduce(mul, f)
            if elm in A:
                flag = True
                break
        if flag:
            break
    if not flag:
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=0
ak=[]
cur=a[0]
miss=False
for i in a[1:]:
	if i==cur:
		miss=True
	else:
		if not miss:
			ak.append(cur)
		miss=False
		cur=i
if miss==False:
	ak.append(cur)
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:
from collections import Counter

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

    ctr = Counter(A)
    memo = []
    dp = set()
    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 or ((v not in dp) and (a // v not in dp)):
                        ans += 1
                    break
                if a % v == 0 and ((v in dp) or (a // v in dp)):
                    break
            else:
                ans += 1

        memo.append(a)
        dp.add(a)

    print(ans)

    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
import collections
sys.setrecursionlimit(10**6)


def main(input, print):
    n = int(input())
    a = list(map(int, input().split()))
    a = list(collections.Counter(a).items())
    b = []
    for i in range(len(a)):
        if a[i][1] == 1:
            b.append(a[i][0])
    b.sort()
    ans = 0
    for i in range(len(b)):
        isDiv = False
        for j in range(i):
            if b[i] % b[j] == 0:
                isDiv = True
                break
        if not isDiv:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main(sys.stdin.readline, print)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    Pl = [A for A in input().split()]
    Pl = list(set(map(int, Pl)))
    Pl.sort(reverse = True)
    #print(Pl)
    ans = len(Pl) * (len(Pl)-1) / 2
    #print(ans)
    count = 1
    for i in range(len(Pl)-1) :
        flag_i = 0
        flag_c = 0
        #print("--")
        #print(Pl[i])
        #print("--")
        for j in range(i+1 , len(Pl)) :
            val = Pl[i] % Pl[j]
            #print(val)
            if val != 0 and flag_i == 0:
                #print(i)
                flag_i = 1
                count += 1
            elif val == 0 and flag_c == 0 :
                flag_c = 1
        if flag_c == 1 and flag_i == 1 :
            count -= 1

    if len(Pl) == 1 :
        print("0")
    else :
        print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
l = [int(x) for x in input().split()] + [100001]
l.sort()
ans = 0
t = 0
M = [False] * 10 ** 6
for i in range(N):
    if not M[l[i]-1]:
        if l[i] != l[i+1]:
            ans += 1
        t = l[i]
        while t <= 10 ** 6:
            M[t-1] = True
            t += l[i]
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
def is_prime(n,A):
    if n == 1:
        return False
    for i in A:
        if i!=n and n % i == 0:
            return False
    return True
a=0
B=[x for x in set(A) if A.count(x) == 1]
if 1 in B:
    a=1
else:
    for i in B:
        if is_prime(i,B):
            a+=1
print(a)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
if a[0]==a[n-1]:
  print(0)
else:
  ans=[]
  while len(a)!=0:
    now=a.pop(0)
    ans.append(now)
    b=len(a)
    dif=0
    for i in range(0,b):
      if a[i-dif]%now==0:
        aa=a.pop(i-dif)
        dif+=1
  print(len(ans))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def main():
    N = int(input().strip())
    l = sorted([int(i) for i in input().strip().split()])
    for i, n in enumerate(l):
        flag = False
        if n == -1:
            continue
        if i < len(l)-1:
            for j, m in enumerate(l[i + 1:]):
                if m == n:
                    flag = True
                if m % n == 0:
                    l[i + j + 1] = -1
        if flag:
            l[i] = -1
    ans = len(set(l)) - 1

    return ans


if __name__ == "__main__":
    print(main())

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(-(-a[g]**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 not loop and not temp in exist:
        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()))
if n == 1:
    print(1)
    exit()
A =list(set(A))
if len(A) == 1:
    print(0)
    exit()
ans = 0
for i,a in enumerate(A):
    flg = 0
    for i2,a2 in enumerate(A):
        if i == i2:
            continue
        if a % a2 == 0:
            flg = 1
            break
    if flg == 0:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
ans = 0
for i in range(N):
    flg = 0
    for j in range(i):
        if A[j] > int(-(-A[i]**0.5//1))+1:
            break
        if i != 0:
            if A[i]%A[j] == 0:
                flg = 1
                break    
    if flg == 0:
        if i +1 < N:
            if A[i+1] != A[i]:
                ans += 1
        else:
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
a_cnt = Counter(a)

a = sorted(list(set(a)))
n = len(a)
def divisor(n):
    res = []
    for i in range(1, int(n ** 0.5)+1):
        if n % i == 0:
            res.append(i)

            if i != n // i and i != 1:
                res.append(n // i)
    return res

divs = [set(divisor(a[i])) for i in range(n)]

ans = 0
memo = set(a)
for i in range(n):
    if a_cnt[a[i]] == 1:
        if memo & divs[i] == set():
            ans += 1


print(ans)

Submission status: Wrong Answer

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

if a.count(1) == 1:
    print(1)
    exit()
if a.count(1) >= 2:
    print(0)
    exit()
a.sort()
d = {}

ans = 0



for i in range(n):
    if a[i] not in d.keys():
        ans += 1
        for j in range(1,10):
            if j == 1:
                d[a[i]*j] = 1
            else:
                d[a[i]*j] = 0
    else:
        if d[a[i]] == 1:
            ans -= 1
            d[a[i]] = 2

print(ans)

Submission status: Wrong Answer

Solution code:
def 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()))
b = list(map(lambda n: divisors(n), a))

cnt = n
for i in range(n):
    for j in range(n):
        if i != j and a[i] in b[j]:
            cnt -= 1
            break
print(cnt)

Submission status: Wrong Answer

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

#print(dup)

sorted_A_list = sorted(dup)
ans = 0

#print(sorted_A_list)

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

print(ans)

Submission status: Wrong Answer

Solution code:
#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math
from collections import deque
import itertools
import heapq
#import bisect
from fractions import Fraction
import copy
from functools import lru_cache
from collections import defaultdict
import pprint


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

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]

def ret(a):
    c=[None]*(len(a)-1)
    if len(a)==1:
        return a[0]
    elif len(a)==0:
        return 0
    for i in range(1,len(a)):
        c[i-1]=abs(a[i]-a[i-1])
    return ret(c)

def soinsubunkai(n):
    a = []
    i = 1
    while i*i <= n:
        if n % i == 0 and i!=1:
            a.append(i)
            n=n//i

        if n% i !=0 or i==1:
            i += 1
    nokori=[n]
    return a + nokori

def main():
    n=int(input())
    a=list(map(int,input().split()))
    a=sorted(a)
    count=0
    if n>=2:
        for i in range(1,n):
            temp=0
            for j in range(i):
                if a[i]%a[j]==0:
                    temp=1
            if temp==0:
                count+=1
        if a[0]!=a[1]:
            count+=1
    print(count)









if __name__ == "__main__":

    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
import collections
import bisect


def divisor(n):
    i = 1
    table = []
    while(i * i <= n):
        if n % i == 0:
            table.append(i)
            table.append(n // i)
        i += 1
    table = list(set(table))
    return table


N = int(input())

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

A.sort()

ans = 0
ans = N
for i in range(N):
    divs = divisor(A[i])
    #print(A[i], "divs", divs)
    for d in divs:
        if i != 0 and d != 1:
            #print(A[:i], d, bisect.bisect_left(A[:i], d))
            if len(A[:i]) <= bisect.bisect_left(A[:i], d):
                continue
            if A[:i][bisect.bisect_left(A[:i], d)] == d:
                ans -= 1
                break
        if i < N - 1:
            if A[i] == A[i + 1]:
                ans -= 1
                break
print(ans)

Submission status: Wrong Answer

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

A = sorted(A, reverse = True)
ans = 0

if A.count(A[-1]) == 1:
    ans = 1 

for i in range(N):
    B = A[i]
    flag = 0
    j = i + 1
    if j == N:
        flag = 1
    while j < N:
        if B % A[j] == 0:
            flag = 1
            break
        if B < A[j]:
            break
        j += 1
    if flag == 0:
        ans += 1

print(ans)

Submission status: Wrong Answer

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

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

print(cnt)

Submission status: Wrong Answer

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

ans = 0
for i in range(n):
    if i == 0 and n > 1:
        if A[i] % A[i+1] != 0:
            ans += 1
    for j in range(i):
        if A[i] % A[j] == 0:
            break
        if j == i - 1:
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
M = int(input())
A=list(map(int,input().split()))
A.sort()
k=0
if len(A)==1:
    print(0)
else:
    while True:
        if k>=len(A)-1:
            break
        for i in range(len(A)-1,k,-1):
            if A[i]%A[k]==0:
                A.pop(i)
        k+=1

    print(len(A))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n = int(input())
arr = list(map(int,input().split()))
d = defaultdict(int)
for i in arr:
	d[i]+=1
arr.sort()
maxn = 10**6+100
prime = [True for i in range(maxn+1)]
p = arr[0]
ind = 0
while p*p<=maxn:
	if prime[p]==True:
		for i in range(p+p,maxn+1,p):
			prime[i] = False
	if ind+1<n:
		ind+=1
		p = arr[ind]
	else:
		break
cnt = 0
for i in arr:
	if prime[i]==True and d[i]==1:
		cnt+=1
print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
# a = sorted(a)
a.sort()
check = True
ans = 0
double = []
for i in range(n):
    if not i == 0:
        if a[i-1] == a[i]:
            double.append(a[i])
    for j in range(0, i):
        if a[j]*2 > a[i]:
            break
        if i == j:
            continue
        if a[i]%a[j] == 0:
            check = False
            break

    if check:
        ans += 1
        # print(i)
    check = True

for i in set(double):
    ans -= a.count(i)
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 = []
li2 = []
before_value = 0
next_flg = False
for n in A:
    if len(li) == 0:
        li.append(n)
        li2.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 li2:
        if (n % n2 == 0):
            break
        if (n < n2 * n2):
            li2.append(n)
            li.append(n)
            break
    else:
        li2.append(n)
        li.append(n)

print(len(li))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = sorted(list(map(int, input().split(" "))))
for i in range(0, n):
    if len(a) <= i:
        break
    t = a[0]
    a = list(filter(lambda x: x % t != 0, a)) + [t]

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

Submission status: Wrong Answer

Solution code:
import math
from collections import defaultdict
def r():
    return int(input())
def rm():
    return map(int,input().split())
def rl():
    return list(map(int,input().split()))

'''D'''
n=r()
a=rl()
b=[0]*n
a.sort(reverse=True)
c=defaultdict(int)
cnt=0
for i in range(n-1):
    if c[i]==1:
        cnt+=1
        continue
    elif c[i]==2:
        continue
    trr=True
    for j in range(i+1,n):
        if a[i]%a[j]==0:
            trr=False
            break
    if trr==True:
        cnt+=1
        c[a[i]]=1
    else:
        c[a[i]]=2
if c[a[-1]]!=2:
    cnt+=1
print(cnt)