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()
A_max = A[-1]
B = [1 for i in range(N)]
for i in range(N):
    if B[i] != 0:
        for j in range(i+1, N):
            if A[i] == A[j]:
                B[i] = 0
                B[j] = 0
            elif A[i] > (A[j])**(1/2):
                break
            elif A[j] % A[i] == 0:
                B[j] = 0
print(sum(B))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
A_max = A[-1]
B = [1 for i in range(N)]
for i in range(N):
    if A[i] > (A_max)**(1/2):
        break
    if B[i] != 0:
        for j in range(i+1, N):
            if A[i] == A[j]:
                B[i] = 0
                B[j] = 0
            elif A[j] % A[i] == 0:
                B[j] = 0
print(sum(B))

Submission status: Wrong Answer

Solution code:
inf =  1000005
def main():
  N = int(input())
  a = list(map(int, input().split()))
  a.sort()
  flag = [True]*inf
  num = [0]*inf 
  for i in range(N):
    num[a[i]] += 1
    if a[i]*2 < inf and flag[a[i]*2]:
      j = 2
      while (j*a[i] < inf):
        flag[j*a[i]] = False
        j += 1
  ans = 0
  for i in range(N):
    if flag[a[i]] and num[a[i]] == 1:
      ans += 1
  print(ans)
  
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
inf =  1000005
def main():
  N = int(input())
  a = list(map(int, input().split()))
  a.sort()
  flag = [True]*inf
  num = [0]*inf 
  for i in range(N):
    num[a[i]] += 1
    if flag[a[i]]:
      j = 2
      while (j*a[i] < inf):
        if not flag[j*a[i]]:
          break
        flag[j*a[i]] = False
        j += 1
  ans = 0
  for i in range(N):
    if flag[a[i]] and num[a[i]] == 1:
      ans += 1
  print(ans)
  
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
inf =  1000005
def main():
  N = int(input())
  a = list(map(int, input().split()))
  a.sort()
  flag = [True]*inf
  num = [0]*inf 
  for i in range(N):
    num[a[i]] += 1
    j = 2
    while (a[i]*j < inf):
      if not flag[a[i]*j]:
        break
      else:
        flag[a[i]*j] = False
        j+=1
  ans = 0
  for i in range(N):
    if flag[a[i]] and num[a[i]] == 1:
      ans += 1
  print(ans)
  
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
inf =  1000005
def main():
  N =  int(input())
  a = list(map(int, input().split()))
  a.sort()
  detect = [0] *inf
  for i in range(N):
    detect[a[i]] += 1
    if detect[a[i]] >= 2:
      continue
    j = 2
    while (a[i]*j < inf):
      if detect[a[i]*j] >= 2:
        break
      else:
        detect[a[i]*j] += 2
        j+=1
  ans = 0
  for i in range(N):
    if detect[a[i]] == 1:
      ans += 1
  print(ans)
  
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
n = int(input())
lst = [int(i) for i in input().split()]
lst.sort()
#print(lst)

if 1 in lst:
  count = 0
  for i in range(n):
    if lst[i] == 1:
      count += 1
    if count == 2:
      break
  if count == 1:
    print(1)
  else:
    print(0)
else:
  tf_lst = [1] * lst[n - 1]
  count = 0
  if n > 1:
    pre = 0
    for i in range(n):
      tf_lst[pre:lst[i] - 1] = [0] * (lst[i] - pre - 1)
      pre = lst[i]
      if tf_lst[lst[i] - 1] == 0:
        continue
      if i <= n - 2:
        if lst[i] == lst[i + 1]:
          tf_lst[lst[i] - 1] = 0
      if n > 100:
        if lst[i] >= lst[n - 1] ** 0.5:
          continue
      for j in range(lst[i] * 2, lst[n - 1] + 1, lst[i]):
        tf_lst[j - 1] = 0
    #print(tf_lst)
    for i in tf_lst:
      count += i
  else:
    count += 1
  print(count)

Submission status: Wrong Answer

Solution code:
inf =  2100000
def main():
  N =  int(input())
  a = list(map(int, input().split()))
  a.sort()
  detect = [0] *inf
  for i in range(N):
    detect[a[i]] += 1
    if detect[a[i]] >= 2:
      continue
    j = 2
    while (a[i]*j < inf):
      if detect[a[i]*j] >= 2:
        break
      else:
        detect[a[i]*j] += 2
        j+=1
  ans = 0
  for i in range(N):
    if detect[a[i]]== 1:
      ans += 1
  print(ans)
  
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
inf =  2100000
def main():
  N =  int(input())
  a = list(map(int, input().split()))
  a.sort()
  detect = [0] *inf
  for i in range(N):
    detect[a[i]] += 1
    if detect[a[i]] >= 2:
      continue
    j = 2
    while (a[i]*j < inf):
      if detect[a[i]*j] >= 2:
        break
      else:
        detect[a[i]*j] += 2
        j+=1
  ans = 0
  for i in range(N):
    if detect[a[i]]<2:
      ans += 1
  print(ans)
  
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
inf =  2100000
def main():
  N =  int(input())
  a = list(map(int, input().split()))
  a.sort()
  detect = [0] *inf
  for i in range(N):
    detect[a[i]] += 1
    j = 2
    while (a[i]*j < inf):
      if detect[a[i]*j] >= 2:
        break
      else:
        detect[a[i]*j] += 2
        j+=1
  ans = 0
  for i in range(N):
    if detect[a[i]]<2:
      ans += 1
  print(ans)
  
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
n = int(input())
lst = [int(i) for i in input().split()]
lst.sort()
#print(lst)

if lst[0] == 1:
  if n > 1:
    if lst[0] == lst[1]:
      print(0)
    else:
      print(1)
  else:
    print(1)
else:
  tf_lst = [1] * lst[n - 1]
  count = 0
  if n > 1:
    pre = 0
    for i in range(n):
      if tf_lst[lst[i] - 1] == 0:
        continue
      tf_lst[pre:lst[i] - 1] = [0] * (lst[i] - pre - 1)
      pre = lst[i]
      if i <= n - 2:
        if lst[i] == lst[i + 1]:
          tf_lst[lst[i] - 1] = 0
      for j in range(2, lst[n - 1] // lst[i] + 1):
        if lst[i] * j in lst:
          tf_lst[lst[i] * j - 1] = 0
    #print(tf_lst)
    for i in tf_lst:
      count += i
  else:
    count += 1
  print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
lst = [int(i) for i in input().split()]
lst.sort(reverse=True)
#print(lst)

if lst[n - 1] == 1:
  if n > 1:
    if lst[n - 1] == lst[n - 2]:
      print(0)
    else:
      print(1)
  else:
    print(1)
else:
  count = 0
  for i in range(n):
    if i < n - 1:
      flag = True
      if (lst[i] == lst[i + 1]) or (lst[i] == lst[i - 1] and i > 0):
        flag = False
      else:
        for j in range(i + 1, n):
          if lst[i] % lst[j] == 0:
            flag = False
            break
      if flag:
        count += 1
    if i == n - 1:
      if lst[i] != lst[i - 1]:
        count += 1
  print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
lst = [int(i) for i in input().split()]
lst.sort(reverse=True)
#print(lst)

count = 0
for i in range(n):
  if i < n - 1:
    flag = True
    for j in range(i + 1, n):
      if lst[i] % lst[j] == 0:
        flag = False
        break
    if flag:
      count += 1
  if i == n - 1:
    if lst[i] != lst[i - 1]:
      count += 1
print(count)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

m = np.zeros(max(a)+1, dtype=int)
cnt = 0

for i in a:
    if m[i] == 0:
        cnt +=1
    m[i::i] += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
N=int(input())
data=list(map(int,input().split()))
count=0
data.sort()
for i in range(N):
    for j in range(i):
        if int(data[i])%int(data[j]) == 0:
            break
    else:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.readline
import time
import math
import itertools as it
def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
start_time = time.perf_counter()
# ------------------------------

N = inp()
A = inpl()
A.sort()
dp = [False] * 1001001
nt = -1
ls = []
for i in A:
    if i != nt:
        dp[i] = True
    else:
        ls.append(i)
    nt = i

l = set(ls)

ans = 0
mx = A[N-1]
for i in A:
    if dp[i]:
        ans += 1
        j = i
        while j <= mx:
            dp[j] = False
            j += i
print(ans - len(l))

# -----------------------------
end_time = time.perf_counter()
print('time:', end_time-start_time, file=sys.stderr)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.readline
import time
import math
import itertools as it
def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
st = time.perf_counter()
# ------------------------------

N = inp()
A = inpl()
A.sort()
dp = [False] * 1001001
nt = -1
ls = set()
for i in A:
    if i != nt:
        dp[i] = True
    else:
        ls.add(i)
    nt = i

ans = 0
mx = A[N-1]
for i in A:
    if dp[i]:
        ans += 1
        j = i
        while j <= mx:
            dp[j] = False
            j += i
print(ans - len(ls))

# -----------------------------
ed = time.perf_counter()
print('time:', ed-st, file=sys.stderr)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.readline
import time
import math
import itertools as it
def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
st = time.perf_counter()
# ------------------------------

N = inp()
A = inpl()
A.sort()
dp = [False] * 1001001
nt = -1
for i in A:
    if i != nt:
        dp[i] = True
    else:
        dp[i] = False
    nt = i

ans = 0
mx = A[N-1]
for i in A:
    if dp[i]:
        ans += 1
        j = i
        while j <= mx + 100:
            dp[j] = False
            j += i
print(ans)

# -----------------------------
ed = time.perf_counter()
print('time:', ed-st, file=sys.stderr)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.readline
import time
import math
import itertools as it
def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
st = time.perf_counter()
# ------------------------------

N = inp()
A = inpl()
A.sort()
dp = [False] * 1001001
nt = -1
for i in A:
    if i != nt:
        dp[i] = True
    else:
        dp[i] = False
    nt = i

ans = 0
mx = A[N-1]
for i in A:
    if dp[i]:
        ans += 1
        j = i + i
        while j <= mx:
            dp[j] = False
            j += i
print(ans)

# -----------------------------
ed = time.perf_counter()
print('time:', ed-st, file=sys.stderr)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.readline
import time
import math
import itertools as it
def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
st = time.perf_counter()
# ------------------------------

N = inp()
A = inpl()
A.sort()
dp = [False] * 1001001
nt = -1
for i in A:
    if i != nt:
        dp[i] = True
        nt = i
    else:
        dp[i] = False
ans = 0
mx = A[N-1]
for i in A:
    if dp[i]:
        ans += 1
        j = i
        while j <= mx:
            dp[j] = False
            j += i
print(ans)

# -----------------------------
ed = time.perf_counter()
print('time:', ed-st, file=sys.stderr)

Submission status: Wrong Answer

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

A.sort()
A_max = max(A)
A = A
i = 0
while 2 * A[i] <= A_max:
    f = False
    j = i + 1
    if j >= len(A):
        break
    while True:
        if A[j] % A[i] == 0:
            if A[j] == A[i]:
                f = True
            A.pop(j)
        else:
            j += 1
        if j >= len(A):
            break
    if f:
        A.pop(i)
        i -= 0
    i += 1
    if i >= len(A):
        break

ans = len(A)
print(ans)

Submission status: Wrong Answer

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

A.sort(reverse=True)

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

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
B = []
cnt = 0
for i in range(N):
    if A[i] in B:
        if A[i] == A[i - 1] and A[i] != A[i - 2]:
            cnt += 1
        cnt += 1
    else:
        for k in range(A[N - 1] // A[i] + 2):
            b = A[i] * k
            B.append(b)
print(N - cnt)

Submission status: Wrong Answer

Solution code:

def solution():
    _ = input()
    user_input = input()
    num_list = [int(x) for x in user_input.split()]

    iter = max(num_list) // min(num_list) 

    h = {}
    for num in num_list:
        h[num] = 0
    
    multiplier = 1
    for _ in range(iter):
        for num in h:
            if num * multiplier in h:
                h[num * multiplier] += 1
        multiplier += 1
    
    result = 0
    for _, val in h.items():
        if val == 1:
            result += 1
    print(result)

solution()

Submission status: Wrong Answer

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

A = sorted(A, key=lambda x: -x)
all = [True] * N

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

ans = 0
for i in all:
    if i:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
num = [0]*(10**6+1)
for x in a:
    if num[x] != 0:
        num[x] = 2
        continue
    for i in range(x, 10**6//x+1, x):
        num[i] += 1
ans = 0
for x in a:
    if num[x] == 1:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import collections
n = int(input())
a = list(map(int, input().split()))
Ca = collections.Counter(a)
# print(Ca.keys())
# print(Ca[2])
m = len(Ca)
if m == 1:
    print(0)
    exit()
# print(Ca, m)
num = [0]*(10**6 + 1)
for i in Ca.keys():
    for j in range(1, 10**6//i + 1):
        num[i*j] += 1
# for i in range(n):
#     for j in range(1, 10**6//a[i]+1):
#         num[a[i]*j] += 1

ans = 0
for i in Ca.keys():
    if num[i] < 2:
        ans += Ca[i]

# print(num[:30])
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
n = int(input())
a = list(map(int, input().split()))
Ca = collections.Counter(a)
# print(Ca.keys())
# print(Ca[2])
m = len(Ca)
if m == 1:
    print(0)
    exit()
# print(Ca, m)
num = [0]*(10**6 + 1)
for i in Ca.keys():
    for j in range(1, 10**6//i + 1):
        num[i*j] += 1
# for i in range(n):
#     for j in range(1, 10**6//a[i]+1):
#         num[a[i]*j] += 1

ans = 0
for i in Ca.keys():
    if num[i] < 2:
        ans += Ca[i]

print(num[:30])
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
n = int(input())
a = list(map(int, input().split()))
Ca = collections.Counter(a)
# print(Ca.keys())
# print(Ca[2])
m = len(Ca)
# print(Ca, m)
num = [0]*(10**6 + 1)
for i in Ca.keys():
    for j in range(1, 10**6//i + 1):
        num[i*j] += 1
# for i in range(n):
#     for j in range(1, 10**6//a[i]+1):
#         num[a[i]*j] += 1

ans = 0
for i in Ca.keys():
    if num[i] < 2:
        ans += Ca[i]

# print(num[:30])
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
re_a = list(set(a))
m = len(re_a)
num = [0]*(10**6 + 1)
for i in range(m):
    for j in range(1, 10**6//re_a[i]+1):
        num[re_a[i]*j] += 1

ans = 0
for i in range(m):
    if num[re_a[i]] < 2:
        ans += 1

# print(num[:30])
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
num = [0]*(10**6 + 1)
for i in range(n):
    for j in range(1, 10**6//a[i]+1):
        num[a[i]*j] += 1

ans = 0
for i in range(n):
    if num[a[i]] < 2:
        ans += 1

print(num[:30])
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
Atemp = [int(i) for i in input().split()]
A = [i for i in list(set(Atemp)) if Atemp.count(i) == 1]

if len(A) > 0:
    count = [0] * (max(A)+1)
    ans = 0
    for i in range(len(A)):
        a = A[i]
        
        if count[a] == 0:
            ans += 1

            for j in range(a, max(A)+1, a):
                count[j] += 1

    print(ans)

else:
    print(0)

Submission status: Wrong Answer

Solution code:
# 問題文誤読して30分経過してた
# ソートしたとき「自分より小さいいずれの値も自分の素因数に含まれない」
# これはなんか実装しにくいので、A<10^6を利用して、調和級数的なノリでやってみる
n = int(input())
a = sorted(list(set(list(map(int, input().split())))))

if len(a) == 1 and n > 1:
    # この場合のやつなんかもっといい方法ないんか
    print(0)
    exit()

t = {}
for av in a:
    if av not in t:
        t[av] = True
limit = a[-1]

d = [True] * (limit + 1)
for av in a:
    for i in range(av * 2, limit + 1, av):
        d[i] = False

ans = 0
for av in a:
    if d[av]:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
# 問題文誤読して30分経過してた
# ソートしたとき「自分より小さいいずれの値も自分の素因数に含まれない」
# これはなんか実装しにくいので、A<10^6を利用して、調和級数的なノリでやってみる
n = int(input())
a = sorted(list(set(list(map(int, input().split())))))

if len(a) == 1 and n > 1:
    # この場合のやつなんかもっといい方法ないんか
    print(0)
    exit()

t = {}
for av in a:
    if av not in t:
        t[av] = True
limit = 10**6 + 1

d = [True] * limit
for av in a:
    for i in range(av * 2, limit, av):
        d[i] = False

ans = 0
for i in range(1, limit):
    ans += 1 if i in t and d[i] else 0
print(ans)

Submission status: Wrong Answer

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

xs = [0] * (max(a) + 1)

for v in a:
    if xs[v] == 0:
        for j in range(v, len(xs), v):
            xs[j] += 1
    else:
        xs[v] += 1
print(len(list(filter(lambda v: xs[v] == 1, a))))

Submission status: Wrong Answer

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

cnt =0
for i in A:
    j_list = []
    for t in A:
        if i == t:
            continue
        else:
            j = i % t
            j_list.append(j)
    if 0 not in j_list:
        cnt += 1

print(cnt)

Submission status: Wrong Answer

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

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

B = [0] * (max(A)+1)
C = []
for i in range(n):
    B[A[i]] += 1
for i in range(len(B)):
    if B[i] == 1:
        C.append(i)

C.sort()
D = [0] * (10**6+5)

ans = 0
for i in range(len(C)):
    # print(C[i])
    if D[C[i]] == 0:
        ans += 1
    j = C[i]
    while j < len(D):
        D[j] = 1
        j += C[i]
print(ans)

Submission status: Wrong Answer

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

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

print(ans)

Submission status: Wrong Answer

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

m=max(A)

X=[True]*(m+1)

A.sort()

for i in range(n):
    for j in range(A[i]*2,m+1,A[i]):
        X[j]=False
ans=0
for i in range(n):
    if X[A[i]]==True:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort()
TF={}
for i in range(N):
    if i>0 and A[i-1]==A[i]:
        TF[A[i]]=False
    else:
        TF[A[i]]=True
for i in range(N):
    if TF[A[i]]==True:
        m=A[N-1]//A[i]
        for j in range(2,m+1):
            s=A[i]*j
            if s in TF:
                TF[s]=False
print(len([1 for a in A if TF[a]==True]))

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
M=10**6
A.sort()
TF={a:True for a in A}
for a in TF:
    if A.count(a)>1:
        TF[a]=False
for i in range(N):
    if TF[A[i]]==True:
        m=M//A[i]
        for j in range(2,m+1):
            s=A[i]*j
            if s in TF:
                TF[s]=False
print(len([1 for a in A if TF[a]==True]))

Submission status: Wrong Answer

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

a.sort()
pn = [1]*n

for i in range(n):
    if pn[i] == 1:
        for j in range(i+1, n):
            if a[j] % a[i] == 0:
                pn[j] = 0
    
print(sum(pn))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D_fix_4
# CreatedDate:  2020-07-20 00:18:24 +0900
# LastModified: 2020-07-20 00:40:55 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd


def main():
    n = int(input())
    A = sorted(map(int, input().split()))
    ans = [1 if i in A else 0 for i in range(A[-1]+1)]
    for i, a in enumerate(A):
        if ans[a] == 0:
            continue
        for s in range(a, A[-1]+1, a):
            ans[s] = 0
        ans[a] = 1

    print(sum(ans))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

print(a)

nall = list(range(n))

cnt = n
for i in nall:
	print(f'trial {i}')
	if a.count(a[i]) > 1:
		print("found")
		cnt -= 1
		continue
	for j in nall:
		print(f'trial {i},{j}')
		if i <= j:
			print("break")
			break
		if a[i] % a[j] == 0:
			print("found")
			cnt -= 1
			break

print(cnt)

Submission status: Wrong Answer

Solution code:
import numpy as np
nn=int(input())
aa=list(map(int,input().split()))
a=list(set(aa))
n=len(a)
if n==1:
    print(0)
a1=np.array([a])
a2=np.array([[a[i] for j in range(n)] for i in range(n)])
r=a2 % a1
arr=np.array(r==0)
ans=list(np.sum(arr,axis=1))
print(ans.count(1))

Submission status: Wrong Answer

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

dp = [-1] * (A[-1]+1)
ans = 0
for i in range(N):
    a = A[i]
    if dp[a] != -1:
        continue

    if A.count(a) == 1:
        ans += 1
        for j in range(a+a, A[-1]+1, a):
            dp[j] = 0
    else:
        dp[a] = 0

print(ans)

Submission status: Wrong Answer

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

N = int(input())
A = sorted([int(i) for i in input().split()])

dp = [-1] * (A[-1]+1)
ans = 0
for i in range(N):
    a = A[i]
    if dp[a] != -1:
        continue

    if A.count(a) == 1:
        ans += 1
        for j in range(a+a, A[-1]+1, a):
            dp[j] = 0
    else:
        dp[a] = 0

print(ans)

Submission status: Wrong Answer

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

dp = [-1] * (A[-1]+1)
ans = 0
for i in range(N):
    a = A[i]
    if dp[a] != -1:
        continue

    if dp[a] == -1 and A.count(a) == 1:
        ans += 1
        for j in range(a+a, A[-1]+1, a):
            dp[j] = 0
    else:
        dp[a] = 0

print(ans)

Submission status: Wrong Answer

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

dp = [-1] * (A[-1]+1)
ans = 0
for i in range(N):
    a = A[i]
    if dp[a] == -1 and A.count(a) == 1:
        ans += 1
        for j in range(a+a, A[-1]+1, a):
            dp[j] = 0
    else:
        dp[a] = 0

print(ans)

Submission status: Wrong Answer

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

dp = [-1] * (A[-1]+1)

for i in range(N):
    a = A[i]
    if dp[a] == -1 and A.count(a) == 1:
        dp[a] = 1
        for j in range(a+a, A[-1]+1, a):
            dp[j] = 0
    else:
        dp[a] = 0

print(dp.count(1))

Submission status: Wrong Answer

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

dp = [True] * max(A)

for i in range(1, max(A)+1):
    if A.count(i) == 1 and dp[i-1] == True:
        for j in range(i+i, max(A)+1, i):
            dp[j-1] = False
    else:
        dp[i-1] = False

print(dp.count(True))

Submission status: Wrong Answer

Solution code:
import numpy as np
import collections

n = int(input())
aa = np.array(list(map(int,input().split())))
c = collections.Counter(aa)
a=np.unique(aa)
amax=max(a)+1
ah=[0]*amax

for i in a:
    if c[i]>=2 and ah[i]==0:
        ah[i]=2
        continue
    for j in range(i,amax,i):
        ah[j]+=1

an=0
for i in a:
    if ah[i]==1:
        an+=1
print(an)

Submission status: Wrong Answer

Solution code:
def solution():
    length = int(input())
    user_input = input()
    num_list = [int(x) for x in user_input.split()]
    result = 0
    for i in range(length):
        success = True 
        for j in range(length):
            if i == j:
                continue
            if num_list[i] > num_list[j] and num_list[i] % num_list[j] == 0:
                success = False 
                break
        if success:
            result += 1
    
    print(result)

solution()

Submission status: Wrong Answer

Solution code:
import sys
import math
input=sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))

ans=0
a=sorted(a)

if n==1:
  print(1)
  
else:
  if a[0]==a[1]:
    ans+=1
  for x in range(1,n):
    b=a[x]
    c=math.sqrt(b)
    ch=0
    for u in range(x):
      if a[u]>c:
        continue
      if not b%a[u]==0:
        ch+=1
        continue
        
    if ch==0:
      ans+=1
      
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
input=sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))

ans=1
a=sorted(a)

if n==1:
  print(ans)
  
else:
  for x in range(1,n):
    b=a[x]
    c=math.sqrt(b)
    ch=0
    for u in range(x):
      if a[u]>c:
        continue
      if not b%a[u]==0:
        ch+=1
        continue
        
    if ch==0:
      ans+=1
      
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
input=sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))

ans=1
a=sorted(a)

if n==1:
  print(ans)
  
else:
  for x in range(1,n):
    b=a[x]
    c=math.sqrt(b)
    ch=0
    for u in range(x):
      if a[u]>c:
        continue
      if not b%a[u]==0:
        ch+=1
        continue
        
    if ch==0:
      ans+=1
      
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
data = [int(i) for i in input().split(" ")]
res = 0

for i in range(N):
    for j in range(N):
        if data[i] != data[j] :
            if data[j] % data[i] == 0:
                res = res + 1

print(res)

Submission status: Wrong Answer

Solution code:
N = int(input())
data = [int(i) for i in input().split(" ")]
res = 0

for i in range(N):
    for j in range(N):
        if i != j :
            if data[j] % data[i] == 0:
                res = res + 1

print(res)

Submission status: Wrong Answer

Solution code:
n=int(input())
b=list(map(int,input().split()))
ans=0
w=max(b)
a=[0]*(w+1)
for i in b:
  x=i
  while x<w:
    a[x]+=1
    x+=i
for i in b:
  if a[i]==1:
    ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import collections

n = int(input())
aa = np.array(list(map(int,input().split())))
c = collections.Counter(aa)
a=np.unique(aa)
amax=max(a)+1
ah=[0]*amax

for i in a:
    if c[i]>=2:
        ah[i]=2
        continue
    for j in range(i,amax,i):
        ah[j]+=1

an=0
for i in a:
    if ah[i]==1:
        an+=1
print(an)

Submission status: Wrong Answer

Solution code:
import numpy as np
import collections

n = int(input())
aa = np.array(list(map(int,input().split())))
c = collections.Counter(aa)
a=np.unique(aa)
amax=max(a)+1
ah=[0]*amax

for i in a:
    if c[i]>=2:
        if len(a)!=1:
            ah[i]+=1
        continue
    for j in range(i,amax,i):
        ah[j]+=1

an=0
for i in a:
    if ah[i]==1:
        an+=1
print(an)

Submission status: Wrong Answer

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))

# ===CODE===

eps = 10 ** (-9)


def main():
    n = ni()
    a = na()

    seta = set(a)
    cnta = collections.Counter(a)
    lista = list(seta)
    lista.sort()

    table = [True for _ in range(10 ** 6 + 1)]
    ans = 0

    for ai in lista:
        if cnta[ai] == 1 and table[ai]:
            ans += 1
            for i in range(ai, 10 ** 6 + 1, ai):
                table[i] = False

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))

# ===CODE===

eps = 10 ** (-9)


def main():
    n = ni()
    a = na()

    seta = set(a)
    cnta = collections.Counter(a)

    # 約数を列挙　n=10^12までいける
    def make_divisors(n):

        if 1 in seta:
            return True
        if cnta[n] > 1:
            return True

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

        return False

    ans = 0
    for ai in list(seta):
        if not make_divisors(ai):
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))

# ===CODE===

eps = 10 ** (-9)


def main():
    n = ni()
    a = na()

    seta = set(a)
    cnta = collections.Counter(a)

    # 約数を列挙　n=10^12までいける
    def make_divisors(n):
        divisors = []

        if 1 in seta:
            return True
        if cnta[n] > 1:
            return True

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

        return False

    ans = 0
    for ai in seta:
        if not make_divisors(ai):
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()