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:
# template by 3xC and starkizard.
# contributors: 

#####################################################################################
from __future__ import division, print_function 

import sys
import os
from collections import Counter, deque, defaultdict
import itertools
import math
import io


"""Uncomment modules according to your need"""


# from bisect import bisect_left, bisect_right, insort
# from heapq import heappop, heapify, heappush
# from random import randint as rn
# from Queue import Queue as Q
# from copy import deepcopy
# from decimal import *
# import re
# import operator

#####################################################################################
# this enables you to write python3 code with PyPy2 (Python 2)
if sys.version_info[0] < 3:
    input = raw_input
    range = xrange

    filter = itertools.ifilter
    map = itertools.imap
    zip = itertools.izip

#####################################################################################

"""value of mod"""
MOD = 998244353
mod = 10**9 + 7

"""Uncomment next 4 lines if doing huge recursion"""
# import threading
# threading.stack_size(1<<27)
# sys.setrecursionlimit(10000

def prepare_factorial(mod=mod):
    """ returns two lists, factorial and inverse factorial modulo argument by default 10**9 +7 """
    # Comment code out when you don't need inverse factorial or vice versa
    fact = [1]
    for i in range(1, 200005):
        fact.append((fact[-1] * i) % mod)

    ifact = [0] * 200005
    ifact[200004] = pow(fact[200004], mod - 2, mod)
    for i in range(200004, 0, -1):
        ifact[i - 1] = (i * ifact[i]) % mod

    return fact, ifact

def modinv(n, p):
    """ returns N inverse modulo p """
    return pow(n, p - 2, p)

def ncr(n, r,  fact, ifact):
    """ takes 4 arguments: n , r and factorial and inverse factorial lists"""
    t = (fact[n] * (ifact[r]*ifact[n-r]) % MOD)% MOD
    return t


def get_n(Sum):    
    """this function returns the maximum n for which Summation(n) <= Sum"""
    ans = (-1 + sqrt(1 + 8*Sum))//2
    return ans

def sieve(n):
    """ returns a list of prime numbers till n """
    if n < 2: return list()
    prime = [True for _ in range(n + 1)]
    p = 3
    while p * p <= n:
        if prime[p]:
            for i in range(p * 2, n + 1, p):
                prime[i] = False
        p += 2
    r = [2]
    for p in range(3, n + 1, 2):
        if prime[p]:
            r.append(p)
    return r



def divs(n, start=1):
    """ returns a list of all divisors till n """
    divisors = []
    for i in range(start, int(math.sqrt(n) + 1)):
        if n % i == 0:
            if n / i == i:
                divisors.append(i)
            else:
                divisors.extend([i, n // i])
    return divisors



def divn(n, primes):
    """ returns the number of divisors, two arguments n and the sieve till n """
    divs_number = 1
    for i in primes:
        if n == 1:
            return divs_number
        t = 1
        while n % i == 0:
            t += 1
            n //= i
        divs_number *= t



def lrfind(d, x, default=-1):
    """ Takes 2 arguments an iterable and an element. returns a tuple (firstoccurence,lastoccurence) -1 if not found """
    left = right = -1
    for i in range(len(d)):
        if d[i] == x:
            if left == -1: left = i
            right = i
    if left == -1:
        return default, default
    else:
        return left, right

def gcd(x, y): # math.gcd is slower
    """ returns greatest common divisor of x and y """
    while y:
        x, y = y, x % y
    return x

def check_sorted(a):
    ''' returns True/False '''
    for i in range(len(a)-1):
        if a[i]>a[i+1]:
            return False
    return True
def ceil(n, k=1): return n // k + (n % k != 0) #returns math.ceil but protecting against floating inconsistencies
def input(): return sys.stdin.readline().strip()
def ii(): return int(input()) #inputs integer
def mi(): return map(int, input().split()) # inputting space seperated variables for example x,y,z
def li(): return list(map(int, input().split())) #inputting a space seperated list of integers
def lw(): return input().split() #inputting a space seperated list of strings
def lcm(a, b): return abs(a * b) // gcd(a, b) #returns LCM of two arguments
def prr(a, sep=' ', end='\n'): print(sep.join(map(str, a)), end=end) #For printing an iterable with seperator sep as optional second argument (default : " "), ending character (default: "\n") as optional third
def dd(): return defaultdict(int) #returns a dictionary with values defaulted to 0
def ddl(): return defaultdict(list) #returns a dictionary with values defaulted to []
def write(s): return sys.stdout.write(s)












###################################################################
def main():
    #CODE GOES HERE:
    n=ii()
    a=li()
    a.sort()
    count=0
    s=[]
    setter=set()
    for i in range(n):
        try:
            if a[i]==a[i+1]:
                if a[i] not in setter:
                    s.append(a[i])
                    setter.add(a[i])
                continue
        except:
            check=True
            for el in s:
                if a[i]%el==0:
                    check=False
                    break
            if(check):
                count+=1
        if(i==0):
            s.append(a[i])
            continue
        checker=True
        for el in s:
            if a[i]%el==0:
                checker=False
                break
        if(checker):
            count+=1
            setter.add(a[i])
            s.append(a[i])
        
    print(count)



































""" -------- Python 2 and 3 footer by Pajenegod and c1729 ---------"""

py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange

import os, sys
from io import IOBase, BytesIO

BUFSIZE = 8192

class FastIO(BytesIO):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
        return s

    def read(self):
        while self._fill(): pass
        return super(FastIO, self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill();
            self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

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


class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            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')
# sys.stdin = open('input.txt', 'r')
# sys.stdout = open('output.txt', 'w')

""" main function"""

if __name__ == '__main__':
    main()
    # threading.Thread(target=main).start()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n = int(input())
a = sorted([int(i) for i in input().split()])
if len(set(a)) == 1:
    print(0)
else:
    if a.count(1) == 1:
        print(1)
    elif a.count(1) > 1:
        print(0)
    else:
        dict_a = dict()
        for ai in a:
            flag = True
            for da in dict_a.keys():
                if ai % da == 0:
                    flag = False
            if flag:
                dict_a[ai] = 1
        print(len(dict_a))

Submission status: Wrong Answer

Solution code:
import math

n=int(input())
A=list(map(int,input().split()))
A.sort()
m=10**6+10
C=[0]*m
C[0]=-1
ans=0
now=0
flag=0
for a in A:
    if now==a:
        flag=1
        continue
    if now!=a and flag:
        ans-=1
        flag=0
    now=a
    if C[a]==0:
        ans+=1
        j=a
        while j<m:
            C[j]=1
            j+=a
if flag:
    ans-=1
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
from collections import deque
A.sort()
B = deque(A)
ans = []
while len(B)>0:
    p = B.popleft()
    B = deque([j for j in B if j % p !=0])
    ans.append(p)
print(len(ans))

Submission status: Wrong Answer

Solution code:
import sys

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

def main():

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

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

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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from itertools import permutations, product, combinations
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)))
    if len(A) == 1:
        print(0)
        return
    
    count = 0

    dd = defaultdict(lambda: [0, -1])
    for a in A:
        d = get_prime_factors(a)

        flag = True
        for prime, value in d.items():
            dd_prime, dd_mn = dd[prime]
            
            if dd_mn == -1:
                dd_mn = a

            if dd_prime != 0 and a % dd_mn==0:
                flag = False

            dd[prime][0] += value
            dd[prime][1] = min(dd_mn, a)
        if flag:
            count+= 1

    # print(count)
    # for a in A:
    #     d = get_prime_factors(a)

    #     flag = True

    #     for prime, value in d.items():
    #         if dd[prime] != value and value !=1:
    #             flag = False
    #             break

    #     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:
n = int(input())
a = list(set(map(int, input().split())))
a.sort()
num_ans = 0

if(len(a) == 1):
    num_ans = 0
else:
    for i in range(len(a)):
        flag = True
        for j in range(i):
            if a[i] % a[j] == 0:
                flag = False
                break
        if flag:
            num_ans += 1

print(num_ans)

Submission status: Wrong Answer

Solution code:

def resolve():
    N = int(input())
    A = list(map(int,input().split()))
    B= set(A)

    A.sort(reverse= True)

    count = 0
    for idx,i in enumerate(A):
        if i == A[idx -1]:
            continue
        if idx != N-1 and i == A[idx +1]:
            B.discard(i)

        deleted =set()
        for j in B:
            if i == j:
                count+=1
            if j % i ==0:
                deleted.add(j)
        B.difference_update(deleted)





    print(count)

resolve()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = set(i for i in range(n))
ans = [0]*n
warizai_index = set()

for i in range(n):
    for wari in warizai_index:
        if a[i]%a[wari] == 0 and i != wari:
            ans[i] = 1
            if i in warizai_index:
                warizai_index.remove(i)
            if i in b:
                b.remove(i)
            break
    if ans[i] == 1:
        continue
    
    for j in b:
        if i == j:
            continue
        if a[i]%a[j] == 0:
            ans[i] = 1
            if i in warizai_index and a[i] != a[j]:
                warizai_index.remove(i)
            if i in b:
                b.remove(i)
            warizai_index.add(j)
            break

print(ans.count(0))

Submission status: Wrong Answer

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

oks = np.ones(len(aa))
for i in range(len(aa)):
    if i < len(aa)-1:
        if aa[i+1] == aa[i]:
            oks[i] = 0
    if oks[i] == 0:
        continue
    for j in range(i+1,len(aa)):
        if (aa[j]%aa[i] == 0):
            oks[j] = 0
print(int(oks.sum()))

Submission status: Wrong Answer

Solution code:
import sys
import copy

data = sys.stdin
data_list = data.readlines()
data_1 = data_list[0].strip("\n").split(" ")
data_2 = data_list[1].strip("\n").split(" ")

ans = 0
flag = 0

for i in range(int(data_1[0])):
  moto = int(data_2[i])
  new_list = data_2.copy()
  del new_list[i]
  for x in new_list:
    if moto % int(x) == 0:
      flag = 1
      break
  if flag == 0:
    ans += 1
print(ans)

Submission status: Wrong Answer

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

A.sort(reverse=True)

for i in range(len(A)-1):
    flg = True
    for j in range(i+1, len(A)):
        if A[i] % A[j] == 0:
            flg = False
            break
    if flg == True:
        print(i)
        ans += 1

print(ans)

Submission status: Wrong Answer

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

ans = 0
a_sort = sorted(a)
div = []
dup = 0

for i in set(a_sort):
	if a_sort.count(i) > 1:
		dup +=1

for i, n in enumerate(a_sort):
	for x in div:
		if n == x:
			break
		if n%x == 0:
			break
	else:
		ans += 1
		div.append(n)

print(ans-dup)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int,input().split()))
i = 0
ans = 0
ans_2 = 1
for j in range(n-1):
    if A[n-1] % A[j] == 0:
        ans_2 = 0
        break   
while True:
    for j in range(i+1,n):
        if A[i] % A[j] == 0:
            break
        elif j == n - 1:
            ans = ans + 1
    if i == n-1:
        print(ans+ans_2)
        break
    i = i + 1

Submission status: Wrong Answer

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

N = int(input().strip())
A_list = list(map(int, input().rstrip().split()))
#-----

A_list = list(set(A_list))

if len(A_list) == 1:
    print(0)
    sys.exit()

A_list.sort()
check = [1]*len(A_list)

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

print(check.count(1))

Submission status: Wrong Answer

Solution code:
import math

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

if len(set(A)) == 1:
    print(0)
else:
    ju = [True for _ in range(N)]

    for i in range(N-1):
        n = i+1
        if not ju[n] or not ju[i]:
            continue
        if A[i] > math.sqrt(A[-1]):
                break
        while n < N:
            if ju[n]:
                if A[n]%A[i] == 0:
                    ju[n] = 0
            n += 1
        if A[i] == A[i+1]:
            ju[i] = 0
    print(sum(ju))

Submission status: Wrong Answer

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

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

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.values() if x>1])
    # print(p)
    # print(div)
    print(len(div)-p)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
INF = float('inf')
from collections import defaultdict
dic = defaultdict(lambda:INF)

used = defaultdict(lambda:0)
remove = defaultdict(lambda:0)


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

cnt1 = a.count(1)
if cnt1 == 1:
    print(1)
    exit()
elif cnt1 >1:
    print(0)
    exit()

from collections import Counter
def prime_factorize(n):
    d = Counter()
    m = 2
    while m*m <= n:
        while n%m == 0:
            n //= m
            d[m] += 1
        m += 1
    if n > 1:
        d[n] += 1
    return d

for aa in a:
    if used[aa]:
        remove[aa]=1
        break
    c = prime_factorize(aa)
    flg = True
    for k in c.keys():
        if dic[k] == INF:
            dic[k] = aa//k
        else:
            if dic[k] > aa//k:
                dic[k] = aa//k
            elif (aa//k)%dic[k]==0:
                flg = False

    if flg:
        used[aa]=1

ans = sum(list(used.values()))-sum(list((remove.values())))
print(ans)

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)

if (A[0] == A[1]):
    count = 0
else:
    count = 1

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

    if (flag):
        count += 1

print(count)

Submission status: Wrong Answer

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

A.sort()

d = set()
for i in range(N-1):
    if A[i] == A[i+1]:
        d.add(A[i])

A = sorted(list(set(A)))

ans = []
for a in A:
    if a in d:
        continue
    f = True
    for k in ans:
        if a % k == 0:
            f = False
    if f:
        ans.append(a)
print(len(ans))

Submission status: Wrong Answer

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

length = len(given_list)
count = 0

given_list_sort = sorted(given_list, reverse=True)

for i in range(length):
    ele_1 = given_list_sort[i]
    for j in range(length):
        ele_2 = given_list_sort[j]
        if (i < j) and (ele_1 % ele_2 == 0):
            count += 1
            break

print(length - count)

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-1):
  flg = 0
  for j in range(i+1,N):
    if (A[i] % A[j] == 0):
      flg = 1
      break
  if (flg == 0):
    cnt += 1

if (A[N-1] == A[N-2]):
  print(cnt)
else:
  print(cnt+1)

Submission status: Wrong Answer

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

counter = 0

A.sort()


for i in range(N):
  for j in range(i):
    if A[i]%A[j] == 0:
      counter += 1
      break
      
if N >= 2:
  if A[0]%A[1] == 0:
    counter += 1
      
print(N-counter)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int,input().split()))
A = sorted(a, reverse=True)
count = 0
for i in range(N):
  flag = False
  for j in range(i+1,N):
    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:
from math import sqrt

def readinput():
    n=int(input())
    a=list(map(int,input().split()))
    return n,a

def main(n,a):
    sortedA=sorted(a)
    #m=int(sqrt(sortedA[n-1]))+1
    m=sortedA[n-1]//2+1
    #print(sortedA)
    #print(m)

    count=0
    for i in range(n):
        calc=False
        for j in range(n):
            if i==j:
                continue
            if sortedA[j]>m:
                #print(i,j)
                continue
            if(sortedA[i]%sortedA[j]==0):
                #print(i,j)
                break
            else:
                calc=True
        else:
            if calc==True:
                count+=1

    return count

if __name__=='__main__':
    n,a=readinput()
    ans=main(n,a)
    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()
    if i == 1:
        print(ans+len(a)+1)
        exit()
    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:
import bisect
N=int(input())
A=list(map(int,input().split()))
A.sort()
ans=0
for i in range(1,N)[::-1]:
    flag=0
    a=A[i]
    b=a//2
    r=bisect.bisect_left(A,b)
    for j in range(r+1):
        if j==i:
            if a%A[j+1]==0:
                flag=1
                break
        elif a%A[j]==0:
            flag=1
            break
    if flag==0:
        ans+=1
if A[0]!=A[-1]:
    ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

def is_prime(n):
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return n != 1

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

counter = Counter(A)

ans = 0
for k, v in counter.items():
    if v != 1:
        continue

    if is_prime(k):
        ans += 1
    else:
        can = True
        for d in make_divisors(k):
            if d == k:
                continue
            if d in counter:
                can = False
        if can:
            ans += 1

print(ans)

Submission status: Wrong Answer

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

a.sort(reverse=True)
cnt = 0
div = False
for i in range(1,len(a)+1):
    div = False
    for j in range(1,len(a)):
        if i-1 == j :
            continue
        if a[i-1] % a[j] == 0:
            div = True
            break
    if div :
        cnt += 1

print(n - cnt)

Submission status: Wrong Answer

Solution code:
def main():

    import collections

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

    A_s.sort()
    max_A = A_s[-1]

    # CNT_A = collections.Counter(A_s)
    CNT_A = collections.Counter(A_s).most_common()
    CNT_A.sort()

    NG_list = [True for i in range(max_A)]
    cnt = 0

    
    for i in range(len(CNT_A)):
        counter = CNT_A[i][1]
        if (counter > 1):
            continue
        
        num = CNT_A[i][0]
        # num = A_s[i]

        index_num = num - 1
        

        if (NG_list[index_num] == True):
            cnt += 1
            NG_list[index_num] = False
            

        coef = 1
        while (True):
            coef += 1
            tmp_num = coef * num
            
            if (tmp_num <= max_A):
                NG_list[tmp_num-1] = False
            else:
                break

    print(cnt)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
N=int(input())
A=list(map(int,input().split()))
X=[]


A.sort(reverse=True)

counter=2
tmp=10000000

for i in A:
    if tmp==i:
        counter+=1
    elif counter==0:
        X.append(tmp)
    else:
        counter=0
    tmp=i
if (tmp not in X )and counter==0:
    X.append(tmp)


#print(X)

B=sorted(X)
#print(X)#[24, 16, 11, 8, 3]
#print(B)#[3, 8, 11, 16, 24]


for i in X:
    for j in range(len(B)-1,-1,-1):
        #print(j)
        if B[j]%i==0 and i!=B[j]:
            del B[j]
            
print(len(B))

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)
    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:
#!/usr/bin/env python3

from pprint import pprint
import sys

sys.setrecursionlimit(10 ** 6)
INF = float('inf')


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

indices = [*range(n)]
sorted_indices = sorted(indices, key=lambda i: -A[i])
sorted_num = [A[i] for i in sorted_indices]
# print(sorted_indices)
# print(sorted_num)

res = []
for idx, i in enumerate(sorted_indices):
    num_i = A[i]
    # print(f'num_i = {num_i}')
    is_ok = True
    for j in range(idx + 1, n):
        num_j = sorted_num[j]
        # print(f'num_j = {num_j}')
        if num_i % num_j == 0:
            # print(f'False')
            is_ok = False
            break
    if idx == n - 1 and num_i == A[i-1]:
        is_ok = False
    if is_ok:
        res.append(i + 1)

print(len(res))

Submission status: Wrong Answer

Solution code:
n=int(input())
A=list(map(int,input().split()))
if n==1:
  print(1)
  exit()
A.sort()
A2=[]
before=A[0]
flag=0
for a in A[1:]:
  if before!=a:
    if flag==0:
      A2.append(before)
      before=a
    else:
      before=a
      flag=0
  else:
    flag=1
if flag==0:A2.append(A[-1])

ans=len(A2)
S=[]
for a in A2:
  flag==0
  for s in S:
    if a%s==0:
      ans-=1
      flag=1
      break
  if flag==0:
    S.append(a)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys,collections,bisect
input=sys.stdin.readline
n=int(input())
l=list(map(int,input().split()))
c=collections.Counter(l)
x=list(set(l))
x.sort()
def div(n):
    ass = set([n])
    for i in range(2,int(n**0.5)+1):
        if n%i == 0:
            ass.add(i)
            ass.add(n//i)
    return ass 
ans=0
if len(x)==0:
  print(0)
else:
  for i,y in enumerate(x):
    memo=0
    s=div(y)
    for z in s:
      if bisect.bisect_left(x[:i],z)==bisect.bisect_right(x[:i],z):
        memo+=1
    if memo==len(s) and c[y]==1:
        ans+=1
        
  print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
hitoketa=[]
count=0
A=list(map(int,input().split()))
A.sort()
sumi=set()
#for i in range(min(1000,N)):
    #hitoketa.append(A[i])
for i in range(len(A)):
    for j in range(len(A)):
        if A[i]%A[j]==0 and A[i]!=A[j] and j not in sumi:
            sumi.add(i)
            count+=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:
n = int(input())
a = list(map(int, input().split()))
cnt = n

for i in a:
  for j in a:
    if i%j == 0 and i != j:
      cnt -= 1
      break
print(cnt)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
n=int(input())
As=list(map(int,input().split()))
dup = [x for x in set(As) if As.count(x) > 1]
As=list(set(As)-set(dup))
As.sort()

mul=1
ans=[0]*len(As)
for i in range(len(As)):
    for j in range(i+1,len(As)):
        if As[i]*mul>As[j]:
            mul*As[i]
            break
        elif As[j]%As[i]==0:
            ans[j]+=1
print(ans.count(0))

Submission status: Wrong Answer

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


X=set()
d=set()
for i in A:
    if i in d:
        d.add(i)
    X.add(i)

ans = 0

for a in A:

    exist = False 
    X.remove(a)

    for i in range(1, int(-(-a**0.5//1))+1):
        if a%i == 0:
            if i in d or i in X:
                exist = True
                break
            if i in d or i in X:
                exist = True
                break

    if not exist:
        ans += 1
    X.add(a)
print(ans)

Submission status: Wrong Answer

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

#if n>1:
#    if li[0]==li[1]:
#        ans -= 1

import math
import bisect
import collections
c = collections.Counter(li)
li = list(set(li))
li.sort()
while len(li)>0:
    ba = li.pop(-1)
    if c[ba]>1:
        continue
    s_ba = math.ceil(math.sqrt(ba))
    index = bisect.bisect_right(li, s_ba)
    tmp_li = li[:index+1]
    #print(ba,tmp_li)
    for tt in tmp_li:
        if ba%tt == 0:
            break
    else:
        ans += 1
print(ans)