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:
def examA():
    X = LI()
    for i in range(len(X)):
        if X[i]==0:
            ans = i+1
    print(ans)
    return

def examB():
    X, Y = LI()
    ans = "No"
    for i in range(X+1):
        if i*2+(X-i)*4==Y:
            ans = "Yes"
    print(ans)
    return

def examC():
    X, N = LI()
    P = LI()
    P = set(P)
    cur = inf
    ans = -1
    for i in range(-1,102):
        if i in P:
            continue
        now = abs(i-X)
        if now<cur:
            ans = i
            cur = now
    print(ans)
    return

def examD():
    N = I()
    A = LI()
    n = max(A)
    C = set()
    D = set()
    for a in A:
        if a in D:
            C.discard(a)
            continue
        D.add(a)
        C.add(a)
    if 1 in D:
        if 1 in C:
            print(1)
        else:
            print(0)
        return
    C2 = deepcopy(C)
    for a in C:
        for i in range(2,1+n//a):
            if (i*a) in C2:
                C2.discard(i*a)
    ans = len(C2)
    print(ans)
    return

def examE():
    N, Q = LI()
    AB = [LI()for _ in range(N)]



    ans = 0
    print(ans)
    return

def examF():
    H, W, K = LI()
    x1,y1,x2,y2 = LI()
    x1 -= 1; y1 -= 1; x2 -= 1; y2 -= 1
    C = [SI()for _ in range(H)]

    def bfs_grid(h, w, s, maze):
        distance = [[inf] * w for _ in range(h)]

        def bfsg():
            queue_up = deque()
            queue_d = deque()
            queue_r = deque()
            queue_l = deque()
            queue_up.append(s)
            queue_d.append(s)
            queue_r.append(s)
            queue_l.append(s)
            distance[s[0]][s[1]] = 0
            while (len(queue_up) or len(queue_r) or len(queue_d) or len(queue_l)):
                if queue_up:
                    y, x = queue_up.popleft()
                    for k in range(1, K + 1):
                        nx, ny = x, y + k
                        if (0 <= nx < w and 0 <= ny < h and maze[ny][nx] != '@'):
                            if distance[ny][nx] <= distance[y][x] + 1:
                                continue
                            queue_r.append((ny, nx))
                            queue_l.append((ny, nx))
                            distance[ny][nx] = distance[y][x] + 1
                        else:
                            break
                        if k == K:
                            queue_up.append((ny, nx))
                if queue_d:
                    y, x = queue_d.popleft()
                    for k in range(1, K + 1):
                        nx, ny = x, y - k
                        if (0 <= nx < w and 0 <= ny < h and maze[ny][nx] != '@'):
                            if distance[ny][nx] <= distance[y][x] + 1:
                                continue
                            queue_r.append((ny, nx))
                            queue_l.append((ny, nx))
                            distance[ny][nx] = distance[y][x] + 1
                        else:
                            break
                        if k == K:
                            queue_d.append((ny, nx))
                if queue_r:
                    y, x = queue_r.popleft()
                    for k in range(1, K + 1):
                        nx, ny = x + k, y
                        if (0 <= nx < w and 0 <= ny < h and maze[ny][nx] != '@'):
                            if distance[ny][nx] <= distance[y][x] + 1:
                                continue
                            queue_up.append((ny, nx))
                            queue_d.append((ny, nx))
                            distance[ny][nx] = distance[y][x] + 1
                        else:
                            break
                        if k == K:
                            queue_r.append((ny, nx))
                if queue_l:
                    y, x = queue_l.popleft()
                    for k in range(1, K + 1):
                        nx, ny = x - k, y
                        if (0 <= nx < w and 0 <= ny < h and maze[ny][nx] != '@'):
                            if distance[ny][nx] <= distance[y][x] + 1:
                                continue
                            queue_up.append((ny, nx))
                            queue_d.append((ny, nx))
                            distance[ny][nx] = distance[y][x] + 1
                        else:
                            break
                        if k == K:
                            queue_l.append((ny, nx))

            return distance

        return bfsg()
    L = bfs_grid(H,W,(x1,y1),C)
    #print(L)
    ans = L[x2][y2]
    if ans==inf:
        ans = -1
    print(ans)
    return

from decimal import Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Wrong Answer

Solution code:
import numpy as np
N = list(map(int, input().split()))[0]
A = np.array(list(((map(int, input().split())))))
idx = np.argsort(A)
A = np.sort(A)
Z = np.zeros(N)

def get_result():
    result = 0
    for i in range(N):
        flag = True
        if i < N - 1 and A[i] == A[i + 1]:
            flag = False
        for j in range(i):
            if Z[j] != 0:
                continue
            d, m = divmod(A[i], A[j])
            if d < 2:
                break
            if m == 0:
                flag = False
                Z[i] = 1
                break
            if A[i] / A[j] < 2:
                break
        if flag:
            result += 1
    return result

print(get_result())

Submission status: Wrong Answer

Solution code:
import copy

n = int(input())
a = [int(item) for item in input().split()]

a.sort()

b = copy.deepcopy(a)
flag = []

for i in range(n):
    if i in flag:
        continue
    for j in range(i+1, n):
        if j in flag:
            continue
        if a[j] % a[i] == 0 and a[j] in b:
            flag.append(j)
            b.remove(a[j])

print(len(b))

Submission status: Wrong Answer

Solution code:
def main():
  n=int(input())
  a=list(map(int,input().split()))
  a.sort()
  if a[0]==a[-1]:
    print(0)
    exit()
  if a[0]==1:
    print(1)
    exit()
  a=a+[0]
  ans=1
  x=1
  if a[0]==a[1]:
    ans=0
  for i in range(x,n):
    for j in range(i+1):
      if a[i]%a[j]==0:
        ans-=1
        break
      if a[j]>pow(a[i],0.5):
        if a[i]==a[i-1] or a[i]==a[i+1]:
          ans-=1
        break
    ans+=1
  print(ans)
  
if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
def calc():
    n, *a = map(int, open(0).read().split())
    if n == 0:
        return 0
    if n == 1:
        return 1

    a.sort()
    count = 0
    r = set()
    prev = -1 if a[0] != a[1] else a[0]
    for x in a:
        if x == prev:
            continue
        r.add(x)
        if divis(x) & r:
            continue
        prev = x
        count += 1
    return count

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

print(calc())

Submission status: Wrong Answer

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

a.sort()

# print(a)
ans = 0
for i in range(n):
    # first element
    if i == 0:
        if a[0] in a[1:]:
            ans += 0
        else:
            ans += 1
    
    flag = True
    # others
    for j in range(0, i):
        if a[i] % a[j] == 0:
            flag = False
            break
    
    if flag:
        ans += 1

print(ans-1)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

B = set(A)
count = 0

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

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

print(count)

Submission status: Wrong Answer

Solution code:
import math
def is_prime(n):
    if n == 1: return False
    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True

n = int(input())
a = list(map(int, input().split()))
# a = list(set(a))
# n = len(a)
print(a)
ans = 0
prime_1 = False
if 1 in a:
    prime_1 = True

for i in range(n):
    if is_prime(a[i]):
        if prime_1 == False and a[i] not in a:
            print("prime",a[i])
            ans += 1
            continue
    flag = True
    for j in range(n):
        if i != j and a[i] % a[j] == 0:
            flag = False
            break
    if n != 1 and flag:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8

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

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

for i in a:
    for j in a:
        if i!=j and i%j==0:
            ans +=1
            break

print(abs( ans - n*(1+len(a)-len(list(set(a)))) ))

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):
                        ans += 1
                    break
                if a % v == 0:
                    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()))


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

ans = 0
print(X,d)

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 a//i in d or a//i in X:
                exist = True
                break

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

Submission status: Wrong Answer

Solution code:
import math

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

if len(A) > 1:
    for i in range(len(A)):
        for j in range(i+1):
            if A[j] > math.sqrt(A[i]):
                ans += 1
                break
            if A[i] % A[j] == 0:
                if j != i:
                    break
        else:
            ans += 1

print(ans)

Submission status: Wrong Answer

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

a.sort()
count = 0

for i in range(n):
  flag = 0
  for j in range(n):
    if(a[i] < a[j]):
      flag = 1
    elif(a[i] == a[j]):
      if(i == j):
        pass
      else:
        flag = 0
    else:
      if(a[i]%a[j] == 0):
        flag = 0
        break
      else:
        flag = 1
  if(flag == 1):
    count = count + 1
      
print(count)

Submission status: Wrong Answer

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

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

if sum(l) == n*l[0]:
    print(0)
    exit()

l.sort()
j = [0]*2

for i in l:
    if i%2 == 0:
        if j[0] == 0:
            j[0] = i
            break

for m in l:
    if m%2 != 0:
        if j[1] == 0:
            j[1] = m
            break
    
ans = 0
for k in l:
    if k in j:
        ans += 1
    elif k%2 == 0:
        if k%j[0] != 0:
            ans += 1
    else:
        if k%j[1] != 0:
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
N=list(map(int,input().split()))
A=list(map(int,input().split()))
A=list(set(A))
A.sort()
 
ans=[]
for a in A:
    for ans_idx in range(len(ans)+1):
        if ans_idx == len(ans):
            ans.append(a)
            break
            
        ans_temp=ans[ans_idx]
        if a % ans_temp == 0:
            break
        
print(len(ans))

Submission status: Wrong Answer

Solution code:
def solve(Auniq, Ai):
  for x in Auniq:
    if Ai % x == 0:
      return False
  return True

def main():
  N = int(input())
  A = list(map(int, input().split()))
  res = 0
  for i, Ai in enumerate(A):
    Aless = list(filter(lambda x: x< Ai, A))
    if len(Aless) == 0:
      res += 1
    else:
      res += solve(set(Aless), Ai)
  return res

print(main())

Submission status: Wrong Answer

Solution code:
import math
import bisect

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

a.sort()

count = 0

if(n == 1):
    print(1)
else:
    for i in reversed(range(n)):
        flag = 0
        for j in range(i):
            if(a[i] % a[j]== 0):
                flag = 1

        if(flag == 0):
            count += 1
    if(a[0] == a[1]):
        count -= 1
    print(count)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys


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


def resolve():
    n = int(input().rstrip())
    a_list = list(map(int, input().split()))

    a_list.sort()


    cnt = 0

    for i in range(len(a_list)):
        num = a_list[i]

        # 最小の値は割れない
        if i == 0:
            continue

        div_flag = False
        for j, num2 in enumerate(a_list):
            #print(num, num2)
            if i == j:
                break
            if num % num2 == 0:
                div_flag = True
                break

        if not div_flag:
            cnt += 1

    print(cnt)


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
ans=N
if len(set(A))==1:
    print(0)
elif all(A)%2==min(A):
    print(1)
else:
    for i in range(N):
        for j in range(N):
            if j==i:
                continue
            if A[i]<A[j]:
                continue
            if A[i]%A[j]==0:
                ans-=1
                break
    print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
print(0)

Submission status: Wrong Answer

Solution code:
import math


#n=map(int,input().split())
n=int(input())
a=list(map(int,input().split()))
count=0
a.sort()
b=[]
while True:
    if a==[]:
        break
    """
    if a[0] in a[1:len(a)]:
        temp=a[0]
        a.pop(0)
        a.pop(a.index(temp))
        continue
    """
    b.append(a[0])
    a.pop(0)

    atemp=[i for i in a if i % b[-1]!=0]
    a=atemp.copy()
print(len(b))

Submission status: Wrong Answer

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

n = int(input())
a = sorted(list(map(int, input().split())))
b = list(map(lambda n: divisors(n), a))

cnt = n
for i in range(n):
    for j in range(n-1, -1, -1):
        if i != j and a[i] in b[j]:
            cnt -= 1
            break
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import Counter

def main():
    n_ = int(input())

    if n_ == 1:
        print(1)
        return

    A = Counter(map(int, input().split()))
    A = set(k for k, v in A.items() if v == 1)
    ans = len(A)

    def divisors(n):
        for i in range(2, int(a ** 0.5) + 1):
            if n % i == 0:
                if i in A and i != 1:
                    return 1
                if n % (n // i) == 0:
                    if n // i in A:
                        return 1
        return 0

    for a in A:
        ans -= divisors(a)

    print(ans)

main()

Submission status: Wrong Answer

Solution code:
import sys
import collections
import math

def main():

    input = sys.stdin.readline

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

    ans = 0
    sort_A = sorted(set(A))

    c = collections.Counter(A)

    calc_list = []

    for a in sort_A:
        flag = True
        for k in calc_list:
            if math.sqrt(a) < k:
                break
            if (a % k == 0):
                flag = False
                break

        if flag == True:
            if c[a] == 1:
                ans += 1

            if len(calc_list) == 0:
                calc_list.append(a)
            elif calc_list[-1] != a:
                calc_list.append(a)

    print(ans)





if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

iter = 0

for i in a:
  lst = [i%j for j in a]
  print(lst)
  if lst.count(0) == 1:
    iter = iter + 1
    #print(iter)
print(iter)

Submission status: Wrong Answer

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

a.sort()

for i in range(n):
    flag=True
    for j in range(n):
        if(((a[i]%a[j]) == 0) and (a[i] != a[j])):
            flag=False
    if((flag == True) and (a[i] != a[j])):
        x += 1

print(x)

Submission status: Wrong Answer

Solution code:
n = input()
alla = input()
a_l = alla.split()
counter = 0
for i in a_l:
  cnt = 0
  for j in a_l:
    if i == j:
      pass
    elif int(i) % int(j) == 0:
      break
    else:
      cnt += 1
      pass
    
    if cnt == int(n)-1:
      counter += 1
print(counter)

Submission status: Wrong Answer

Solution code:
def check_prime(k):
    if k == 1:return 1
    num = int(k ** 0.5 // 1)
    for i in range(2, num + 1):
        if k % i == 0:
            if check.get(i) or check.get(k//i):return 0

    return 1

n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
double = dict()
check = dict()

for i in range(n):
    if i < n - 1 and a[i] == a[i + 1]:
        double[a[i]] = 1
        check[a[i]] = 1
        continue
    if double.get(a[i]):continue


    temp = check_prime(a[i])
    if temp:
        check[a[i]] = 1
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
def check(N):
    for i in range(1,int(N**0.5)+1):
        if(N%i==0):
            if i in s:
                return True
            if(N//i!=i):
                if N//i in s:
                    return True
    return False

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

cnt=[0]*1000001
for i in range(N):
    cnt[A[i]]+=1
ng=set()
for i in range(N):
    if cnt[A[i]]>1:
        ng.add(A[i])
min_=min(A)
s=set(A)

ans=0
for i in reversed(range(N)):
    if A[i] in ng:
        continue
    if A[i]<min_*2:
        ans+=1
        break
    s.remove(A[i])
    t=check(A[i])
    if not t:
        ans+=1
    s.add(A[i])
print(ans)

Submission status: Wrong Answer

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

if len(a_list) < 2:
    print(0)
else:
    count = 1
    for i in range(1, len(a_list)):
        flag = True
        target = a_list[i]
        for child in a_list[:i]:
            if target%child == 0:
                flag = False
                break
        if flag:
            count += 1
    print(count)

Submission status: Wrong Answer

Solution code:
import collections

N = int(input())
h = list(map(int, input().split()))
h.sort(reverse = True)
l = []
for i in range(0, N):
    d = []
    for j in range(0, max(0, len(l))):
        if l[j] % h[i] == 0:
            d.append(l[j])
    for k in range(0, len(d)):
        l.remove(d[k])
    l.append(h[i])
if len(collections.Counter(h)) == 1:
    l.clear()
print(len(l))

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)

Submission status: Wrong Answer

Solution code:
import numpy as np


def main():
    n = int(input())
    As = list(map(int, input().split()))
    if 1 in As:
        print(0)
        exit()
    As = sorted(As)
    As_arr = np.array(As)
    ans = 0

    while np.any(As_arr):
        if np.sum(As_arr == As_arr[0]) >= 2:
            As_arr = As_arr[np.where(As_arr % As_arr[0] != 0)]
        else:
            As_arr = As_arr[np.where(As_arr % As_arr[0] != 0)]
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = 5
ARR = [24, 11, 8, 3, 16]
#
# N = 4
# ARR = [5, 5, 5, 5]
#
# N = 10
# ARR = [33, 18, 45, 28, 8, 19, 89, 86, 2, 4]

N = int(input())

ARR = list(map(int, input().split()))


def filterNotTheSame(n, arr):
    dict = {}
    for i in range(n):
        if dict.get(arr[i]) == None:
            dict.__setitem__(arr[i], 1)
        else:
            dict.__delitem__(arr[i])

    return dict.keys()


def calculate(arr):
    if len(arr) == 0:
        return []
    arr = sorted(arr)
    # limit = arr[-1] // 2 + 1

    limit = arr[-1]

    prev = []
    while len(arr) > 0:
        start = arr[0]
        prev.append(start)
        if start > limit:
            break
        brr = []
        for i in arr:
            if i % start != 0:
                brr.append(i)
        arr = brr

    prev.extend(arr)
    return prev


ARR = filterNotTheSame(N, ARR)
result = calculate(ARR)

print(len(result))

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>1005: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:
import math

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

def isDiv(x, y):
  if x % y == 0:
    return True
  else:
    return False

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

if A[0] == 1:
  print(N - A.count(1))
  exit()

for i in range(N):
  x = A[i]
  if isPrime(x):
    if i - 1 >= 0:
      y = A[i - 1]
      if isDiv(x, y):
        cnt -= 1
        continue
    if i + 1 < N:
      y = A[i + 1]
      if isDiv(x, y):
        cnt -= 1
        continue
          
  for j in range(N):
    if i == j:
      continue

    y = A[j]
    if x < y:
      break
    if isDiv(x, y):
      cnt -= 1
      break
print(cnt)

Submission status: Wrong Answer

Solution code:
import copy
n = int(input())
li = list(map(int,input().split()))
set1 = set()
ban = set()
for i in li:
    if i in set1:
        set1.remove(i)
        ban.add(i)
    if i not in set1 and i not in ban:
        if len(set1):
            for j in set1:
                if i % j == 0:
                    ban.add(i)
                else:
                    set1.add(i)
                    break
        else:
            set1.add(i)
set2 = copy.copy(set1)
cnt = 0
for i in (set1):
    set2.remove(i)
    flg = False
    for j in set2:
        if flg:
            break
        if i != j:
            if i % j == 0:
                flg = True
    if not flg:
        cnt += 1
        set2.add(i)
print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
count = 0
for i in range(n):
    x = list(range(n))
    x.remove(i)
    tmp = 0
    for j in x:
        print(a[i], a[j])
        if a[i] % a[j] != 0 or a[i] < a[j]:
            tmp += 1
        else:
            tmp = 0
    if tmp == n-1:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
import collections
N = int(input())
A = sorted([int(i) for i in input().split()])
maxA = A[-1]

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

C = collections.Counter(A)
cand = set(A)

ans = 0
for i in range(N):
    if C[A[i]] >= 2:
        continue

    if A[i] in cand:
        ans += 1
        cand -= set([A[i]*j for j in range(1, maxA//A[i]+2)])
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def main():
  n=int(input())
  a=list(map(int,input().split()))
  a.sort()
  a=tuple(a)
  ans=0
  if n==1:
    ans+=1
  elif a[0] != a[1]:
    ans+=1
  for i in range(1,n):
    flg=0
    for j in range(i):
      if a[i]%a[j]==0:
        flg=1
        break
      elif a[j]*2>a[i]:
        ans+=1
        flg=1
        break
    if flg==0 and j==i-1:
      ans+=1
  print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n = int(input())
a=list(map(int,input().split()))
a.sort()
ans=n
for val in a:
    if a.count(val)!=1:
        ans-=a.count(val)
b=list(set(a))
b.sort()
length = len(b)
closed = []
for i in range(length-1):
    for j in range(i+1,length):
        if j in closed:
            continue
        if b[j]%b[i]==0 and a.count(b[j])==1:
            ans-=1
            closed.append(j)
if ans<0:
    ans=0
print(ans)

Submission status: Wrong Answer

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

k = 0
b = 0
for l in range(n):
    if a[l] == 1:
        b = b + 1
        
if b == 0:
    for i in range(n):
        for j in range(n):
            if a[j] != 0:
                if i != j:            
                    if a[i] % a[j] == 0:
                        a[i] = 0
                        break
            if j == n-1:
                k = k + 1          
    print(k)
elif b == 1:
    print('1')
else:
    print('0')

Submission status: Wrong Answer

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

C=[1 for i in range(10**6+1)]
for i in range(N):
    if C[A[i]]==0:
        continue
    if C[A[i]]==-1:
        C[A[i]]=0
        continue
    C[A[i]]*=-1
    for j in range(2,10**6//A[i]-1):
        C[A[i]*j]=0
        

print(C.count(-1))

Submission status: Wrong Answer

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

res = []

sorted_p = sorted(pi)
max_p = sorted_p[-1]

if sorted_p[0] != max_p:
    for p in sorted_p:
        if p in res:
            res.append(p)
        else:
            flag = True
            for div in res:
                if div < (p/2)+1:
                    break
                elif p % div == 0:
                    flag = False
                    break
            if flag:
                res.append(p)

print(len(res))

Submission status: Wrong Answer

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

A.sort()

cnt = 0

for i in range(1, N+1):
    ai = A[i-1]
    for j in range(1, N+1):
        aj = A[j-1]
        if ai < aj and j != N:
            cnt += 1
            break
        if i == j and j != N:
            continue
        if ai % aj == 0 and j != N:
            break
        if j == N:
            cnt += 1
            break

print(cnt)

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
    if 0 < i and _q == a_list[i-1]:
        f_list[i] = False
        continue
    for j in range(0,i):
        if not 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)