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, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce, lru_cache  # @lru_cache(None)
from fractions import gcd
import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**6)
# ----------------------------------------------------------- #

n = int(input())
A = list(int(x) for x in input().split())
A.sort()
ans = 0
while A:
    tmp = A[0]
    if len(A) > 1:
        if tmp not in A[1:]:
            ans += 1
        index = bisect_left(A[1:], tmp*2)
        A = A[1:index] + [a for a in A[index:] if a % tmp != 0]
    else:
        ans += 1
        break
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
N = int(input())
A = sorted(list(map(int,input().split())))
C = collections.Counter(A)
L = []
for i in range(N):
    if C[A[i]] != 1:
        continue
    for l in L:
        if A[i]%l == 0:
            break
    else:
        L.append(A[i])

print(len(L))

Submission status: Wrong Answer

Solution code:
n=int(input())
l=list(map(int,input().split()))
l.sort()
chols={}
ansls=[0]*n
ans=0
for i in range(n):
  s=l[i]
  st=s*0.5
  flag=True
  for j in range(ans):
    if s%ansls[j]==0:
      if s==ansls[j]:
        chols[s]=1
      flag=False
      break
    if ansls[j]>st:
      break
  if flag:
    ansls[ans]=s
    ans+=1
de=chols.keys()

print(ans-len(de))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
flag_lst = [0]*N

for i in range(N):
    for j in range(N):
        if flag_lst[j] >= 1:
            pass
        else:
            if A[j] % A[i] == 0:
                flag_lst[j] += 1

res = 0
for flag in flag_lst:
    if flag == 1:
        res += 1

print(res)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
a.reverse()
ans=0
for i in range(n-1):
    flg=True
    for j in range(n-1,i,-1):
        if a[i]%a[j]==0:
            flg=False
            break
    if flg:
        ans+=1
if n>1:
    if a[-1]!=a[-2]:
        ans+=1
print(ans)

Submission status: Wrong Answer

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

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 len(B) == len(ans):
        break
    B = list(ans)
print(len(ans))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
M = A[-1]
T = [1] * N
for i in range(N):
  if T[i] == 1:
    for j in range(N):
      if T[j] == 1 and i != j and A[j] % A[i] == 0:
        T[j] = 0
print(sum(T))

Submission status: Wrong Answer

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

def is_prime(n):
    if n <= 1: return False
    for i in range(2, int(n**0.5)+1):
        if n%i == 0: return False
    return True

ans = [A[0]]
for a in A[1:]:
    flag = True
    if is_prime(a): ans.append(a)
    else:
        for x in ans:
            if a%x == 0: flag = False
        if flag: ans.append(a)
print(len(ans) if len(ans) > 1 else 0)

Submission status: Wrong Answer

Solution code:
from sys import stdin
from copy import deepcopy
from functools import reduce
from fractions import gcd
import math
import itertools
from collections import Counter
from itertools import chain  ##list(chain.from_iterable(l)) ##flatten
from heapq import heappush, heappop
import bisect


"""
N = int(input())
A, B = map(int,input().split())
A = list(map(int,input().split())) ## 横一列
A = [int(input()) for _ in range(N)] ## 縦一列
lst = [list(map(int,input().split())) for i in range(M)] ## 二次元
"""


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

## 例外処理
if N == 1:
  print(1)
  exit()
elif N > 1 and A[0] == 1:
  if A[1] == 1:
    print(0)
    exit()
  else:
    print(1)
    exit()
elif A[0] == A[-1]:
  print(0)
  exit()


MAXINT = int(1e6)
lst = [False for _ in range(MAXINT+1)]
for i in range(N):
  lst[A[i]] = True

for i in range(N):
  if lst[A[i]]:
    j = 2 * A[i]
    while j <= MAXINT:
      lst[j] = False
      j += A[i]

solver = [i for i in range(MAXINT+1) if lst[i]]
ans = len(solver)
print(ans)

Submission status: Wrong Answer

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

nums.sort()

t = [nums[0]]

if n >= 2 and len(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:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
a = na()
a.sort()
b = []
ans = n

for i in a:
    flag = True
    for p in range(len(b)):
        j,k = b[p]
        if j > i/2:
            x,y = b[-1]
            if i == x:
                ans -= 1
                if y == 0:
                    ans -= 1
                    b[-1] = (x,1)
            break
        if i%j == 0:
            ans -= 1
            flag = False
            break
    if flag:
        b.append((i,0))

print(ans)

Submission status: Wrong Answer

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

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

while len(a) > 0:
    i = a.pop()
    ans+=1
    n = 1
    remove_set = set()
    while i*n <= max:
        remove_set.add(i*n)
        n+=1
    a = a - remove_set

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10

    N = II()
    A = LMIIS()
    A.sort()
    ans = 0
    count = defaultdict(int)
    for a in A:
        count[a] += 1
    next_A = deque()
    for a in A:
        if count[a] == 1:
            next_A.append(a)
    A = list(next_A)

    F = deque()
    for a in A:
        f = []
        if a % 2 == 0:
            c = 0
            while a % 2 == 0:
                a //= 2
                c += 1
            f.append((2,c))
        for i in range(3,int(a**0.5)+1,2):
            if a % i == 0:
                c = 0
                while a % i == 0:
                    a //= i
                    c += 1
                f.append((i,c))
        if a != 1:
            f.append((a,1))
        F.append(f)
    Not_Divisible = defaultdict(bool)
    for f in F:
        tmp = 1
        for num, e in f:
            for i in range(e):
                tmp *= num
                if Not_Divisible[tmp] == True:
                    break
            else:
                continue
            break
        else:
            Not_Divisible[tmp] = True
    dbg(list(Not_Divisible.items()))
    print(list(Not_Divisible.values()).count(True))
        

            
            
                



    
main()

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
count_a=0
a.sort(reverse=True)
for i in range(n-1):
    count_b=0
    for j in range(n-i-1):
        k=j+i+1
        if a[i]%a[k]==0:
            count_b+=1
            continue
        else:
            pass
    if count_b==0:
        count_a+=1
if a[n-1]!=a[n-2]:
    count_a+=1
print(count_a)

Submission status: Wrong Answer

Solution code:
import sys
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
INF = 1000000000000

n = I()
a = LI()

a.sort()
f = [False]*n

if(n > 1):
    for i in range(1,n):
        if(a[i-1] == a[i]):
            f[i-1] = True
        for j in range(0,i):
            if(a[i] % a[j] == 0):
                f[i] = True
                break
        if(a[i] / a[j] < 2):
            break

count = 0
for i in range(n):
    if(not f[i]):
        count += 1

print(count)

Submission status: Wrong Answer

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

c = 0
for i in range(n-1):
    for j in range(i+1, n):
        if A[i] % A[j] == 0:
            break
    else:
        c += 1
if A[n-1]%A[n-2] != 0:
    c += 1
print(c)

Submission status: Wrong Answer

Solution code:
def solve(i,j,a):
    k=False
    sc=0
    for c in a:
        if i==len(a)-1:
            if a[i-1]==j:
                k=True
                break
        elif i==0:
            if a[i+1]==j:
                k=True
                break
        else:
            if a[i-1]==j or a[i+1]==j:
                k=True
                break
        if c>j//2:
            break
        elif c==j:
            sc+=1
            if sc>=2:
                k=True
                break
        else:
            if j%c==0:
                k=True
                break
    return k

if __name__ == '__main__':
    n=int(input())
    a=sorted(list(map(int,input().split())))
    ans=0
    for i,j in enumerate(a):
        if solve(i,j,a):
            continue
        else:
            ans+=1
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
array = list(map(int, input().strip().split()))
array.sort()
ans = 0
for i in range(N):
    for j in range(i+1):
        if i != j and(array[i] % array[j] == 0 or array[i] == array[j]) :
                break
        if j == i:
            ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
def calc():
    n, *a = map(int, open(0).read().split())
    black = set()
    r = set()
    for x in a:
        if x in r:
            black.add(x)
        r.add(x)

    r = set(a)
    count = 0
    for x in r:
        if r & black:
            continue
        if r & divis(x):
            continue
        count += 1
    return count

def divis(n):
    ds = set()
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            ds.add(i)
            if i != n // i:
                ds.add(n//i)
    return ds

print(calc())

Submission status: Wrong Answer

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

if(len(set(a)) == 1):
    print(0)
else:
    a.sort()
    b = [a[0]]
    for i in range(1,n):
        flag = 1
        for j in b:
            if(a[i]%j == 0):
                flag = 0
                break
        if(flag == 1):
            b.append(a[i])

    print(len(b))

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
if n==1:
    print(1)
    sys.exit()
a.sort()
tmp=set()
onaji=set()
if a[0]!=a[1]:
    tmp.add(a[0])
for i in range(1,n-1):
    flg=True
    if a[i]==a[i+1] or a[i]==a[i-1]:
        flg=False
    for j in tmp:
        if a[i]%j==0:
            flg=False
    if flg:
        tmp.add(a[i])
flg=True
if a[n-1]==a[n-2]:
    flg=False
for i in tmp:
    if a[n-1]%i==0:
        flg=False
if flg:
    tmp.add(a[n-1])
print(len(tmp))

Submission status: Wrong Answer

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

A = list(set(A))

for i in range(N):
    length = len(A)
    count = 0
    if i >= length:
        break
    else:
        for j in range(i+1, length):
            if A[j]%A[i] == 0:
                A[j] = 0
                count += 1
        for k in range(count):
            A.remove(0)

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

else:
    print(len(A))

Submission status: Wrong Answer

Solution code:
n = int(input())
lst = list(map(int, input().split()))
lst = list(set(lst))
lst.sort(reverse = True)
n = len(lst)
if n == 1:
  print(0)
  exit()
ans = 1
for i in range(n-1):
  judge = True
  for j in range(i+1, n):
    if lst[i]%lst[j]==0:
      judge = False
      break
  if judge:
    ans += 1
print(ans)

Submission status: Wrong Answer

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

alist = list(set(alist))

alist.sort(reverse=True)

#print(alist)

cnt = 0
for i in range(len(alist)):
    result = True
    for j in range(i+1,len(alist)):
        ai = alist[i]
        aj = alist[j]
#        print("{}[{}] {}[{}] {}/{}".format(ai,i,aj,j,(ai==aj),(ai%aj==0)))
        if ai == aj or ai%aj == 0:
            result = False
            break
    if result:
        cnt+=1

if len(alist)==1:
    print(0)
else:
    print(cnt)

Submission status: Wrong Answer

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

S = set(A)
C = Counter(A)

if 1 in S:
    print(1)
    exit()

ans=0
for a in reversed(A):
    i=2
    while i*i<=a:
        if a%i==0:
            d1 = a//i
            d2 = i
            if d1 in S or d2 in S:
                break
        i+=1
    else:
        if C[a]==1:
            ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import math
from collections import Counter


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


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", 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


reduce_fs = set()
for c in cs:
    # print(c, sum([c%ap==0 for ap in aps]))
    if sum([c%ap==0 for ap in aps]) == 0:
        reduce_f = reduce_multiple(factorization(c))
        reduce_fs.add(reduce_f)

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

a_list = [a for a in a_list if a not in dup_list]

b_list = a_list

ans = []

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

print(len(a_list))

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()))
b = set()
if len(set(a)) != n:
    print(0)
    exit()
a.sort()
cnt = 0
flg = True

for i in a:
    flg = True
    l = make_divisors(i)
    for num in l:
        if num in b:
            flg = False
            break
    if flg == True:
        cnt += 1
    b.add(i)


print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())))
sa = set(a)
sl = len(sa)
ans = 0
for i in range(sl):
    count = 0
    for j in range(n):
        if i == j:
            pass
        elif count == 0:
            if a[i] % a[j] == 0:
                count = 1
        else:
            break
    else:
        if count == 0:
            ans += 1
print(ans)

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 c[l[0]]==1: sm+=1
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)

Submission status: Wrong Answer

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

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

count = 0
found = 0
for i in range(N):
    for j in range(N):
        if i != j:
            if A[i] % A[j] == 0:
                break
            else:
                found = found + 1
        else:
            continue
    if found == N-1:
        count = count + 1
    found = 0
        


print(count)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from math import gcd

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

n = int(input())
a = list(map(int, input().split()))
a.sort()
b = [set() for _ in range(n)]
for i, ai in enumerate(a):
    x = 1
    while x * x <= ai:
        if ai % x == 0:
            b[i].add(x)
            b[i].add(ai // x)
        x += 1

c = set()
if n > 1 and a[0] == a[1]:
    ans = -1
else:
    ans = 0
for ai, bi in zip(a, b):
    if len(bi & c) == 0:
        ans += 1
    c.add(ai)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
ans=0
A_sort = sorted(A)
print(A_sort)

for i in range(N):
  flag = "true"
  for j in range(N):
    if i <= j:
      break
    if A_sort[i] % A_sort[j] == 0:
      flag = "false"
      break
  if flag == "true":
    ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return sorted(divisors)

n = int(input())
A = sorted(tuple(map(int, input().split())))
if n ==1:
    print(1)
    exit()
if A[0] == 1:
    if A[1] == 1:
        print(0)
    else:
        print(1)
else:
    ans = []
    tyo = []
    for i in range(n):
        flag = True
        if tyo != []:
            if A[i] == tyo[-1]:
                continue
        tmp = make_divisors(A[i])
        for x in tmp:
            if bisect.bisect_left(ans, x)< len(ans):
                if x == ans[bisect.bisect_left(ans,x)]:
                    flag = False
                    break
        if not flag:
            continue


        if i<n-1:
            if A[i+1] == A[i]:
                tyo.append(A[i])
                continue
        ans.append(A[i])
    print(len(ans))

Submission status: Wrong Answer

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

array = list(set(array) - set([x for x in set(array) if array.count(x) > 1]))
array.sort()

i = 0;
while(i < len(array)):
    multi = [j * array[i] for j in range(2, int(array[-1] / array[i] + 1))]
    array = list(set(array) - set(multi))
    array.sort()
    i += 1
    
print(len(array))

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 (flag):
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
d = {}
n = A[-1]
def makePrimeChecker(n):
    isPrime = [True] * (n + 1)
    isPrime[0] = False
    isPrime[1] = False
    i = 0
    for j in A:
        if i == j:
            isPrime[i] = False
        i = j
        if i > 10**3:
            break
        if isPrime[i]:
            for j in range(i * 2, n + 1, i):
                isPrime[j] = False
    return isPrime
P = makePrimeChecker(n)
i = 0
ans = 0
for j in A:
    if i == j:
        continue
    else:
        i = j
        if P[i]:
            ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
N = int(input())
A = input().split()

if N == 1:
  print(1)
else:
	for i in range(N):
		A[i] = int(A[i])
	A.sort()
	K = collections.Counter(A)
	num = list(K.keys())

	ans = len(num)
	lim = len(num)
	if len(num) == 1:
		print(0)
	else :
		for i in range(len(num)):
			if num[i] != 0:
				for j in range(i+1,len(num)):
					if num[j] != 0:
						if (num[j] % num[i]) == 0:
							ans -= 1
							num[j] = 0
                
		print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

a.sort()
q = deque(a)
nq = deque()
ans = []
i = 0

while len(q) != 0:
    a_ = q.popleft()
    lenq = len(q)

    for _ in range(lenq):
        q_ = q.popleft()
        if q_ % a_ != 0:
            nq.append(q_)
    q = nq.copy()
    nq = deque()
    if not (i == 0 and len(q) == 0):
        ans.append(a_)
    i += 1

# print(ans)
print(len(ans))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
a = list(map(int, input().split()))
a.sort()
aa = np.array(a)
check = [0] * n

for j, i in enumerate(a):
    if (check[j] == 1):
        continue
    tar = aa[aa % i == 0]
    #tar = np.where(aa % i == 0)
    if (len(tar) == 1):
        continue

    tar = np.where(aa % i == 0)
    # print(tar)
    # print(len(tar))
    tar = tar[0]
    for k, val in enumerate(tar):
        if (k == 0):
            continue

        check[val] = 1

ans = n - sum(check)
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
ans=0
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return set(divisors)
for i in a:
    s=set(a)
    s.discard(i)
    if len(make_divisors(i)&s)==0:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter

input = sys.stdin.readline


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

    if N == 1:
        ans = 0
    else:
        A.sort()
        c = Counter(A)
        keys = list(c.keys())
        ans = 0
        for i, (k, v) in enumerate(c.items()):
            if v > 2:
                continue
            is_ok = True
            for key in keys[:i]:
                if k % key == 0:
                    is_ok = False
                    break
                if k // 2 < key:
                    break
            ans += v * is_ok

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))

n = I()
l = LI()
list.sort(l, reverse=True)
c = 0
for a in l:
  for b in l:
    if a == b:
      continue
    if a % b == 0:
      break
  else:
    c += 1
  
print(c)

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,100):
            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:
N=int(input())
A=tuple(map(int,input().split()))

A_sorted=list(sorted(A))

result=[]
while A_sorted!=[]:
    a=A_sorted.pop(0)
    if a in A_sorted:
        A_sorted=list(filter(lambda x: x!=a,A_sorted))
        continue
    result.append(a)
    A_sorted=list(filter(lambda x: x%a!=0,A_sorted))
print(len(result))

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
A = sorted([int(x) for x in input().split()])
cA = Counter(A)

cand = []
ans = 0
for a, val in cA.items():
    if a == 1:
        print(N)
        exit()
    elif len(cand) != 0:
        for t in cand:
            if a % t == 0:
                break
        else:
            #print(a)
            cand.append(a)
            ans += val
    else:
        if val != N:
            #print(a)
            cand.append(a)
            ans += val
        else:
            print(0)
            exit()
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce


def input(): return sys.stdin.readline().strip()


def INT(): return int(input())


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


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


def ZIP(n): return zip(*(MAP() for _ in range(n)))


sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    N = INT()
    A = LIST()
    
    A.sort()
    i = 1
    dic = defaultdict(int)

    for x in A:
        dic[x] += 1


    div = [A[0]]
    for i in range(1, N):
        for j in div:
            if A[i]%j == 0:
                break
        else:
            div.append(A[i])
    
    p = sum([1 for x in dic.keys() if x>1])
    # print(p)
    # print(div)
    print(len(div)-p)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import collections
n=int(input())
l=list(map(int, input().split()))
l.sort()
d=collections.Counter(l)
cnt=0
if d[l[0]]==1:
    cnt=1
pro=l[0]
if l[0]%2==0:
    pro=2
for i in range(1,len(l)):
    if l[i]%2==0 and pro%2!=0 and d[l[i]]==1:
        pro=pro*2
        cnt=cnt+1
    elif l[i]%2==1 and d[l[i]]==1 and l[i]%pro!=0:
        cnt=cnt+1
        pro=pro*l[i]
print(cnt)

Submission status: Wrong Answer

Solution code:
def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True
n=int(input())
A=list(map(int,input().split(" ")))
g=0
for i in range(n):
  if is_prime(A[i]):
    if A.count(A[i])>=2:
      g=g+1
  else:
    for j in range(n):
      if i!=j:
        if A[i]%A[j]==0:
          g=g+1
          break
print(n-g)

Submission status: Wrong Answer

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

for i in range(n):
  for k in range(i+1):
    a2.append(a[k])
  if i+2<=len(a):
    if a[i+1]==a[i]:
      a2.pop(-1)
  for j in range(i+1,len(a)):
    if a[j]%a[i]!=0:
      a2.append(a[j])
  a=a2
  a2=[]
  print(a)
  if len(a)<=i+1:
    break
       
print(len(a))
print(a)

Submission status: Wrong Answer

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

L = 0
for n,i in enumerate(a):
    H = 0
    if 2 in a and i!=2 and i%2 == 0:
        H=1
    elif 3 in a and i!=3 and i%3 == 0:
        H=1
    elif 5 in a and i!=5 and i%5 == 0:
        H=1
    else:
        for j in a[n+1:]:
            if i % j == 0:
                H = 1
                break
    if H == 0:
        L+=1
print(L)

Submission status: Wrong Answer

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

count = 0

for i in range(1, N):
    if A[0] != A[i]:
        break
    if (i == N - 1) and A[0] == A[i]:
        print(0)
        exit()

for i in range(N):
    if i == 0:
        count += 1
    else:
        for j in range(i):
            if A[i] % A[j] == 0:
                break
            if (j == i - 1) and (A[i] % A[j] != 0):
                count += 1

print(count)

Submission status: Wrong Answer

Solution code:
import itertools

N = int(input())

ans = set([int(x) for x in input().split()])

hoge = set()
cnt = 0

if len(ans) == 1:
    print(0)
else:
    for a,b in itertools.combinations(ans,2):
        if b % a == 0:
            hoge.add(b)
    print(len(ans-hoge))