Problem:


Score : 400 points

Problem Statement

Given is a number sequence A of length N.

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

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

Constraints

All values in input are integers.

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

1 \leq A_i \leq 10^6

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answer.

Sample Input 1

5
24 11 8 3 16

Sample Output 1

3

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

Sample Input 2

4
5 5 5 5

Sample Output 2

0

Note that there can be multiple equal numbers.

Sample Input 3

10
33 18 45 28 8 19 89 86 2 4

Sample Output 3

5



Sample input:
5
24 11 8 3 16


Sample output:
3

Submission status: Wrong Answer

Solution code:
import 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 N == 1:
        print(0)
    elif 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):
            print("i", i)
            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())
a = list(map(int, input().split()))
# divlist = []

# 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]
count = 0
if 1 in a:
    if a.count(1) > 1:
        print(0)
    else:
        print(1)
else:
    for i in range(0,n):
        for j in range(0,n):
            if i == j:
                continue
            else:
                if a[i] % a[j] == 0:
                    count +=1
print(count)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
a = list(map(int, input().split()))

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

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(i) for i in 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
    lower_divisors.remove(1)
    return lower_divisors + upper_divisors[::-1]

divisors_list = {}
for i in range(1,1000001):
  divisors_list[i] = []

for k,i in enumerate(A):
  for j in make_divisors(i):
    divisors_list[j].append(k)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

arr.sort()
c = Counter(arr)
arr = [x for x, y in c.items() if y == 1]

cnt = 0

while cnt < len(arr):
    arr = [arr[cnt]] + [x for x in arr if x % arr[cnt] != 0]
    arr.sort()
    cnt += 1

result = set(arr) - {x for x, y in c.items() if y >= 2}

print(len(result))

Submission status: Wrong Answer

Solution code:
from collections import Counter


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

c = Counter(a)
new = [key for key, val in c.most_common() if val == 1]
div = [make_divisors(i) for i in new]

ans = [set(div[i]) & set(new) for i in range(len(new))]
ans = sum([1 for i in ans if len(i) == 1])
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque 
n = int(input())
a = list(map(int, input().split()))
a.sort()
a = deque(a)
y = [min(a)]
t = []
while a:
    v = a.popleft()
    x = 0
    for j in y:
        if v == j and v not in t:
            t.append(v)
        if v % j == 0:
            break
        else:
            x += 1

        if x == len(y):
            y.append(v)
print(len(y) - len(t))

Submission status: Wrong Answer

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

if 1 in a:
    if a.count(1)==1:
        print(1)
    else:
        print(0)

from copy import deepcopy
b = deepcopy(a)

for i in range(n):
    for j in range(n):
        if a[j]%a[i]==0:
            if not j==i:
                if a[j] in b:
                    b.remove(a[j])

print(len(b))

Submission status: Wrong Answer

Solution code:
from math import sqrt
from collections import Counter

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

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 divisors[:-1]

a=int(input())
b=[int(x) for x in input().split()]
b=sorted(b)
d=Counter(b)
c=0
for i in range(0, a):
  if d[b[i]] > 1:
    c+=1
  elif not is_prime(b[i]):
    di=make_divisors(b[i])
    for i in di:
      if i in b:
        c+=1
        break
print(a-c)

Submission status: Wrong Answer

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

num = 0
t_2 = False
t_3 = False
t_5 = False
t_7 = False

for i in range(N):
    flag = True

    if t_2 == True:
        if A[i] % 2 == 0:
            flag = False
    if t_3 == True:
        if A[i] % 3 == 0:
            flag = False
    if t_5 == True:
        if A[i] % 5 == 0:
            flag = False
    if t_7 == True:
        if A[i] % 7 == 0:
            flag = False

    if flag == True:
        for j in range(N):
            if A[i] % A[j] == 0 and i != j:
                flag = False
                break

    if A[i] == 2:
        t_2 = True
    elif A[i] == 3:
        t_3 = True
    elif A[i] == 5:
        t_5 = True
    elif A[i] == 7:
        t_7 == True

    if flag == True:
        print(i)
        num += 1

print(num)

Submission status: Wrong Answer

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

n = inp()
x = ip()
if len(set(x)) == 1:
    print(0)
elif len(x) == 1:
    print(1)
else:
    x.sort(reverse= True)
    ct = 1
    for i in reversed(range(n-1)):
        flag = 1
        for j in reversed(range(i+1,n)):
            if x[i]%x[j] == 0:
                flag = 0
                break
        if flag:
            ct += 1
    print(ct)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
A.sort()
D=defaultdict(int)
for some in A:
    D[some]+=1

n = 10**6
prime = {i for i in range(2, n)}
for i in range(2, n):
    if i in prime:
        for j in range(i*2, n, i):
            if j in prime:
                prime.remove(j)
ans = 0
for i in range(N):
    if D[A[i]] == 1:
        if A[i] in prime or A[i] == 1:
            ans += 1
        else:
            flag = True
            for j in range(i):
                if A[i] % A[j] == 0:
                    flag = False 
                    break
                if A[j]**2 > A[i]:
                    break
            if flag:
                ans += 1
    else:
        pass
print(ans)

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 = 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]:
      if A[i] % A[j] == 0:
        flag = 1
        break
  if flag == 0:
    ans += 1
    
print(ans)

Submission status: Wrong Answer

Solution code:
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7

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

def make_divisors(n: int) -> list:
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if i == 1:
            continue
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    return divisors

def main():
    n = i_input()
    num_list = i_list()

    num_list.sort()
    num_list = set(num_list)

    if len(num_list) == 1:
        print(0)
        exit()

    count = 0

    for num in num_list:
        yakusu_list = make_divisors(num)
        # if len(yakusu_list) == 0:
        #     count += 1
        #     continue
        # print(num, yakusu_list)
        for yakusu in yakusu_list:
            if yakusu in num_list:
                break
        else:
            count += 1

    print(count)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = input()
    a = list(map(int, input().split()))
    bt = [0] * len(a)
    a.sort()
    for i in range(0, len(a)):
        for j in range(0, len(a)):
            if (a[i] // 2) > a[j]:
                break
            if i == j or bt[i] == 1:
                continue
            if a[j] % a[i] == 0:
                bt[j] = 1
            if a[i] % a[j] == 0:
                bt[i] = 1
    print(len(bt) - sum(bt))



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def make_divisors(n, a, j):
    flag = 0
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            if i in a[:j]:
                flag = 1
                break
            if i != n // i:
                if n//i in a[:j]:
                    flag = 1
                    break
        i += 1
    return flag
    
def has_duplicates(seq):
    return len(seq) != len(set(seq))

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

for i in range(n):
    if i < n-1:
        if a[i] == a[i+1]:
            continue
    else:
        if a[i] == a[i-1]:
            continue
    if i == 0:
        count += 1
    else:
        flag = make_divisors(a[i], a, i)
        if flag == 0:
            count += 1
print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
p = [a[0]]
for i in range(1,n):
    v = 1
    for j in range(len(p)):
        if a[i] % a[j] == 0 or a[i] < 2*a[j]:
            v = 0
            break
    if v == 1:
        p.append(a[i])
ans = len(p)
for i in range(n-2):
    if a[i] == a[i+1] and a[i+1] != a[i+2] and a[i] in p:
        ans -= 1
if n > 1:
    if a[-1] == a[-2] and a[-1] in p:
        ans -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
List = list(map(int, input().split()))
count = 0
for i in range(N):
  x = List.pop(i)
  for j in range(N-1):
    if x == List[j] or x % List[j] == 0:
      break
    else:
      count += 1
      break
  List.insert(i, x)
print(count)

Submission status: Wrong Answer

Solution code:
"""
    こんにちは。これはクシャルです
    
    Author : thekushalghosh (クシャル)
    Team   : CodeDiggers
 
    I prefer Python language over the C++ language :p :D
        
    Visit my website : thekushalghosh.github.io
"""
import sys,math,cmath,time
start_time = time.time()
##########################################################################
################# ---- THE ACTUAL CODE STARTS BELOW ---- #################
def qw(arr,n):
    s = dict()
    c = 0
    max_ele = -10**9
    for i in range(n):  
        s[arr[i]] = 1 
        max_ele = max(max_ele, arr[i])
    res = dict() 
    for i in range(n):  
        if (arr[i] != 0): 
            for j in range(arr[i] * 2,max_ele + 1, arr[i]):
                if (j in s.keys()): 
                    res[j] = 1
    q = []
    for x in res:
        c = c + 1
        q.append(x)
    return(c,q)

def solve():
    n = inp()
    a = inlt()
    a.sort()
    c,w = qw(list(set(a)),len(list(set(a))))
    w.sort()
    ww = []
    qq = 0
    if w:
        for i in range(len(a)):
            if a[i] != w[qq]:
                ww.append(a[i])
            elif qq + 1 < len(w):
                qq = qq + 1
    else:
        ww = list(a)
    q = counter(ww)
    print(len(list(set(a))) - c - len(q) + q.count(0) + q.count(1))
            
################## ---- THE ACTUAL CODE ENDS ABOVE ---- ##################
##########################################################################
 
def main():
    global tt
    if not ONLINE_JUDGE:
        sys.stdin = open("input.txt","r")
        sys.stdout = open("output.txt","w")
    t = 1
    for tt in range(t):
        solve()
    if not ONLINE_JUDGE:
        print("Time Elapsed :",time.time() - start_time,"seconds")
        sys.stdout.close()
    
#---------------------- USER DEFINED INPUT FUNCTIONS ----------------------#
def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    return(input().strip())
def invr():
    return(map(int,input().split()))
 
#------------------ USER DEFINED PROGRAMMING FUNCTIONS ------------------#
def counter(a):
    q = [0] * (max(a) + 1)
    for i in range(len(a)):
        q[a[i]] = q[a[i]] + 1
    return(q)
 
def string_counter(a):
    q = [0] * 26
    for i in range(len(a)):
        q[ord(a[i]) - 97] = q[ord(a[i]) - 97] + 1
    return(q)

def power_two(n):
    if n == 1:
        return(True)
    sttr = str(n)
    len_str = len(sttr)
    sttr = list(sttr)
    num = 0
    if (len_str == 1 and sttr[len_str - 1] == '1'): 
        return(False)
    while (len_str != 1 or sttr[len_str - 1] != '1'):
        if ((ord(sttr[len_str - 1]) - ord('0')) % 2 == 1):
            return(False)
        j = 0; 
        for i in range(len_str):  
            num = num * 10 + (ord(sttr[i]) - ord('0')); 
            if (num < 2): 
                if (i != 0):  
                    sttr[j] = '0'
                    j += 1
                continue
  
            sttr[j] = chr((num // 2) + ord('0'))
            j += 1; 
            num = (num) - (num // 2) * 2
        len_str = j
    return(True)

def getLeftmostBit(n): 
    m = 0
    while (n > 1) : 
        n = n >> 1
        m += 1
    return(m)
def getNextLeftmostBit(n, m) : 
    temp = 1 << m 
    while (n < temp) : 
        temp = temp >> 1
        m -= 1
    return m
def bitcounter(n) :
    m = getLeftmostBit(n) 
    return _countSetBits(n, m) 
def _countSetBits(n, m) :
    if (n == 0) : 
        return 0
    m = getNextLeftmostBit(n, m)
    if (n == (1 << (m + 1)) - 1) : 
        return ((m + 1) * (1 << m))
    n = n - (1 << m)
    return (n + 1) + bitcounter(n) + m * (1 << (m - 1)) 

def log_two(n): 
    return(math.log(n) / math.log(2))

#-----------------------------------------------------------------------#
        
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
    input = sys.stdin.readline
    
main()

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
ANS = []
while A:
    p = A[0]
    if p > 10**3:
        break
    else:
        if len(A) <= 1 or p not in A[1:]:
            ANS.append(p)
        A = [a for a in A[1:] if a % p != 0]

ans = len(ANS) + len(A)
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
def lispin(t=int):return list(pin(t))
#%%code
def resolve():
    N,=pin()
    
        
    A=list(set(pin()))
    B=sorted(A)
    #print(B)

    ans=1
    if len(B)==1:
        print(0)#what?
        return
    if B[0]<B[1]:ans+=1
    
    must_see=[]
    must_see.append(B[0])
    
    """
    for cnt in range(1,10**7):
        if cnt>=N:break
        temp=B[cnt]
        cond=1
        for i in must_see:
            shit+=1
            if temp%i==0:
                cond=0
                break
        if cond==1:
            ans+=1
            must_see.append(temp)
    print(ans)
    """
    ans=B[:]
    x=[]
    for i in range(10**7):
        if i == len(ans):
            break
        temp=ans[i]
        for j in ans:
        
            if j!=temp and j%temp==0:
                #iremasen
                continue
            else:
                #iremasu
                x.append(j)
        ans=x[:]
        #print(i,ans)
        x=[]
    print(len(ans))
    


#%%submit!
resolve()

Submission status: Wrong Answer

Solution code:
_ = int(input())
a = sorted(list(set(map(int, input().split(" ")))))
n = len(a)
prime = []

for i in range(0, n):
    if len(a) == 0:
        break
    t = a[0]
    a = [ item for item in a if item % t != 0]
    prime.append(t)

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

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter
def input():
    return sys.stdin.readline()[:-1]
def main():
    N = int(input())
    A = sorted(list(map(int,input().split())))
    C = Counter(A)
    for k in range(N):
        if C[A[k]] > 1:
            A[k] = 0
        if A[k] > 0:
            for l in range(k+1,N):
                if A[l]%A[k] == 0:
                    A[l] = 0
    ans = 0
    for e in A:
        if e > 0:
            ans += 1
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
num = len(a) - len(set(a))
a = sorted(a)
s = set()
ans = 0
for i in a:
    if i not in s:
        ans +=1
        for j in range(10**6 // i + 1):
            s.add(j*i)
print(max(ans - num, 0))

Submission status: Wrong Answer

Solution code:
import math
import collections
from numba import jit
@jit(cache=True)
def kkk(al):
	k=0
	for i in range(n):
		f=0
		for j in range(i+1,n):
			if min(al[i],al[j])-math.gcd(al[i],al[j])==0:
				f=1
				break
		if f==0:
			k=k+1
	return(k)
        
n=int(input())
a=input()
al=list(map(int,a.split()))

c = collections.Counter(al)
w=n-len(c)
print(kkk(al)-w)

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 = list(set(a))
total = 0
if len(b)==1:
    print(0)
else:
    for j in range(len(b)):
        f = set(b)-set([b[j]])
        g = set(make_divisors(b[j]))
        if f&g == set():
            total += 1
    print(total)

Submission status: Wrong Answer

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

    def get_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]

    if 1 in a:
        print(0)
    elif len(a) == 1:
        print(1)
    else:
        count = 0
        a.sort()
        b = list(reversed(a))
        c = b[:]
        for item in b:
            c.remove(item)
            if item in c:
                break
            else:
                divisors = get_divisors(item)
                divisors.remove(1)
                divisors.remove(item)

                if len(divisors) > 0:
                    lim = max(divisors)
                    flag = True
                    for i in a:
                        if i > lim:
                            break
                        elif item % i == 0:
                            flag = False
                            break
                    if flag:
                        count += 1
                else:
                    count += 1

        print(count)


if 'unittest' not in globals():
    resolve()

Submission status: Wrong Answer

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

#S = [[0 for j in range(3)] for i in range(2)]　2行3列の場合
#S = [[0 for j in range(3)] for i in range(2)]
S.sort()
if S[0]==1 and N==1:
    print(1)
    exit()
elif S[0]==1 and S[1]==0:
    print(0)
    exit()
elif S[0]==1:
    print(1)
    exit()
elif S[0]==S[len(S)-1]:
    print(0)
    exit()
S.reverse()

dic={}
for i in range(N):
    tmp=S[i]
    if tmp in dic:
        dic[tmp]+=1
    else:    
        dic[tmp]=1

keys = [k for k, v in dic.items() if v == 1]
keys.sort()
keys.reverse()

keys2 = [k for k, v in dic.items() if v >= 1]
keys2.sort()

divcount=0
lenk=len(keys)
lenk2=len(keys2)
for i in keys:
    for j in keys2:
        if i!=j:
            if i%j==0:
                
                divcount+=1
                break


print(N-divcount-(lenk2-lenk))

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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


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

    A.sort(reverse=True)
    A = tuple(A)

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

    if A[N-1] != A[N-2]:
        ans += 1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import bisect
import math

n = int(input())
a = [int(num) for num in input().split()]
a.sort()
prev = -1
for i in range(n):
    if a[i] == prev:
        prev = a[i]
        a[i] = -1
        a[i-1] = -1
    else:
        prev = a[i]
        
a.sort()
idx = bisect.bisect_right(a,0)
a = a[idx:]
#print(a)
n = len(a)
b = [0] * 1000001

for i in range(n):
    fl = True
    for j in range(1,int(math.sqrt(a[i])) + 2):
        if a[i] % j == 0 and (b[j] > 0 or b[a[i] // j] > 0):
            fl = False
            break
    if fl:
        b[a[i]] = 1
        
print(sum(b))

Submission status: Wrong Answer

Solution code:
import collections

def make_divisors(n,B):

    if 1 in B:
        return False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            if i in B:
                return False
            if n//i in B:
                return False

    return True



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

    A.sort()

    count = 0
    for i,v in dict(C).items():
        if v!= 1:
            continue
        if make_divisors(i,B):
            count+=1
    print(count)
resolve()

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import defaultdict

input()
A = np.fromstring(input(), int, sep=' ')


counter = defaultdict(int)
for x in A:
    counter[x] += 1

A = np.array(list(set(A)))
A.sort()

count = 0
f = np.ones_like(A, dtype=bool)
for i, x in enumerate(A):
    if not f[i]:
        continue
    # print(i, x, count, A, f)

    if counter[x] == 1:
        count += 1

    if x <= 10**4:
        f[i+1:] &= (A[i+1:] % x != 0)

print(count)

Submission status: Wrong Answer

Solution code:
import math

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

if len(set(a)) == 0:
    print(0)
    exit()

ans = 0
res = 1
for i in range(n):
    if math.gcd(res, a[i]) % 2 == 1:
        res *= a[i]
        ans += 1

print(ans)

Submission status: Wrong Answer

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

n = int(input())
readline = sys.stdin.readline
a = [int(i) for i in readline().split()]
#a = list(map(int, input().split()))

a = list(set(a))
n = len(a)
a.sort()

ans = 0

if n != 1:
    for i in range(n):

        x = a[i]

        j = 0
        while a[j] <= x//2:
            if i != j and x%a[j] == 0:
                break
            else:
                j += 1
        else:
            ans += 1

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<a//2+1) ]
    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:
from collections import defaultdict
import math
def divisors(n):
	i = 1
	div = []
	while i <= math.sqrt(n):
		if (n % i == 0):
			if (n / i == i) : 
				div+=[i] 
			else:
				div+=[i,n//i]
		i+=1
	return div
	
n = int(input())
arr = list(map(int,input().split()))
d = defaultdict(int)
for i in arr:
	d[i]+=1
ans = 0
for i in arr:
	if d[i]!=1:
		continue
	temp = divisors(i)
	f = 0
	for j in temp:
		if j!=i:
			if d[j]==1:
				f = 1
				break
	if f==0:
		ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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 and not n == n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors


N = int(input())
A = list(map(int, input().split()))
A_counter = Counter(A)
A_val = A_counter.values()
cnt = 0
for a_val in A_val:
    if a_val == 1:
        continue
    cnt -= a_val
exist_flags = [False] * (10 ** 6)

for a in A:
    exist_flags[a - 1] = True
for a in A:
    div_list = make_divisors(a)
    for div_val in div_list:
        if exist_flags[div_val - 1]:
            break
    else:
        cnt += 1
print(cnt)

Submission status: Wrong Answer

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

A = list(set(A))
if len(A) == 1:
    print(0)
    exit()
heapq.heapify(A)
count = 0
divisor_list = []
while len(A) >= 1:
    count += 1
    item = heapq.heappop(A)
    for j in list(A):
        if j % item == 0:
            A.remove(j)

print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split(" ")))
ans = []
counter = 1

A.sort(reverse = True)
if N == 1:
  print(1)
else:
  if A[N-2] != A[N-1]:
    ans.append(A[N-1])
  for i in A:
    for j in range(counter,N):
      if i%A[j] == 0:
          break
      if j == N-1:
        if i%A[j] != 0:
          ans.append(i)

    counter += 1
print(len(ans))

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
a = Counter(map(int, input().split()))
ans = n
for num, count in a.items():
    if count > 1:
        ans -= count
        continue
    if 1 in a and num != 1:
        ans -= count
        continue
    if 2 * 2 <= num:
        if num % 2 == 0:
            if 2 in a or (num // 2) in a:
                ans -= count
                continue
    else:
        continue
    i = 3
    while i * i <= num:
        if num % i == 0:
            if i in a or (num // i) in a:
                ans -= count
                break
        i += 2
print(ans)

Submission status: Wrong Answer

Solution code:
kosu = int(input())
suretu = list(input().split(" "))
count = 0

for i in range(kosu):
    for j in range(kosu):
        if i == j:
            continue
        elif int(suretu[i]) % int(suretu[j]) == 0:
            break
        elif j + 1 == kosu:
            count += 1

print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
p = [a[0]]
for i in range(1,n):
    v = 1
    for j in range(len(p)):
        if a[i] % a[j] == 0 or a[i] < a[j]:
            v = 0
            break
    if v == 1:
        p.append(a[i])
ans = len(p)
for i in range(n-2):
    if a[i] == a[i+1] and a[i+1] != a[i+2] and a[i] in p:
        ans -= 1
if n > 1:
    if a[-1] == a[-2] and a[-1] in p:
        ans -= 1
print(ans)

Submission status: Wrong Answer

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