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:
#!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase
from typing import List
from collections import Counter


def get_no_dupes(arr: List[int]) -> List[int]:
    cntr = Counter(arr)
    ret = []
    for elem in cntr:
        if cntr[elem] == 1:
            ret.append(elem)
    return ret


def main() -> None:
    input()

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

    busted = [False] * (10 ** 6 + 10)

    seen = set()
    max_limit = 10 ** 6
    for num in arr:
        if num in seen:
            continue
        for i in range(2 * num, max_limit, num):
            busted[i] = True
        seen.add(num)

    arr = get_no_dupes(arr)
    cnt = 0
    for num in arr:
        if not busted[num]:
            cnt += 1

    print(cnt)


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self, **kwargs):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

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


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase
from typing import List
from collections import Counter


class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        left = 0
        ans, prod = 0, 1
        lenght = 0
        for num in nums:
            if prod * num >= k:
                prod *= num
                lenght += 1
                while prod >= k:
                    prod //= nums[left]
                    left += 1
                    lenght -= 1
                ans += lenght
            else:
                prod *= num
                lenght += 1
                ans += lenght
            # print(ans)

        return ans


def get_no_dupes() -> List[int]:
    arr = list(map(int, input().split()))
    cntr = Counter(arr)
    ret = []
    for elem in cntr:
        if cntr[elem] == 1:
            ret.append(elem)
    return ret


def main() -> None:
    input()

    arr = get_no_dupes()

    busted = [False] * (10 ** 6 + 10)

    max_limit = 10 ** 6
    for num in arr:
        for i in range(2 * num, max_limit, num):
            busted[i] = True

    cnt = 0
    for num in arr:
        if not busted[num]:
            cnt += 1

    print(cnt)


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self, **kwargs):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

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


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy,bisect
#from operator import itemgetter
#from heapq import heappush, heappop
#import numpy as np
#import sympy
#from scipy.sparse.csgraph import breadth_first_order, depth_first_order, shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
#from scipy.sparse import csr_matrix
#from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
import sys

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
nf = lambda: float(ns())
na = lambda: list(map(int, stdin.readline().split()))
nb = lambda: list(map(float, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ni()
A = na()
A.sort()
li = [0] * (10 ** 6 + 1)
ans = 0
for i in range(N):
    now = A[i]
    if li[now] == 0:
        ans += 1
    for j in range(now, 10 ** 6 + 1, now):
        li[j] = 1
print(ans)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy,bisect
#from operator import itemgetter
#from heapq import heappush, heappop
import numpy as np
#import sympy
#from scipy.sparse.csgraph import breadth_first_order, depth_first_order, shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
#from scipy.sparse import csr_matrix
#from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
import sys

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
nf = lambda: float(ns())
na = lambda: list(map(int, stdin.readline().split()))
nb = lambda: list(map(float, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

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 = ni()
A = na()
A.sort()
s = set()
ans = 0
for i in range(len(A)):
    ai = A[i]
    li = make_divisors(ai)
    flag = True
    for pn in li:
        if pn in s:
            flag = False
            break
    if flag:
        ans += 1
    s.add(ai)
if A.count(A[0]) == N:
    print(0)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys,math
from collections import defaultdict,deque,Counter
import itertools
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

def make_divisors(n):
    divisors = []
    for i in range(1, int(math.sqrt(n))+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors
n = inp()
a = inpl()
a.sort()
c = Counter(a)
s = set()
res = 0
for x in a:
    if c[x] > 1: continue
    for y in make_divisors(x):
        if y in s:
            break
    else:
        res += 1
    s.add(x)
print(res)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = sorted(list(map(int,input().split())))
if N==1:
    print(1)
elif A[0]==A[-1]:
    print(0)
elif A[0]==1 and A[1]==1:
    print(0)
elif A[0]==1 and A[1]>1:
    print(1)
else:
    P = [0 for _ in range(10**6+1)]
    for i in range(N):
        P[A[i]] = 1
    for i in range(N):
        for j in range(2*A[i],10**6+1,A[i]):
            P[j] = 0
    print(sum(P))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = sorted(list(map(int,input().split())))
C = {}
for i in range(N):
    a = A[i]
    if a not in C:
        C[a] = 0
    C[a] += 1
if len(C)==1:
    print(0)
else:
    if A[0]==1 and A[1]==1:
        print(0)
    elif A[0]==1 and A[1]>1:
        print(1)
    else:
        P = [0 for _ in range(10**6+1)]
        for i in range(N):
            P[A[i]] = 1
        for i in range(N):
            for j in range(2*A[i],10**6+1,A[i]):
                P[j] = 0
        print(sum(P))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = sorted(list(map(int,input().split())))
if N==1:
    print(1)
else:
    if A[0]==1 and A[1]==1:
        print(0)
    elif A[0]==1 and A[1]>1:
        print(1)
    else:
        P = [0 for _ in range(10**6+1)]
        for i in range(N):
            P[A[i]] = 1
        for i in range(N):
            for j in range(2*A[i],10**6+1,A[i]):
                P[j] = 0
        print(sum(P))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = sorted(list(map(int,input().split())))
P = [0 for _ in range(10**6+1)]
for i in range(N):
    P[A[i]] = 1
for i in range(N):
    for j in range(2*A[i],10**6+1,A[i]):
        P[j] = 0
print(sum(P))

Submission status: Wrong Answer

Solution code:
def prime_number(n):
    l = []
    for i in range(2, n+1):
        count = 0
        for j in range(2, i):
            if i % j == 0:
                count += 1
                break
        if count == 0:
            l.append(i)
    return l


n = int(input())
al = list(map(int, input().split()))
als = sorted(list(set(al)))

prime = prime_number(als[-1])
min_eve, min_odd = 1001001001, 1001001001
cnt = 0
num = []
if len(als) == 1:
    print(0)
else:
    for a in als:
        if a in prime:
            cnt += 1
            num.append(a)
        elif a%2 != 0 and a < min_odd:
            min_odd = a
        elif a%2 == 0 and a < min_eve:
            min_eve = a
    if min_eve != 1001001001:
        cnt += 1
    if min_odd != 1001001001:
        cnt += 1
    print(cnt)

    # print(num, min_eve, min_odd, prime, als)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [-1] + list(map(int, input().split())) + [10**7]
a.sort()

ans = 0
furui = [True]*(10**6+1)
for i in range(1,n+1):
    if a[i-1] != a[i] and a[i] != a[i+1] and furui[a[i]]:
        ans += 1
        for j in range(a[i],10**6+1,a[i]):
            furui[j] = False

print(ans)

Submission status: Wrong Answer

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

B = [0]*(1000001)

for i in range (0, N):
	B[A[i]]+=1

import math
count = 0
for i in range (1, 500002):
	if B[i] == 1:
		count+=1
		for j in range (1, math.floor(1000001/i)):
			B[j*i] = 0
  
print(count)

Submission status: Wrong Answer

Solution code:
# import itertools
import math
from functools import reduce
# import sys
# sys.setrecursionlimit(500*500)
# import numpy as np
# import heapq
# from collections import deque

N = int(input())
# S = input()
# n, *a = map(int, open(0))
# N, M = map(int, input().split())
A = list(map(int, input().split()))
# B = list(map(int, input().split()))
# tree = [[] for _ in range(N + 1)]
# B_C = [list(map(int,input().split())) for _ in range(M)]
# S = input()

# B_C = sorted(B_C, reverse=True, key=lambda x:x[1])
# all_cases = list(itertools.permutations(P))
# a = list(itertools.combinations_with_replacement(range(1, M + 1), N))
# itertools.product((0,1), repeat=n)

# A = np.array(A)
# cum_A = np.cumsum(A)
# cum_A = np.insert(cum_A, 0, 0)

# def dfs(tree, s):
#     for l in tree[s]:
#         if depth[l[0]] == -1:
#             depth[l[0]] = depth[s] + l[1]
#             dfs(tree, l[0])
# dfs(tree, 1)

# def factorization(n):
#     arr = []
#     temp = n
#     for i in range(2, int(-(-n**0.5//1))+1):
#         if temp%i==0:
#             cnt=0
#             while temp%i==0:
#                 cnt+=1
#                 temp //= i
#             arr.append([i, cnt])
#     if temp!=1:
#         arr.append([temp, 1])
#     if arr==[]:
#         arr.append([n, 1])
#     return arr

# def gcd_list(numbers):
#     return reduce(math.gcd, numbers)

# if gcd_list(A) > 1:
#     print("not coprime")
#     exit()

# 高速素因数分解準備
MAXN = 10**6+10
sieve = [i for i in range(MAXN+1)]
p = 2
while p*p <= MAXN:
    if sieve[p] == p:
        for q in range(2*p, MAXN+1, p):
            if sieve[q] == q:
                sieve[q] = p
    p += 1


B = []
for a in A:
    tmp = set()
    while a > 1:
        tmp.add(sieve[a])
        a //= sieve[a]
    B.append([len(tmp), tmp])
B = sorted(B, reverse=False, key=lambda x:x[0])

ans = 0
st = set()    
for l in B:
    for i in l[1]:
        if i in st:
            break
    else:
        ans += 1
        for i in l[1]:
            st.add(i)
print(ans)

Submission status: Wrong Answer

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


def solve2(N, A):
    A = sorted(A)
    amax = A[-1]
    dp = [True] * (amax + 1)

    for i in range(len(dp)):
        x = i + 1
        if x in A:
            cnt = 2
            y = cnt * x
            while y <= amax:
                dp[y] = False
                cnt += 1
                y = cnt * x

    ansval = [x for x in A if dp[x]]

    # print(ansval)
    ans = len(ansval)

    return ans


def solve1(N, A):
    ans = 0
    for i in range(N):
        is_ans = True
        for j in range(N):
            if i != j:
                if A[i] % A[j] == 0:
                    is_ans = False
                    break

        if is_ans:
            ans += 1

    return ans


print(solve2(N, A))

Submission status: Wrong Answer

Solution code:
from collections import Counter as c
n = int(input())
a = list(map(int,input().split()))
a.sort()

count, a_max = 0, a[-1]
li = [-1] * a_max

for i in a:
  if li[i-1] == -1:
    count += 1
    li[i-1] = 0
  li[i-1] += 1
  j = 2
  while i * j <= a_max:
    li[i*j-1] = 0
    j += 1

li.sort(reverse=True)
for i in li:
  if -1 <= i <= 1: break
  count -= 1

print(count)

Submission status: Wrong Answer

Solution code:
from collections import Counter as c
n = int(input())
a = list(map(int,input().split()))
a.sort()

count, a_max = 0, a[-1]
li = [-1] * (a_max+1)

for i in a:
  if li[i] == -1:
    count += 1
    li[i] = 0
  li[i] += 1
  j = 2
  while i * j <= a_max:
    li[i*j] = 0
    j += 1

li.sort(reverse=True)
for i in li:
  if i == 1 or i == 0 or i == -1: break
  count -= 1

print(count)

Submission status: Wrong Answer

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

for i in range(n):
  ai = a[i]
  if i == 0:
    if n == 1 or (n >= 2 and a[0] != a[1]): count += 1
    continue
  for j in range(i):
    if ai % a[j] == 0: break
  else: count += 1

print(count)

Submission status: Wrong Answer

Solution code:
import math

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

def factrization(num):
    fac_set = set()
    for i in range(1, math.floor(math.sqrt(num))+1):
        if num % i == 0:
            fac_set |= {i, num//i}
    return fac_set

B = set(A)
for item in A:
    B.discard(item)
    if not (factrization(item) & B):
        if B:
            count += 1
    B.add(item)

print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
m = max(a)
dp = [True]*(m+1)
b = list(sorted(a))
for i in b:
    x = i + i
    while x <= m:
        dp[x] = False
        x += i
ans = 0
x = 0
l = []
for i in a:
    if dp[i]:
        if i in l:
            if x <= 1:
                x = 0
            ans = max(ans,x)
            x = 1
            l.clear()
            l.append(i)
        else:
            x += 1
            l.append(i)
    else:
        ans = max(ans,x)
        l.clear()
        x = 0
if x <= 1:
    x = 0
print(max(ans,x))

Submission status: Wrong Answer

Solution code:
n = int(input())
A = sorted(list(map(int, input().split())))
from collections import Counter
c = Counter(A)

MAX = 10 ** 6 + 1000
cnt = [0] * MAX
dp = [True] * MAX

for k, v in c.items():
    print(k, v)
    if dp[k] == False: continue
    if v > 1: dp[k] = False
    for x in range(k + k, MAX, k):
        dp[x] = False

res = 0
for x in range(n):
    if dp[A[x]]: res += 1
print(res)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

visited = np.zeros(10**6+1, dtype=int)
ans = 0
s = set()
for i in range(n):
    j = 1
    flg = True
    if a[i] in s:
        flg = False
    elif visited[a[i]] and a[i] == a[i-1] >= 2:
        flg = False
        ans -= 1
        s.add(a[i])
    elif visited[a[i]]:
        flg = False
    if flg:
        ans += 1   
    # print(a[i], flg)
    visited[a[i]::a[i]] += 1
print(ans)

Submission status: Wrong Answer

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

X = [True]*(10**6+1)
for a in A:
  for i in range(a*2,len(X),a):
    X[i] = False

ans = 0
for a in A:
  if X[a]:
    ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
 
M = 10**6 + 1
 
cnt = [0] * M
 
for a in A:
    if cnt[a] != 0:
        continue
    for b in range(a, M, a):
        cnt[b] += 1
 
ans = 0
for a in A:
    if cnt[a] == 1:ans += 1
 
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import math
 
def INT(): return int(input())
def MAPINT(): return map(int, input().split())
def LMAPINT(): return list(map(int, input().split()))
def STR(): return input()
def MAPSTR(): return map(str, input().split())
def LMAPSTR(): return list(map(str, input().split()))
 
f_inf = float('inf')
 
n = INT()
a = sorted(LMAPINT())

ans = [True] * n
for i in range(int(math.sqrt(n))+1000):
  try:
    tmp = ans[i]
  except Exception:
    break
  if ans[i] is False:
    continue
  for j in range(i+1, n):
    if a[j] % a[i] == 0:
      ans[j] = False
    if a[j] == a[i]:
      ans[i], ans[j] = False, False
 
print(ans.count(True))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import math
 
def INT(): return int(input())
def MAPINT(): return map(int, input().split())
def LMAPINT(): return list(map(int, input().split()))
def STR(): return input()
def MAPSTR(): return map(str, input().split())
def LMAPSTR(): return list(map(str, input().split()))
 
f_inf = float('inf')
 
n = INT()
a = sorted(LMAPINT())

ans = [True] * n
for i in range(int(math.sqrt(n))):
  if ans[i] is False:
    continue
  for j in range(i+1, n):
    if a[j] % a[i] == 0:
      ans[j] = False
    if a[j] == a[i]:
      ans[i], ans[j] = False, False
 
print(ans.count(True))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import math
 
def INT(): return int(input())
def MAPINT(): return map(int, input().split())
def LMAPINT(): return list(map(int, input().split()))
def STR(): return input()
def MAPSTR(): return map(str, input().split())
def LMAPSTR(): return list(map(str, input().split()))
 
f_inf = float('inf')
 
n = INT()
a = sorted(set(LMAPINT()))

if a[0] == a[len(a)-1]:
  print(0)
  exit()
 
ans = [True] * len(a)
for i in range(int(math.sqrt(len(a)))+1):
  if ans[i] is False:
    continue
  for j in range(i+1, len(a)):
    if a[j] % a[i] == 0:
      ans[j] = False
 
print(ans.count(True))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import math
 
def INT(): return int(input())
def MAPINT(): return map(int, input().split())
def LMAPINT(): return list(map(int, input().split()))
def STR(): return input()
def MAPSTR(): return map(str, input().split())
def LMAPSTR(): return list(map(str, input().split()))
 
f_inf = float('inf')
 
n = INT()
a = sorted(LMAPINT())
 
if a[0] == a[n-1]:
  print(0)
  exit()
 
ans = [True] * n
for i in range(int(math.sqrt(n))+1):
  if ans[i] is False:
    continue
  for j in range(i+1, n):
    if a[j] % a[i] == 0:
      ans[j] = False
 
print(ans.count(True))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import math
 
def INT(): return int(input())
def MAPINT(): return map(int, input().split())
def LMAPINT(): return list(map(int, input().split()))
def STR(): return input()
def MAPSTR(): return map(str, input().split())
def LMAPSTR(): return list(map(str, input().split()))
 
f_inf = float('inf')
 
n = INT()
a = sorted(LMAPINT())
 
if a[0] == a[n-1]:
  print(0)
  exit()
 
ans = [True] * n
for i in range(int(math.sqrt(n))):

  for j in range(i+1, n):
    if a[j] % a[i] == 0:
      ans[j] = False
 
print(ans.count(True))

Submission status: Wrong Answer

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

def INT(): return int(input())
def MAPINT(): return map(int, input().split())
def LMAPINT(): return list(map(int, input().split()))
def STR(): return input()
def MAPSTR(): return map(str, input().split())
def LMAPSTR(): return list(map(str, input().split()))

f_inf = float('inf')

n = INT()
a = sorted(LMAPINT())

if a[0] == a[n-1]:
  print(0)
  exit()

ans = [True] * n
for i in range(int(math.sqrt(n))):
  if ans[i] is False:
    continue
  for j in range(i+1, n):
    if a[j] % a[i] == 0:
      ans[j] = False

print(ans.count(True))

Submission status: Wrong Answer

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

def INT(): return int(input())
def MAPINT(): return map(int, input().split())
def LMAPINT(): return list(map(int, input().split()))
def STR(): return input()
def MAPSTR(): return map(str, input().split())
def LMAPSTR(): return list(map(str, input().split()))

f_inf = float('inf')

n = INT()
a = sorted(LMAPINT())

if a[0] == a[n-1]:
  print(0)
  exit()

ans = [True] * n
for i, x in enumerate(a):
  if ans[i] is False:
    continue
  for j in range(i+1, n):
    if a[j] % x == 0:
      ans[j] = False

print(ans.count(True))

Submission status: Wrong Answer

Solution code:
import copy

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

    elem_count = {}
    for a in A:
        if a in elem_count:
            elem_count[a] += 1
        else:
            elem_count[a] = 1

    uniq_A = []
    for k, v in elem_count.items():
        if v == 1:
            uniq_A.append(k)
    
    if len(uniq_A) == 0:
        print(0)
        return

    uniq_A.sort()
    uniq_A_copy = copy.copy(uniq_A)

    for i, a in enumerate(uniq_A):
        for j, b in enumerate(uniq_A_copy):
            if a != b and b % a == 0:
                uniq_A_copy.pop(j)

    print(len(uniq_A_copy))

main()

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N=I()
    A=sorted(LI())

    MAX=10**6
    divible=[False]*(MAX+1)

    ans = 0
    for i,a in enumerate(A):
        if(i+1<N and A[i+1]==a or divible[a]):
            pass
        else:
            ans += 1
            
        b = a
        while(b<=MAX): #エラトステネスの篩と同じ計算量解析.
            if(divible[b]):
                break
            else:
                divible[b] = True
                b += a
    print(ans)
        
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
A=sorted(A)
ans=0
while A:
    notdivisible=[]
    flag=True
    for i in range(len(A)-1):
        if A[i+1]%A[0]!=0:
            notdivisible.append(A[i+1])
        elif A[i+1]==A[0]:
            flag=False
    if flag:
        ans+=1
    A=notdivisible
    print(A)
print(ans)

Submission status: Wrong Answer

Solution code:
from math import gcd

if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))
    
    A.sort(reverse=True)
    print(A)
    all = 1
    for a in A:
        all *= a
    cnt = 0
    for a in A:
        all //= a
        g = gcd(all, a)
        if g in A:
            cnt += 1
                
    print(N - cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
num_list = [0] * (max(A) + 1)
for i in range(len(A)):
    num_list[A[i]] += 1
for i in range(len(num_list)):
    if num_list[i] == 0:
        continue
    elif num_list[i] >= 2:
        num_list[i] = 0
    else:
        for j in range(2 * i, max(A) + 1,i):
            num_list[j] = 0
ans = 0
for i in range(len(num_list)):
    ans += num_list[i]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline #文字列入力はするな！！
sys.setrecursionlimit(10**9) #再帰の上限をあげる
n=int(input())
a=list(map(int,input().split()))
z=[0]*(10**6+1)
ans=0
for i in a:
    z[i]+=1

x=[-1]*(10**6+1) #2以上の自然数に対して最小の素因数を表す
x[0]=0
x[1]=1
i=2
prime=[]
while i<=10**6:
    if x[i]==-1:
        x[i]=i
        prime.append(i)
    for j in prime:
        if i*j>10**6 or j>x[i]:break
        x[j*i]=j
    i+=1

for i in a:
    f=0
    u=i
    if z[u]>=2:
        f=1
    w=[]
    p=x[u]
    cnt=1
    while u>1:
        if p==x[u//p]:
            cnt+=1
            u=u//p
        else:
            w.append([p,cnt])
            cnt=1
            u=u//p
            p=x[u]

    m=len(w)
    y=1
    def s(d,h,y):
        global m
        global i
        global f
        if d==m-1:
            p=y*(w[d][0]**h)
            if p!=i and z[p]>=1:
                f=1
        else:
            y*=w[d][0]**h
            for j in range(w[d+1][1]+1):
                s(d+1,j,y)
    if m==0:
        if z[1]>=2:
            f=1
    else:
        for j in range(w[0][1]+1):
            s(0,j,1)
        if f==0:
            ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline #文字列入力はするな！！

n=int(input())
a=list(map(int,input().split()))
z=[0]*(10**6+1)
ans=0
for i in a:
    z[i]+=1
for i in a:
    j=2
    f=0
    if z[i]>=2:
        f=1
    if z[1]>=2:
        f=1
    if i!=1 and z[i]==1:
        f=1
    while j*j<=i:
        if i%j==0:
            if z[j]>=1 or z[i//j]>=1:
                f=1
        j+=1
    if f==0:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline #文字列入力はするな！！

n=int(input())
a=list(map(int,input().split()))
z=[0]*(10**6+1)
ans=0
for i in a:
    z[i]+=1
for i in a:
    j=2
    f=0
    if z[i]>=2:
        f=1
    if z[1]>=1:
        f=1
    while j*j<=i:
        if i%j==0:
            if z[j]>=1 or z[i//j]>=1:
                f=1
        j+=1
    if f==0:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Sep 12 00:21:05 2020

@author: liang
"""

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

A.sort()
dp = [0] + [True]*10**6
def Solve():
    if A[0] == 1:
        if len(A) >= 2 and A[1] == 1:
            return 0
        else:
            return 1
    k = 0
    for i in range(1,10**6+1):
        if i == A[k]:
            #print("A",i)
            #kの処理
            tmp = A[k]
            cnt = 1
            while k < N-1 and A[k] == tmp:
                #("B",k)
                if cnt == 2:
                    dp[tmp] = False
                cnt += 1
                k += 1
            #倍数の消去
            for j in range(2*i,10**6+1,i):
                #print("C")
                dp[j] = False
    ans = 0
    for a in A:
        if dp[a]:
            ans += 1
    return ans

ans = Solve()
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
nums = list(map(int,input().split()))
nums.sort()
ans = 0
cnt = {}
flag = [0]*1000005
for i in nums:
  cnt[i] = cnt.get(i,0) + 1

for i in nums:
  if flag[i] == 0 and cnt[i] == 1:
    ans += 1
  if flag[i] == 1:
    continue
  for j in range(i,1000000,i):
    flag[j] = 1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
#import numpy as np
def main():
    n, *a = map(int, read().split())
    if 1 in a:
        count1 = a.count(1)
        if count1 == 1:
            print(1)
            sys.exit()
        else:
            print(0)
            sys.exit()
    maxa = max(a)
    seq = [0] * (maxa + 1)
    for ae in a:
        seq[ae] = 1
    for ae in a:
        t = ae * 2
        while t <= maxa:
            seq[t] = 0
            t += ae
    r = sum(seq)
    print(r)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
nums = list(map(int,input().split()))
nums.sort()
ans = 0
cnt = {}
flag = [0]*1000005
for i in nums:
  cnt[i] = cnt.get(i,0) + 1
 
    
for i in nums:
  if flag[i] == 0 and cnt[i] == 1:
    ans += 1
  for j in range(i*2,1000000,i):
    flag[j] = 1
 
print(ans)