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

a.sort()
ans=0
i=0
while True:
    now=a[0]
    

    if len(a)==1: 
        ans+=1
    
    a = [aa for aa in a[1:] if aa%now!=0]
    
    if not a: 
        break
    ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
from math import ceil

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

m = 10**6+100
n_map = {}
v_a = []
for i in a:
    if i not in n_map:
        n_map[i] = 1
    else:
        n_map[i] += 1
v_a = [k for k, v in n_map.items() if v == 1]

v_a.sort()
vv_a = []
nn_map = {}
for i in v_a:
    if i in nn_map:
        continue
    vv_a.append(i)
    for j in range(1, ceil(m/i)+1):
        nn_map[i*j] = True
print(len(vv_a))

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
a = np.array([int(x) for x in input().split()])
count = 0
for i in a:
    i_a = i%a[a<i]
    if np.count_nonzero(i_a == 0) ==0:
        count+=1

print(count)

Submission status: Wrong Answer

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


N = int(input())
Alist = list(map(int, input().split()))
setA = list(set(Alist))
setA.sort(reverse=True)
dnum = len([x for x in setA if Alist.count(x) > 1])

cnt = 0
for idx, item in enumerate(setA):
    sub = setA[:idx:-1]
    for s in sub:
        if item % s == 0:
            break

    else:
        cnt += 1

print(cnt - dnum)

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 B:
        if i>105:break
        for j in ans:
        
            if j!=i and j%i==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:
N = int(input())
good = N
i = 0
A = [int(x) for x in input().split()]
A.sort(reverse=True)
for i in range(N):
    if A[i]==A[i-1]:
        good -= 1
        continue
    for j in range(i+1,N):
        if A[i]%A[j]==0:
            good -= 1
            break
print(good)

Submission status: Wrong Answer

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

count = 0

def explore(i):
  n_i = nums[i]
  for j in range(N):
    if j != i:
      n_j = nums[j]
      if n_j <= n_i // 2:
        if n_i % n_j == 0:
          return 0
  return 1

for i in range(N):
  count += explore(i)

print(count)

Submission status: Wrong Answer

Solution code:
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

import math

n=ni()
a=sorted(nl())


ans=0

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

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
ans=0
chklist=[1]*n
for i in range(n):
  for j in range(i+1,n):
    if a[i] < a[j]:
      if a[j]%a[i]==0:
        chklist[j]=0
    else:
      if a[i]%a[j]==0:
        chklist[i]=0
chkflag=True
for i in range(n-1):
  if a[i]!=a[i+1]:
    chkflag=False
    break
if chkflag:
  print(0)
else:
  print(sum(chklist))

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

    ctr = Counter(A)
    memo = []
    dp = set()
    ans = 0

    for a in sorted(A):
        if a == 1:
            if ctr[a] == 1:
                ans = 1
            break

        if ctr[a] == 1:
            for v in memo:
                if v > int(a ** 0.5):
                    if not (a % v == 0 and ((v in dp) or (a // v in dp))):
                        ans += 1
                    break
                if a % v == 0 and ((v in dp) or (a // v in dp)):
                    break
            else:
                ans += 1

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

    print(ans)

    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

res = 0
for i in range(n):
    for j in range(n):
        if  i == j:
           pass
        elif (a[i] == a[j]) or (a[i]%a[j] == 0):
            break

    else:
        res += 1

Submission status: Wrong Answer

Solution code:
import math
ni = input()
N = int(ni)
num = input().rstrip().split(" ")
numbers=[]
for i in num:
    numbers.append(int(i))
numbers.sort()
ans = set(numbers)
for i in numbers:
    list =[]
    k = i
    k += i
    while k<200000:
        list.append(k)
        k +=i
    t = set(list)
    ans = ans.difference(t)
print(len(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 = list(map(int, input().split()))
setA = set(A)
dup = set([x for x in setA if A.count(x) > 1])

count = 0
for i in range(len(A)):
    flag = False
    for div in make_divisors(A[i]):
        if div <= 1:
            continue
        if div == A[i]:
            if div in dup:
                flag = True
                break
        else:
            if div in setA:
                flag = True
                break
    if not flag:
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
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
while i < len(b) - 1:
  j = i + 1
  while j < len(b):
    if b[j] % b[i] == 0:
      b.remove(b[j])
    else:
      j += 1
  i += 1

print(len(b))

Submission status: Wrong Answer

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

for i in range(len(set_)):
    flag = True
    for j in range(n):
        if i == j:
            continue

        if list_[i] % list_[j] == 0:
            flag = False
            break

    if flag:
        cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
def func(alist,num):
    rl=[]
    rl.append(num)
    for di in alist:
        if di%num!=0:rl.append(di)
    return rl

n=int(input())
a=sorted(map(int,input().split()))
if len(set(a))==1:print(0);exit()
i=0
while(True):
    a=(func(a,a[i]))
    i+=1
    if len(a)<=i:break
print(len(a))

Submission status: Wrong Answer

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

print(ans)

Submission status: Wrong Answer

Solution code:
# D - Not Divisible
import numpy as np
from collections import Counter

N = int(input())
A = list(int(a) for a in input().split())
c = Counter(A)
dbl = len([i[0] for i in c.items() if i[1] >= 2])

A.sort()
A = np.array(A)
ans = 0
for i in range(N):
    if A[i] == 0:
        continue
    else:
        ans += 1
        B = A % A[i]
        A = A * B

print(ans-dbl)

Submission status: Wrong Answer

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


sa = sorted(a)

i = 0

while(True):

    j = i+1

    while(True):
        # print(i,j)

        if j >= len(sa):
            break
        if sa[j] % sa[i] == 0:
            sa.pop(j)
        else:
            j += 1

    if sa[i] == sa[i-1]:
        sa.pop(i)
    
    if i >= len(sa)-1:
        break

    i += 1

print(len(sa))

Submission status: Wrong Answer

Solution code:
from collections import deque

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

A.sort()
Aque = deque(A)
out = deque()
out.append(Aque.popleft())

if out[0] != 1:
    for i in range(N-1):
        yaku = Aque.popleft()
        flag = 1
        for j in out:
            if yaku % j == 0:
                flag = 0
                break
        if flag:
            out.append(yaku)

    ans = len(out)
    if ans == 1:
        print("0")
    else:
        print(ans)

else:
    print("1")

Submission status: Wrong Answer

Solution code:
"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""
import copy
import itertools
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


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

ans = 0

for a in A:
    if A.count(a) >= 2:
        continue
    L = prime_factorize(a)
    len_L = len(L)
    for i in range(1, len_L):
        c_list = list(itertools.combinations(L, i))
        for c in c_list:
            num = 1
            for n in c:
                num *= n
            if num in A:
                break
        else:
            continue
        break
    else:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = sorted([int(each) for each in input().split()])
print(a)
if len(set(a)) == 1:
    print(0)
else:
    counter = 1
    for i in range(1, n):
        for j in range(i):
            if i == j:
                continue
            if a[i]/a[j] == a[i]//a[j]:
                break
        else:
            print(i, j)
            counter += 1

    print(counter)

Submission status: Wrong Answer

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N = getN()
A = getList()
A = sorted(A)
S = Counter(A)

# エラストテネスの篩
prime = [2]
max = 10 ** 6 + 1
limit = int(math.sqrt(max))
data = [i + 1 for i in range(2, max, 2)]

while limit > data[0]:
    prime.append(data[0])
    data = [j for j in data if j % data[0] != 0]
prime = prime + data

prime_list = [0] * (10 ** 6 + 1)
for i in range(len(prime)):
    prime_list[prime[i]] = 1

def make_divisors(n):
    divisors = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            divisors.append(i)
            # √nで無い数についてもう一個プラス
            if i != n // i:
                divisors.append(n // i)
    return sorted(divisors)

numlist = [0] * (10 ** 6 + 1)

cnt = 0
for j in range(N):
    flag = True
    if prime_list[A[j]] == 0:
        ng_list = make_divisors(A[j])
        for ng in ng_list:
            if numlist[ng] >= 1:
                flag = False
                break
    if flag:
        numlist[A[j]] += 1
        cnt += 1

for i in range(len(numlist)):
    if numlist[i] >= 1 and S[i] >= 2:
        cnt -= S[i]
print(cnt)

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
    for x in res: 
        c = c + 1
    return(c)

def solve():
    n = inp()
    a = inlt()
    q = counter(a)
    print(len(list(set(a))) - qw(list(set(a)),len(list(set(a)))) - 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:
import math
n = int(input())
a = list(map(int,input().split()))

a.sort()
ng = []
ans = n
if n > 1:
    if a[0] == a[1]:
        ans -= 1

for i in range(n):
    if ng.count(i) == 0:
        for j in range(i + 1,n):
            if a[j] % a[i] == 0:
                if ng.count(j) == 0:
                    ng.append(j)
                    ans -= 1


print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import Counter
def main():
    n = int(input())
    A = list(map(int, input().split()))

    # 複数の同じ値がある場合は消去、
    C = Counter(A)
    N = []
    double_num = 0
    for num, cnt in C.items():
        N += [num]
        if cnt != 1:
            double_num += 1

    N.sort()
    len_n = len(N)
    memo = [1] * len_n
    mod_num = 0
    # 割り切れる値も消去
    for i in range(len_n - 1):
        for j in range(i + 1, len_n):
            if memo[j] == 0:
                break
            if N[j] % N[i] == 0:
                memo[j] = 0
                mod_num += 1

    print(len_n - mod_num - double_num)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

A.sort()
prime = []

de = []
for i in range(len(A)-1):
  if A[i] == A[i+1]:
    de.append(A[i])
de = de + list(set(de))
for j in de:
  A.remove(j)

while A:
  p = A[0]
  if p >= max(A)//2:
    break
  if len(A) >= 2 and A[0] == A[1]:
    A = [e for e in A if e % p != 0]
  else:
    prime.append(p)
    A = [e for e in A if e % p != 0]


print(len(prime)+len(A))

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())
list_A = list(map(int, input().split()))
set_A = set(list_A)
ans = 0

for num in list_A:
    set_B = set(make_divisors(num))
    set_A.remove(num)
    d = set_A | set_B
    if len(d) == len(set_A) + len(set_B) and len(set_A) != 0:
        ans += 1
    set_A.add(num)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys


N=int(input())
#print(N)
A=input().split()
A_int = [int(s) for s in A]
print(A_int)
Odd=[]
Even=[]
for factor in A_int:
  if factor%2==0:
    Even.append(factor)
  else:
    Odd.append(factor)
#print(Odd)
#print(Even)

#ここから本題
#print(A_int[2])
outcount=0
evencount=0
oddcount=0
for fact in A_int:
  evencount=0
  oddcount=0
  
  if fact%2==0:
    for even in Even:
      if fact%even==0:
        evencount+=1
      if evencount==2:
        outcount+=1
        break
  else:
    for odd in Odd:
      if fact%odd==0:
        oddcount+=1
      if oddcount==2:
        outcount+=1
        break
    
      
print(N-outcount)



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

"""

Submission status: Wrong Answer

Solution code:
import numpy as np

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

sosu = []
count = 0
for i in range(len(A)):
  if (i != len(A)-1 and A[i] == A[i+1]) or (i != 0 and A[i] == A[i-1]):
    continue
  for s in sosu:
    if A[i] % s == 0:
      break
  else:
    count+=1
    sosu.append(A[i])
print(count)

Submission status: Wrong Answer

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

sum = 0

if N == 1:
    print(1)

while True:
    X = A.pop(0) #左端をとる
    
    i = len(A)

    OK = True

    for Y in reversed(A):
        i -= 1

        if Y == X:
            OK = False
            A.pop(i)

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

    if OK:
        sum += 1

    if len(A) == 0:
        break

print(sum)

Submission status: Wrong Answer

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

for i in A:
    for j in A:
        if i != j:
            if i % j == 0:
                count += 1
                break
print(count)

Submission status: Wrong Answer

Solution code:
from math import gcd
from collections import defaultdict
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())
a = list(map(int, input().split()))
ans = 0
if len(set(a)) == 1:
    print(0)
    exit()
for j in a:
    tmp = set(a.copy())
    tmp.remove(j)
    table_ = make_divisors(j)
    for i in table_:
        if i in tmp:
            break
    else:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

A.sort()

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

if ct == 0:
    print(ct)
else:
    print(ct+1)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

ans = 0
if a_sort[0] == a_sort[-1]:
    print(ans)
else:
    for i in range(1,n):
        ans_ = 0
        for j in range(i):
            if a_sort[i] % a_sort[j] == 0:
                ans_ = 1
                break
            if a_sort[j] > a_sort[i]/2:
                break
        if ans_ == 0:
            ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
memo = {}


def make_divisors(n):
    if n in memo:
        return memo[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
    memo[n] = lower_divisors + upper_divisors[::-1]
    return memo[n]


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

setA = set(A)
result = 0

if N == 1:
    print(0)
else:
    for i in range(N):
        tmp = A[i]
        A[i] = 0
        setA = set(A)
        A[i] = tmp
        if 1 in setA:
            break
        divisors = make_divisors(A[i])

        for d in divisors:
            if d in setA:
                break
        else:
            result += 1

    print(result)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
S = set()
T = set()
for x in A:
    S.add(x)
    T.add(x)
cnt = 0
maxi = max(S)
for x in sorted(S):
    i = 2
    while x * i <= maxi:
        if x * i in T:
            T.remove(x*i)
        i += 1
print(len(T))

Submission status: Wrong Answer

Solution code:
a = int(input())
b = list(map(int,input().split()))
count = 0
b.sort()
for i in range(a):
  _count = 0
  _main = b[i]
  for j in range(i):
    if i==j:
      continue
    if (_main%b[j])==0:
      continue
    else:
      _count +=1
  if _count == i and _count!=0:
    count += 1
print(count)

Submission status: Wrong Answer

Solution code:
import numpy as np
N=int(input())
A=list(map(int, input().split()))
A.sort()
A=np.array(A)
j=0
C=0
for i in range(A.size):
  try:
    A=A[A%A[0]!=0]
    C=C+1
  except:
    break
print(C)

Submission status: Wrong Answer

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


def main():
    n = int(input())
    A = [int(i) for i in input().split()]

    MOD = 10 ** 9 + 7
    A.sort()
    A.append(MOD)
    s = set()

    ans = 0
    if A[0] != A[1]:
        ans += 1

    for i in range(1, n):
        if A[i] == A[i + 1]:
            continue

        for j in range(i):
            if A[j] in s:
                continue
            elif A[i] % A[j] == 0:
                s.add(i)
                break
        else:
            ans += 1
            # print(f"{i = }, {j = }, {ans = }")

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

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

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

else:
    print(len(A))

Submission status: Wrong Answer

Solution code:
# D TLE(WA)

n = int(input())
a_list = [int(x) for x in input().split()]
f_list = [True]*n
a_list.sort()

for i in range(n):
    _q = a_list[i]
    if i < n-1 and _q == a_list[i+1]:
        f_list[i] = False
        continue
    for j in range(0,i):
        if f_list[j]:
            continue
        elif _q % a_list[j] == 0:
            f_list[i] = False
            break

ans = sum(x for x in f_list)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

N = int(input())
A = list(map(int,input().split()))
counter = Counter(A)
s = sorted(set(A))
if len(A) == len(s):
    print(len(A))
else:
    lst = []
    ans = 0
    for i in range(len(s)):
        m = int(s[i]**0.5)+1
        flg = True
        for p in lst:
            if s[i]%p == 0:
                flg = False
                break
            elif m < p:
                break
        if flg:
            lst.append(s[i])
            if counter[s[i]] == 1:
                ans += 1
    print(ans)

Submission status: Wrong Answer

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

A.sort()
V = set()

ans = 0
mx = max(A)
for a in A:
    if a in V:
        continue
    ans += 1

    p = a
    while p <= mx:
        V.add(p)
        p += a

print(ans)

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))
for i in B:
    A = [x for x in A if x != i]
L=len(A)
for i in range(L):
    if i<len(A):
        for j in range(min(i+1,len(A)-1),len(A)-1):
            if	j<len(A):
            	if A[j]%A[i]==0:
                	A.remove(A[j])
print(len(A))

Submission status: Wrong Answer

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


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

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

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

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

    return result

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

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

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

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

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

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

def main():
    n=int(input())
    a=list(map(int,input().split()))
    a=sorted(a)
    count=0
    i=0
    while i<len(a)-1:
        b=[]
        for j in range(i+1,len(a)):
            if a[j]%a[i]==0:
                b.append(a[j])
        for j in b:
            a.remove(j)
        i+=len(b)
    print(len(a)) if len(a)>1 else print(0)









if __name__ == "__main__":

    main()

Submission status: Wrong Answer

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n = ii()
a = li()

a.sort()
a.append(1000000007)

dim = []
dim.append(a[0])

ans = 0
if a[0] != a[1]:
    ans += 1

for i in range(1,len(a)-1):
    for j in dim:
        if a[i] % j == 0:
            break
    else:
        if a[i] % a[i+1] != 0:
            dim.append(a[i])
            ans += 1
            # print('out',dim)

print(ans)

Submission status: Wrong Answer

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

import numpy as np


N = int(input())
A = np.array(readline().split(), dtype=np.int64)
A = np.sort(A)
i = 0
while True:
    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))