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:
# Contest No.: ABC170
# Problem No.: D
# Solver:      JEMINI
# Date:        20200614


##### FAST INPUT #####
import os
import sys
from io import BytesIO, IOBase

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
##### END OF FAST INPUT #####
#import sys
import heapq

def main():
    n = int(input())
    nums = list(map(int, input().split()))
    if n == 1:
        print(1)
        return
    nums.sort()
    #nums = list(reversed(nums))
    checkList = [True] * n
    i = 0
    while i < n - 1:
        if not checkList[i]:
            i += 1
            continue
        j = i + 1
        if nums[j] == nums[i]:
            checkList[i] = False
            while j < n and nums[j] == nums[i]:
                checkList[j] = False
                j += 1
            if j == n:
                break
            else:
                i = j
                continue
        pFront = j
        pRear = n - 1

        while True:
            pMid = (pFront + pRear) // 2
            if nums[pFront] * 2 >= nums[i]:
                j = pFront
                break
            if nums[pRear] * 2 < nums[i]:
                j = pRear
                break
            if nums[pMid] * 2 >= nums[i]:
                pRear = pMid - 1
            else:
                pFront = pMid + 1

        while j < n:
            if nums[j] % nums[i] == 0:
                checkList[j] = False
            j += 1
        i += 1
        #print(nums)
        #print(checkList)
    print(sum(checkList))


    
    return

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
def solution():
    
    n = int(input())
    inputList = list(map(int, input().split()))
    numpyArray = np.array(inputList)
    resultCount = 0
    for i in range(n):
        newArray = numpyArray[numpyArray != inputList[i]]
        test = lambda x: inputList[i] % x
        newArray = test(newArray)
        if newArray.size>0 and 0 not in newArray:
            resultCount += 1

    print(resultCount)

solution()

Submission status: Wrong Answer

Solution code:


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

b.sort(reverse=True)
ans = 0
d = {}
a = [0] * n
cnt = 0
for i in range(n):
    if b[i] in d:
        d[b[i]] += 1
        continue
    else:
        d[b[i]] = 1
        a[cnt] = b[i]
        cnt += 1 

n = cnt
if a[n - 1] == 1:
    print("1")
else:
    for i in range(n - 1):
        for j in range(n):
            if a[i] % a[n - j - 1] == 0 and i != n - j - 1 and d[a[i]] < 2:
                break
            if n-j-1 ==  i:
                ans += 1
    if d[a[0]] < 2:
        ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
import math


def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 1:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

import collections





n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
c = collections.Counter(a)
data = []
for e in c.most_common():
  if e[1] == 1:
    data.append(e[0])
count = 0
#data = a.copy()
prime = []
limit = math.sqrt(10**6)
while len(data) > 0:
  p = data[0]
  if len(data) > 1 and p == data[1]:
    count += 1
  if limit <= p:
    prime += data
    break
  prime.append(p)
  data = [e for e in data if e % p != 0]
  #print(data)

print(len(prime)-count)

Submission status: Wrong Answer

Solution code:
import math

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np


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

'''
N = 2*10**4
A = np.random.randint(1,10**6,N)
'''

A = np.sort(np.array(A))
middle_N = np.where(A>A[N-1]//2)[0][0]
middle_num = A[middle_N]
ok_list = np.array([])
ans = 0

for i in range(N):
    a = A[i]
    check_list = ok_list[ np.where(ok_list<middle_num) ]
    if set(  a%check_list==0 ) == {False} or i==0:
        if i>=N-1 or A[i+1]!=a:
            ok_list = np.append(ok_list, a)


print(len(ok_list))

Submission status: Wrong Answer

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


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


dictA = {}

count = 0
for x in a:
    check = a.copy()
    check.remove(x)
    yaku = make_divisors(x)
    count_flag = True
    for y in yaku:
        if y != 1 and y in check:
            count_flag = False
            break
    if count_flag:
        count += 1
print(count)

Submission status: Wrong Answer

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

i=0
num=0

while i<n:

    j=0
    jud=1
    while j<n:
        if i!=j:
            if a[i]>a[j]:

                if a[i]%a[j]==0:
                    jud=0
                    break

        j+=1

    if jud==1:
        num+=1

    i+=1

print(num)

Submission status: Wrong Answer

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

    print(count)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

li= []
li.append(a[0])
for i in range(1,len(a)):
    if all(a[i]%j != 0 for j in li) or li == []:
        li.append(a[i])
    elif not all(a[i] != j for j in li):
        li.remove(a[i])


print(len(li))

Submission status: Wrong Answer

Solution code:
from sys import stdin
N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]
A = set(A)
A = list(A)
A = sorted(A)
N = len(A)

ans=0

if N != 1:
  ans += 1

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

Submission status: Wrong Answer

Solution code:
N = int(input())
num_list = list(map(int, input().split()))
count=0


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

print(N-count)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

b = [str(i) for i in a]
#素因数分解
def fact(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
                arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

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

def fact2(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

a = sorted(a)
ans = 1
alr = fact2(a[0]) #すでにある素因数
for i in range(1,n):
    now_fact = fact(a[i])
    app_fact = fact2(a[i])
    j = 0
    while j <= len(now_fact):
        if j == len(now_fact):
            ans += 1
            for k in now_fact:
                alr.append(k)
            break
        elif now_fact[j] in alr:
            break
        else:
            j += 1
c = Counter(b)
c = c.most_common()
for i in range(len(c)):
    if c[i][1] > 1:
        ans -= 1
print(ans)

Submission status: Wrong Answer

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

import numpy as np
from collections import Counter


N = int(input())
A = np.array(readline().split(), dtype=np.int64)
count = Counter(A)
A = np.array([
    a for a, c in count.items() if c == 1
])
if len(A) != 0:
    A = np.sort(A)
i = 0
while True:
    if len(A) == 0:
        break
    pre = A
    a = A[i]
    A = np.delete(A, np.where((A % a == 0) & (A != a)))
    i += 1
    if len(pre) == len(A) or i >= len(A):
        break

print(len(A))

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int,input().split()))
A.sort(reverse=True)
count = 0
ddd = 0

for i in range(n):
  for j in range(1,n+1):
    if i==n-j:
      continue
    if A[i]%A[n-j] == 0:
      ddd = 1
      break
    if A[i]//2 < A[n-j]:
      break
  if ddd == 0:
    count+=1
  ddd = 0

print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort(reverse=True)
 
if n == 1:
    print(0)
    exit()

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

if n > 1:
    if a[-2] != a[-1]:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
B = sorted(list(set(A)))

if len(B)>=2:
    NotD = 0
    for T in range(1,len(B)):
        Target = B[T]
        Count = 0
        for TT in range(0,T):
            BY = B[TT]
            if Target%BY==0:
                break
            else:
                Count += 1
        if Count==T and A.count(B[T])==1:
            NotD += 1
    print(NotD+1)
elif len(B)==1 and len(A)==1:
    print(1)
else:
    print(0)

Submission status: Wrong Answer

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

count = 0

for i in asetlist:
  if alist.count(i) >= 2:
    count += 1

i = 0

while i < len(asetlist):
  a = asetlist[i]
  j = i + 1

  while j < len(asetlist):
    if asetlist[j] % a == 0:
      del asetlist[j]
    else:
      j += 1

  i += 1

print(len(asetlist) - count)

Submission status: Wrong Answer

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

B = [1 for _ in range(n)]

for i in range(n):
  if A[i]*2 > A[n-1] and A[i] <= A[n-1]:
    if i < n-1 and A[i] == A[i+1]:
      B[i] = 0
      B[i+1] = 0
      for j in range(n)[i+2:]:
        if A[j] == A[i]:
          B[j] = 0
        else:
          break
    else:
      break
  else:
      break
      
  c = 0
  if B[i] == 0:
    continue
  if i < n-1 and A[i] == A[i+1]:
    B[i] = 0
    B[i+1] = 0
    for j in range(n)[i+2:]:
      if A[j] == A[i]:
        B[j] = 0
      else:
        break
  while(A[i]*c <= A[n-1]):
    c += 1
    for j in range(n)[i+1:]:
      if A[j] == A[i]*c:
        B[j] = 0
print(sum(B))

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
A = list(map(int,input().split()))
A.sort()
L = [1]*n
for i in range(n-1):
  if L[i] == 1:
    for j in range(i+1,n):
      if A[j] == A[i]:
        L[i] == 0
      if A[j] % A[i] == 0:
        L[j] = 0
print(sum(L))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import Counter
# from heapq import heappop, heappush
# from bisect import bisect_right
# from math import gcd

def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = set()
    for i,l in Counter(A).items():
        if l == 1:
            B.add(i)
    A = sorted(B)
    N = len(A)
    # L = [1] * (N+1)
    # for i in range(N):
    #     L[i+1] = (L[i]*A[i])//gcd(L[i],A[i])
    ans = 0
    # print(A)
    # print(L)
    A.sort()
    for i in range(N):
        flag = True
        for j in range(i):
            if A[i] % A[j] == 0:
                flag = False
                break
        if flag:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
As = list(map(int, input().split()))
 
ttable = [[False for i in range(N)] for j in range(N)]
 
for i in range(N):
  for j in range(i+1, N):
    if As[i] == As[j]:
      ttable[i][j] = True
      ttable[j][i] = True
    elif As[i] % As[j] == 0:
      ttable[i][j] = True
    elif As[j] % As[i] == 0:
      ttable[j][i] = True

print(ttable)
cnt = 0
for i in range(N):
  if True not in ttable[i]:
    cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
B = set(A)
for i in A:
    if A.count(i) > 1: B = B - {i}
multiplier = 2
for i in B:
    while i*multiplier <= max(B):
        B = B - {i*multiplier}
        multiplier += 1
print(len(B))

Submission status: Wrong Answer

Solution code:
import itertools
import decimal
import math
import collections
import sys
input = sys.stdin.readline

N=int(input())

ListA=list(map(int,input().split()))
ListA.sort()#reverse=True)

ans=N
rootN=int(math.sqrt(N))
for i in range(N):
    if(i < N-1):
        if(ListA[i]==ListA[i+1]):
            ans-=1
            continue

    if(i>=1):
        if(ListA[i]==ListA[i-1]):
            ans-=1
            continue
        
    #rootA=math.sqrt(ListA[i])

    if(ListA[i]%2==0):
        Maxval=ListA[i]/2
    if(ListA[i]%3==0):
        Maxval=ListA[i]/3
    if(ListA[i]%5==0):
        Maxval=ListA[i]/5
    if(ListA[i]%7==0):
        Maxval=ListA[i]/7


    for j in range(i):
        if(ListA[i]%ListA[j]==0):
            ans-=1
            break
        if(ListA[j]>Maxval):
            break

    
# if(N>=2):
#     if(ListA[2]%ListA[1]==0):
#         ans-=1

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())), reverse=True)
ans=0
#小さい方から割る
mem=set([])
for i in range(n):
    for j in range(n):
        if i==n-j-1:
            continue
        if (a[i],a[n-j-1]) in mem:
            ans+=1
            break
        if a[i]%a[n-j-1]==0:
            ans+=1
            mem.add((a[i],a[n-j-1]))
            break
        if a[i]<a[n-j-1]*2:
            break
print(n-ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().strip().split()))
a.sort()
MAX = max(a)
f = [0] * (MAX + 2)
g = [0] * (MAX + 2)

ans = [0] * (MAX + 2)
for i in range(n):
    g[a[i]] += 1
    x = a[i]
    inc = a[i]
    if f[x] == 0:
        ans[a[i]] += 1

    while x <= MAX:            
        if f[x] >= 1:
            break
        else:
            f[x] += 1
            x += inc


#print(g)
ans_count = 0
for i in range(n):
    if g[a[i]] == 1 and ans[a[i]] == 1:
        ans_count += 1


print(ans_count)

Submission status: Wrong Answer

Solution code:
N= int(input())
As = list(map(int,input().split()))
As= [a for a in As if As.count(a)==1]
As.sort()
import sys
if len(As)==0:
    print(0)
    sys.exit()
count=0
for i in range(len(As)):
    flg=True
    for j in range(i):
        if As[i]%As[j]==0:
            flg=False
            break
        if As[j]>As[i]**0.5:
            break
    if flg:
        count +=1
print(count)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort()
B=[]
for i in range(N-1):
    if A[i]==A[i+1]:
        B.append(A[i])
B=list(set(B))
A=list(set(A))
for i in B:
    A.remove(i)
L=len(A)
for i in range(L):
    if i<len(A):
        j=i+1
        while j<=len(A)-1:
            if A[j]%A[i]==0:
                A.remove(A[j])
            else:
                j+=1
print(len(A))

Submission status: Wrong Answer

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

bunpu = [0 for i in range(10 ** 6 + 1)]
for _a in a:
  bunpu[_a] += 1

ans = 0
for _a in a:
  cnt = 0
  i = 1
  while i * i <= n:
    if _a % i == 0:
      cnt += bunpu[i]
      if i * i != _a:
        cnt += bunpu[_a // i]
      if cnt > 1:
        break
    i += 2 if i >= 3 else 1
  if cnt == 1:
    ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
B=list(set(A))
if len(B)==1 and len(A)!=1:
  print('0')
  exit()
for i in range(N):
  key=A[i]
  B=[x for x in B if x%key!=0 or x==key]
  B=list(B)
print(len(B))

Submission status: Wrong Answer

Solution code:
import collections
import numpy as np

N = int(input())
A = sorted([int(i) for i in input().split()])
a = collections.Counter(A)
A = np.array([i[0] for i in a.items() if i[1] == 1])

ans = 0
while len(A) > 0:
    if len(A) == 1:
        ans += 1
    elif A[0] != A[1]:
        ans += 1
    n = A[0]
    A = A[np.where(A % n != 0)[0]]
    
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
import collections

def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
def TI(): return tuple(map(int,input().split()))
def RN(N): return [input().strip() for i in range(N)]


def main():
    
    N = II()
    A = LI()
    As = sorted(A, reverse=True)
    ans = N
    c = collections.Counter(As)

    if len(set(A)) == 1:
        print(0)
    elif c[1] != 0:
        if c[1] == 1:
            print(1)
        else:
            print(0)
    else:
        for i in range(N-1):
            k = N-1
            if c[As[i]] >= 2:
                ans -= 1
                if i == N-2:
                    ans -= 1
            else:
                for j in range(N):
                    if k == i:
                        break
                    elif As[i] % As[k] == 0:
                        ans -= 1
                        break

                    k -= 1

        print(ans)


if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
n=int(input())
li = list(map(int,input().split()))
count=0

for i in range(n):
  for j in range(n):
    if i == j : pass
    elif li[i]%li[j] == 0:break
    elif j == n-1:count = count + 1
        
print(count)

Submission status: Wrong Answer

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

count=0
for i in l:
  for num in range(n):
    if i%l[num]==0:
      if i!=l[num]:
        print(i,l[num])
        count+=1
        break
      
print(n-count)

Submission status: Wrong Answer

Solution code:
N=int(input())
list = list(map(int, input().split()))
rlist = list
rlist.sort()
ans=0

for i in range (0,N):
  res=0
  for j in range(0,N):
    if(list[i] % rlist[j]==0):
      res+=1
      if(2<res):
        break
  if(0<res):
    ans+=1

print(N-ans)

Submission status: Wrong Answer

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

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


ary.sort(reverse=True)

del_list_index = []

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


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

print(len(ary))

Submission status: Wrong Answer

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

d = defaultdict(int)
for i in a:
  d[i] += 1

a.sort()
mx = max(a)

chk = [False for i in range(mx+1)]
cnt = 0
for i in range(n):
  if d[a[i]] >= 2:
    continue
  if chk[a[i]] == False:
    cnt += 1
  for j in range(a[i],mx+1,a[i]):
    chk[j] = True
print (cnt)

Submission status: Wrong Answer

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

    ans = 0
    s = set()
    for i in range(N):
        if i == 0:
            s.add(A[i])
            if A[0] != A[1]:
                ans += 1
        else:
            if any(A[i] % j == 0 for j in s):
                pass
            else:
                s.add(A[i])
                ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N=int(input())
A=list(map(int,input().split()))
A=sorted(A)[::-1]
if Counter(A)[A[-1]]>1:
    ans2=0
else:
    ans2=1
for i in range(N-1):
    ans=0
    for j in range(i,N):
        if A[i]%A[j]!=0:
            ans+=1
    if ans==N-i-1:
        ans2+=1
print(ans2)

Submission status: Wrong Answer

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

K = 10**6+1
num = [0] * K
l = [False] * K
for i in range(N):
    num[A[i]]+=1
    l[A[i]] = True

for i in range(2, K):
    if num[i]>0:
        if num[i]>1:
            l[i] = False
        j = 2
        while i*j < K:
            l[i*j] = False
            j += 1

ans = 0
for i in range(N):
    if l[A[i]]:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
A = list(map(int,input().split()))
A.sort()
ans = 0
for i in range(n-1):
    if math.gcd(A[i+1],A[i]) == 1:
        ans += 1
print(ans)

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 = sorted(list(map(int,input().split())))

if n==1:
    print(1)
    exit()

if a[0] in a[1:]:
    ans = 0
else:
    ans = 1

div = set([a[0]])
for i in a[1:]:
    x = set(make_divisors(i))
    if not x&div:
        ans += 1
    div.add(i)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = sorted(A)[::-1]
T = N
for i in range(N):
    for k in range(N-i-1):
        if B.count(B[i]) != 1:
            T -= 1
            break
        elif B[i] % B[-k -1] == 0:
            T -= 1
            break
        else:
            continue
print(T)

Submission status: Wrong Answer

Solution code:
import math

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


def isPrime(n):
    if n < 2:
        # 2未満は素数でない
        return False
    if n == 2:
        # 2は素数
        return True
    for p in range(2, n):
        if n % p == 0:
            # nまでの数で割り切れたら素数ではない
            return False
    # nまでの数で割り切れなかったら素数
    return True


def tagainiso(a, b):
    for i in range(2, int(max(a, b))):
        if a % i == 0 and b % i == 0:
            return False
    return True


for i in range(n):
    if a.count(a[i]) >= 2:
        continue
    if isPrime(a[i]):
        ans += 1
        # print(a[i])
        continue

    flg = True
    for j in range(n):
        if i != j and a[i] % a[j] != 0:
            continue
        elif i != j and a[i] % a[j] == 0:
            flg = False
            break
    if flg:
        ans += 1

print(ans)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

A.sort()
if A[0] == A[-1]:
    print(0)
    sys.exit(0)
if A[0] == 1:
    print(1)
    sys.exit(0)
if len(A) == 1:
    print(1)
    sys.exit(0)

d =[]

for i in range(len(A)):
    flag = True
    for j in d:
        if A[i] % j == 0:
            flag = False
            break
    if flag:
        d.append(A[i])

print(len(d))

Submission status: Wrong Answer

Solution code:
def resolve():
    n = int(input())
    A = list(map(int, input().split()))
    if len(set(A)) == 1:
        print(0)
        return

    ans = 0
    while len(A) > 0:
        a = A.pop()
        ans += 1
        A = list(map(lambda x: x % 2, A))
        if A.count(0) > 0:
            A = [i for i in A if i != 0]
    print(ans)

resolve()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
import collections
n = int(input())
a_list = list(map(int, input().split()))
a_dict = dict(collections.Counter(a_list))
sorted_dict = sorted(a_dict.items(), key=lambda x:x[0])
flag_list = [1] * len(sorted_dict)

i = 0
for key, count in sorted_dict:
    if flag_list[i] == 0:
        continue
    if count > 1:
        flag_list[i] = 0
    i += 1
    j = i
    for key1, count1 in sorted_dict[i:]:
        if flag_list[j] == 0:
            j += 1
            continue
        if count1 > 1:
            flag_list[j] = 0
            j += 1
            continue
        if key1 % key == 0:
            flag_list[j] = 0
        j += 1

print(sum(flag_list))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

b=[]
for i in range(n):
  if df[i] == 0:
    b.append(a[i])

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict

def get_prime_factors(n):
    dd = defaultdict(lambda: 0)
    if n > 1:
        i = 2
        while i * i <= n:
            if n % i == 0:
                dd[i] += 1
                n /= i
                i = 2
            else:
                i += 1
        dd[n] += 1
    return dd


def solve(N: int, A: "List[int]"):
    
    A = sorted(list(set(A)))
    A = [a for a in A if a != 1]
    if len(A) <= 1:
        print(0)
        return
    
    count = 0

    dd = defaultdict(lambda: (0, 10**6+1))
    
    for a in A:
        d = get_prime_factors(a)

        flag = True
        for prime, value in d.items():
            dd_val, dd_mn = dd[prime]
            
            if a % dd_mn==0:
                flag = False
                break

            dd[prime] = (dd_val + value, min(dd_mn, a))

        if flag:
            count+= 1

    print(count)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import copy

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

a1 = input().split()
a = []

for i in a1:
    a.append(int(i))

count = 0
t = []

for i in range(n):
    t = copy.copy(a)
    del t[i]
    if len(set(make_divisors(a[i])) & set(t)) == 0:
        count += 1


if n == 1:
    print(0)
else:
    print(count)