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,*a=map(int,open(0).read().split())
a.sort()
for i in range(n):
    for j in range(n):
        if i!=j and a[i]%a[j]==0:
            n-=1
            break
print(n)

Submission status: Wrong Answer

Solution code:
import sys
from io import StringIO
import unittest
import os
import math
import collections
import math

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


# 素因数分解モジュール
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


# 実装を行う関数
def resolve(test_def_name=""):
    # 数値取得サンプル
    #   1行N項目 x, y = map(int, input().split())
    #   N行N項目 x = [list(map(int, input().split())) for i in range(n)]

    # 文字取得サンプル
    #   1行1項目 x = input()
    n = int(input())

    a_list = list(map(int, input().split()))
    a_list.sort()
    a_list = list(set(a_list))

    if len(a_list) == 1:
        print(0)
        return

    if a_list[0] == 1:
        print(len(a_list) - 1)
        return

    dp = [False for i in range(1000001)]

    for a in a_list:
        if dp[a]:
            continue
        for i in range(500001):
            if a * (i+2) > 1000000:
                break
            dp[a * (i+2)] = True

    ans = 0
    for a in a_list:
        if not dp[a]:
            ans += 1

    print(ans)


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """5
24 11 8 3 16"""
        output = """3"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """4
5 5 5 5"""
        output = """0"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """10
33 18 45 28 8 19 89 86 2 4"""
        output = """5"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def test_1original_1(self):
        test_input = """6
        2 7 21 1000000 1000000 1000000"""
        output = """2"""
        self.assertIO(test_input, output)

    def test_1original_2(self):
        test_input = """6
        1 7 21 1000000 1000000 1000000"""
        output = """3"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Wrong Answer

Solution code:
n,*a=map(int,open(0).read().split())
for i in range(n):
    for j in range(n):
        if i!=j and a[i]%a[j]==0:
            n-=1
            break
print(n)

Submission status: Wrong Answer

Solution code:
import sys
from io import StringIO
import unittest
import os
import math
import collections
import math

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


# 素因数分解モジュール
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


# 実装を行う関数
def resolve(test_def_name=""):
    # 数値取得サンプル
    #   1行N項目 x, y = map(int, input().split())
    #   N行N項目 x = [list(map(int, input().split())) for i in range(n)]

    # 文字取得サンプル
    #   1行1項目 x = input()
    n = int(input())

    a_list = list(map(int, input().split()))
    a_list.sort()
    a_list = list(set(a_list))

    if len(a_list) == 1:
        print(0)
        return

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

    dp = [False for i in range(1000001)]

    for a in a_list:
        if dp[a]:
            continue
        for i in range(500001):
            if a * (i+2) > 1000000:
                break
            dp[a * (i+2)] = True

    ans = 0
    for a in a_list:
        if not dp[a]:
            ans += 1

    print(ans)


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """5
24 11 8 3 16"""
        output = """3"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """4
5 5 5 5"""
        output = """0"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """10
33 18 45 28 8 19 89 86 2 4"""
        output = """5"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
bai = [0 for _ in range(max(a)+1)]
i = 2
for i in a:
    j = i
    while j < len(bai):
        bai[j] += 1
        j += i

res = 0
if n <= 1:
    print(i)
    exit()

for i in range(n):
    if i == 0:
        if a[i] != a[i+1] and bai[a[i]] == 1:
            res += 1
    elif i == n-1:
        if a[i] != a[i-1] and bai[a[i]] == 1:
            res += 1
    else:
        if a[i] != a[i-1] and a[i] != a[i+1] and bai[a[i]] == 1:
            res += 1

print(res)

Submission status: Wrong Answer

Solution code:
def main():
  n=int(input())
  a=sorted(map(int,input().split()))
  #maxa=a[-1]+1
  af=[False]*n
  #tf=[False]*maxa
  r=0
  n-=1
  for i in range(n):
    a_i=a[i]
    if af[i] ==False:
      #print(a_i)
      if a_i < a[i+1]:
        r+=1
      for j in reversed(range(i+1,n+1)):
        #print(a[j])
        if a[j]<a_i*2:
          break
        if a[j] % a_i == 0:
          #print(str(a_i)+"aj:"+str(a[j]))
          af[j]=True
  if af[-1] ==False:
    r+=1
  print(r)
main()

Submission status: Wrong Answer

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


def divisor(n):
    div_list = []
    limit = int(n**0.5) + 1
    for div in range(1, limit):
        if n % div == 0:
            div2 = n // div
            div_list.append(div)
            if div != div2:
                div_list.append(div2)
    
    return div_list


nums = set()
ans = n
A.sort()
for a in A:
    divs = divisor(a)
    for div in divs:
        if div in nums:
            ans -= 1
            break
    nums.add(a)
        
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from io import StringIO
import unittest
import os
import math
import collections
import math

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


# 素因数分解モジュール
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


# 実装を行う関数
def resolve(test_def_name=""):
    # 数値取得サンプル
    #   1行N項目 x, y = map(int, input().split())
    #   N行N項目 x = [list(map(int, input().split())) for i in range(n)]

    # 文字取得サンプル
    #   1行1項目 x = input()
    n = int(input())

    a_list = list(map(int, input().split()))
    a_list.sort()
    a_list = list(set(a_list))

    if len(a_list) == 1:
        print(0)
        return

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

    limit = a_list[-1] / 2

    a_len = len(a_list)
    for i in range(9999999):
        if i >= len(a_list):
            break

        if a_list[i] > limit:
            break

        new_list = []
        for j in a_list:
            if a_list[i] == j:
                new_list.append(j)
            elif not j % a_list[i] == 0:
                new_list.append(j)

        a_list = new_list

    print(len(a_list))


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """5
24 11 8 3 16"""
        output = """3"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """4
5 5 5 5"""
        output = """0"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """10
33 18 45 28 8 19 89 86 2 4"""
        output = """5"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Wrong Answer

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

div = [[a_i % a_j for a_j in A[i+1:]] for i, a_i in enumerate(A[:N-1])]
ans = 0
for d in div:
  if 0 not in d:
    ans += 1
    
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from io import StringIO
import unittest
import os
import math
import collections
import math

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


# 素因数分解モジュール
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


# 実装を行う関数
def resolve(test_def_name=""):
    # 数値取得サンプル
    #   1行N項目 x, y = map(int, input().split())
    #   N行N項目 x = [list(map(int, input().split())) for i in range(n)]

    # 文字取得サンプル
    #   1行1項目 x = input()
    n = int(input())

    a_list = list(map(int, input().split()))
    a_list.sort()
    a_list = list(set(a_list))

    if len(a_list) == 1:
        print(0)
        return

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

    limit = a_list[-1] / 2

    a_len = len(a_list)
    for i in range(9999999):
        if i >= len(a_list):
            break
        # if a_list[i] > limit:
        #     break

        new_list = []
        for j in a_list:
            if a_list[i] == j:
                new_list.append(j)
            elif not j % a_list[i] == 0:
                new_list.append(j)

        a_list = new_list

    print(len(a_list))


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """5
24 11 8 3 16"""
        output = """3"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """4
5 5 5 5"""
        output = """0"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """10
33 18 45 28 8 19 89 86 2 4"""
        output = """5"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
divs = [a[0]]
idx=1
v = a[0]
t = a[-1]**(1/2)
while v<t and idx<n:
  if all([a[idx]%d!=0 for d in divs]):
    divs.append(a[idx])
  v = a[idx]
  idx += 1
for i in range(n):
  if all(a[i]!=d and a[i]%d!=0 for d in divs):
    divs.append(a[i])
if len(divs)==1:
  if all(p%divs[0]!=0 for p in a[1:]):
    print(len(divs)+1)  
  else:
    print(0)
else:
  print(len(divs))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
divs = [a[0]]
idx=1
v = a[0]
t = a[-1]/2
while v<t and idx<n:
  if all([a[idx]%d!=0 for d in divs]):
    divs.append(a[idx])
  v = a[idx]
  idx += 1
ans = 0
for i in range(n):
  if all(a[i]!=d and a[i]%d!=0 for d in divs):
    ans += 1
if len(divs)==1:
  if all(p%divs[0]!=0 for p in a[1:]):
    print(ans+1)  
  else:
    print(ans)
else:
  print(ans+len(divs))

Submission status: Wrong Answer

Solution code:
from collections import Counter
teisuu1=10**6
N=int(input())
A=list(map(int,input().split()))
count_A=Counter(A)
dp=[True]*(teisuu1+1)
s=list(set(A))
for i in s:
  temp=i*2
  while temp<=s[-1]:
    dp[temp]=False
    temp+=i
ans=0
for i in A:
  if count_A[i]==1 and dp[i]==True:
    ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys 
import numpy as np
from numba import jit
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


@jit(cache=True)
def solve(A):
  count = np.zeros(10**6)
  for x in A:
    if count[x] > 1:
      continue
    count[::x] += 1
  ans = 0
  for x in A:
    ans += count[x] == 1
  return ans

N = int(readline())
A = list(map(int,readline().split()))
A = np.array(A)
print(solve(A))

Submission status: Wrong Answer

Solution code:
from collections import Counter
teisuu1=10**6
N=int(input())
A=list(map(int,input().split()))
count_A=Counter(A)
print(count_A)
dp=[True]*(teisuu1+1)
s=list(set(A))
for i in s:
  temp=i*2
  while temp<=teisuu1:
    dp[temp]=False
    temp+=i
ans=0
for i in A:
  if count_A[i]==1 and dp[i]==True:
    ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
def d170(n,a):
    count=0
    sa=sorted(a)
    dp=[True for i in range(n)]
    return dp.count(True)
    
n=int(input())
a= list(map(int, input().split()))    
print(d170(n,a))

Submission status: Wrong Answer

Solution code:
n = int(input())
list_P = list(map(int, input().split()))
list_P.sort()
list_ANS = list_P.copy()

for i in range(n):
    for num in list_ANS:
        if list_P[i] != num and num % list_P[i] == 0:
            list_ANS.remove(num)

print(len(list_ANS))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = sorted(list(map(int,input().split())))
m = max(a)+1
c = [0]*m
for x in a:
    for i in range(x,m,x):
        if c[i]<2:c[i]+=1
        else:break
ans = 0
for i in a:
    if c[i]==1:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

MAX_N = max(A)+1
cnt = [0] * MAX_N 

for a in A:
  for i in range(a, MAX_N, a):
    if cnt[i-1] >= 2: break 
    cnt[i-1] += 1
      
ans = 0
for a in A:
  if cnt[a-1] == 1: ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input().strip())
A = list(map(int, input().strip().split()))
A.sort()
AMAX = max(A)
ans = 0
is_div = [True for i in range(AMAX+1)]
print(A)
for i in range(N):
  a = A[i]
  if is_div[a]:
    if not ((i > 0 and A[i] == A[i-1]) or (i < N-1 and A[i] == A[i+1])):
      ans += 1
    for j in range(a, AMAX+1, a):
      is_div[j] = False
print(f'{ans}')

Submission status: Wrong Answer

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

MAX_N = max(A)+1
cnt = [0] * MAX_N 

for a in A:
  for i in range(a, MAX_N, a):
    if cnt[i] >= 2: break 
    cnt[i] += 1
      
ans = 0
for a in A:
  if cnt[a] == 1: ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
li = set(list(map(int,input().split())))
li=sorted(list(li))
ans=0
dp=[0]*(li[-1]+1)
for i in li:
    for j in range(i,li[-1]+1,i):
        dp[j]+=1
for i in li:
    if dp[i]==1:
        ans+=1
if len(li)>1:
    print(ans)
else:
    print(0)

Submission status: Wrong Answer

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

F = [0 for i in range(10**6+1)]
for i in A:
  F[i] = 1

c_set = set()
for i in range(1,N+1):
  if F[i] == 0:
    continue
  c_set.add(i)
  for j in range(2*i, N+1, i):
    F[j] = 0

ans = len(c_set)
d = 0
for i in c_set:
  if A.count(i) > 1:
    d += 1

print(ans - d)

Submission status: Wrong Answer

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

F = [0 for i in range(10**6+1)]
for i in A:
  F[i] = 1

c_set = set()
for i in range(1,N+1):
  if F[i] == 0:
    continue
  c_set.add(i)
  for j in range(2*i, N+1, i):
    F[i] = 0

ans = len(c_set)
d = 0
for i in c_set:
  if A.count(i) > 1:
    d += 1

print(ans - d)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=sorted(list(map(int,input().split())))
dp=[True]*N
if len(set(A))==1:
    print(0)
    exit()
for i in range(N-1):
    if dp[i]:
        for j in range(i+1,N):
            if A[j]%A[i]==0:
                dp[j]=False
print(dp.count(True))

Submission status: Wrong Answer

Solution code:
n = int(input())
data = list(map(int, input().split()))
mx = max(data)
marked = [0]*(mx + 1)
for a in data:
    for x in range(a, mx+1, a):
        marked[x] += 1
        print(marked)
ans = 0
for a in data:
    if marked[a] == 1:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
d=dict()
for i in a:
    if i in d:
        d[i]+=1
    else:
        d[i]=1
e=list()
for i,j in d.items():
    if j==1:
        e.append(i)
e.sort()
n=len(e)
c=[1 for i in range(n)]
for i in range(n):
    if c[i]==0:
        continue
    for j in range(i+1,n):
        if c[j]==0:
            continue
        if e[j]%e[i]==0:
            c[j]=0
print(len([i for i in c if i]))
#print(e,c,sep='\n')

Submission status: Wrong Answer

Solution code:
N = int(input())
*A, = map(int, input().split())
m = max(A)
# cnt = [0] * (m + 1)
# for elem in A:
#     cnt[elem] += 1
# print(cnt)

# unique = []
# for i in range(m + 1):
#     if cnt[i] == 1:
#         unique.append(i)
# print(unique)
unique = list(set(A))
if len(unique) == 1:
    unique = []
cnt = [0] * (m + 1)
A = list(set(A))
for elem in A:
    for mul in range(elem * 2, m + 1, elem):
        cnt[mul] = 1
ans = 0

for elem in unique:
    if cnt[elem] == 0:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
aMax=a[-1]
isAns=[True]*(aMax+1)
for ai in a[:n-1]:
    if isAns[ai]:
      jMax=aMax//ai
      for j in range(2,jMax+1):
        isAns[ai*j]=False

ans=0
former=None
for ai in a:
  if former!=ai:
    former=ai
    if isAns[ai]:
      ans+=1
if n>1:
  if a[0]==a[1]:
    ans-=1
  
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
alist = list(map(int, input().split()))
asetlist = list(set(alist))
asetlist.sort()
dp = [0] * (max(asetlist) + 1)

count = 0

for num in asetlist:
  r = num
  if alist.count(num) >= 2:
    count += 1
    
  while num <= max(asetlist):
    dp[num] += 1
    num += r

ans = 0    
    
for num in asetlist:
  if(dp[num] == 1):
    ans += 1
    
print(ans - count)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[int(x) for x in input().split()]
a.sort()
p=[]
q=0
for c in a:
    t=0
    for d in p:
        if c%d==0:
            t=1
            break
    if t==0:
        q+=1
        p.append(c)
print(q)

Submission status: Wrong Answer

Solution code:
def divisor(n):
    d = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            d.append(i)
            if i ** 2 == n:
                continue
            d.append(n // i)
    return d

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

cnt = [0]*(max(A)+1)
for a in A:
    tmp = set(divisor(a)) & set_A
    if len(tmp) == 1 and cnt[a] == 0: 
      cnt[a] = 1
print(sum(cnt))

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
kari=[0]*((10**6)+1)
A.sort()
hako=[]
chohuku=[]
for i in range(N):
    kari[A[i]]+=1

for i in range(N):
    if kari[A[i]]==1:
        hako.append(A[i])
    elif kari[A[i]]>1:
        chohuku.append(A[i])
kari=[0]*((10**6)+1)
aru=A.copy()
count=0
aru=list(set(aru))
#print(hako)
chohuku=list(set(chohuku))
for i in hako:
    for j in range(i*2,10**6+1,i):
        kari[j]+=1
for i in aru:
    if kari[i]==0:
        count+=1
print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
MAX = 10 ** 6 + 10

one = a.count(1)
if one > 0:
  if one == 1:
    print(1)
  else:
    print(0)
  exit(0)

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

    # divisors.sort()
    return divisors
m = [0] * MAX
for i in range(n):
  m[a[i]] += 1
#print(m[:30])
mx = max(a)
ans = 0
a.sort()
for p in range(n):
  i = a[p]
  if m[i] != 1:
    continue
  divs = make_divisors(i)
  flg = True
  #print('i : ', i)
  #print(divs)
  for j in range(len(divs)):
    div = divs[j]
    if div == i:
      continue
    
    if m[div] > 0:
      flg = False
      break
  if flg:
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
kari=[0]*((10**6)+1)
A.sort()
hako=[]
chohuku=[]
for i in range(N):
    kari[A[i]]+=1

for i in range(N):
    if kari[A[i]]==1:
        hako.append(A[i])
    elif kari[A[i]]>1:
        chohuku.append(A[i])
kari=[0]*((10**6)+1)
aru=A.copy()
count=0
aru=list(set(aru))
#print(hako)
chohuku=list(set(chohuku))
for i in aru:
    for j in range(i*2,10**6+1,i):
        kari[j]+=1
for i in aru:
    if kari[i]==0:
        count+=1
print(count-len(chohuku))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import math
import sys
N = int(input())
A = list(map(int, input().split()))
#A.sort()
a_dic = {}
for n in range(N):
    if A[n] in a_dic:
        a_dic[A[n]] += 1
    else:
        a_dic[A[n]] = 1
#print(a_dic)
A = list(set(A))
A.sort()
#print(A)
maxA = max(A)
dp = [1 for i in range(maxA+1)]
ans = 0
for a in A:
    if dp[a] == 1 and a_dic[a] == 1:
        ans += 1
    j = a + a
    while j <= maxA:
        dp[j] = 0
        j += a
        print(j)
#print(dp)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
count = 0 
divisible = False
for i, x in enumerate(A):
  for _i, _x in enumerate(A):
    if _i != i and _x % x == 0:
      divisible = True
      break
  if not divisible:
    count += 1
  divisible = False
print(count)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
import collections
import bisect


def divisors(n):
    i = 2
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    return table

def BinarySearch(a, x): 
    i = bisect.bisect_left(a, x) 
    if i != len(a) and a[i] == x: 
        return i 
    else: 
        return -1

N = int(input())
A = [int(a) for a in input().split()]
A.sort()
L = collections.Counter(A)

ans = 0
for a in A:
    if L[a] != 1:
        continue
    i = 2
    while i * i <= a:
        if a%i == 0:
            if(BinarySearch(A,i) or BinarySearch(A,a//i)):
                break
        i+=1
    else:
        ans += 1

print(ans)

Submission status: Wrong Answer

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

max_num = max(a_list)

is_ans = [False]*(max_num+1)
memo = [0]*(max_num+1)
for i in a_list:
    is_ans[i] = True
    memo[i] += 1

for i in range(1, max_num+1):
    if is_ans[i]:
        for j in range(2*i, max_num+1, i):
                is_ans[j] = False

ans = is_ans.count(True)
e = len([i for i in memo if i > 1])
print(ans-e)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
import collections
import bisect


def divisors(n):
    i = 2
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    return table

def BinarySearch(a, x): 
    i = bisect.bisect_left(a, x) 
    if i != len(a) and a[i] == x: 
        return i 
    else: 
        return -1

N = int(input())
A = [int(a) for a in input().split()]
A.sort()
L = collections.Counter(A)

ans = 0
for a in A:
    if L[a] != 1:
        continue
    for d in divisors(a)[:-1]:
        if(BinarySearch(A, d)!=-1):
            break
    else:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys 
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))

def main():
    n = I()
    a = LI()
    a.sort(reverse=True)
    ava = [1]*n

    for i in range(n):
        for j in range(i+1,n):
            if not ava[i]:
                break
            if not a[i]%a[j]:
                ava[i] = 0
            if not a[j]%a[i]:
                ava[j] = 0
    print(ava.count(1))
    return
 
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
*A, = map(int, input().split())
m = max(A)
# cnt = [0] * (m + 1)
# for elem in A:
#     cnt[elem] += 1
# print(cnt)
#
# unique = []
# for i in range(m + 1):
#     if cnt[i] == 1:
#         unique.append(i)
# print(unique)
unique = list(set(A))

cnt = [0] * (m + 1)
A = list(set(A))
for elem in A:
    for mul in range(elem * 2, m + 1, elem):
        cnt[mul] = 1
ans = 0

for elem in unique:
    if cnt[elem] == 0:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
A = list(map(int, input().split()))
A.sort()
maxA = A[-1]+1
#print(N, A, maxA)
dp = [1 for a in range(maxA)]
#print(dp)
for a in range(maxA):
    if a in A and dp[a] == 1:
        tgt = math.sqrt(maxA)
        b = 2
        while b*a < maxA:
            dp[a*b] = 0
            b += 1
            print(b, tgt)
#print(dp)
myans = 0
for n in range(N):
    myans += dp[A[n]]
print(myans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
import collections
import bisect


def divisors(n):
    i = 2
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return sorted(table)

def BinarySearch(a, x): 
    i = bisect.bisect_left(a, x) 
    if i != len(a) and a[i] == x: 
        return i 
    else: 
        return -1

N = int(input())
A = [int(a) for a in input().split()]
A.sort()
L = collections.Counter(A)

ans = 0
for a in A:
    if L[a] != 1:
        continue
    for d in divisors(a)[:-1]:
        if(BinarySearch(A, d)!=-1):
            break
    else:
        ans += 1

print(ans)

Submission status: Wrong Answer

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

max_num = max(a_list)

is_ans = [False]*(max_num+1)
memo = [0]*(max_num+1)
for i in a_list:
    if memo[i] == 0:
        is_ans[i] = True
        memo[i] = 1
    else:
        is_ans[i] = False

for i in range(1, max_num+1):
    if is_ans[i]:
        for j in range(2*i, max_num+1, i):
                is_ans[j] = False

ans = is_ans.count(True)
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
d=dict()
for i in a:
    if i in d:
        d[i]+=1
    else:
        d[i]=1
e=list()
for i,j in d.items():
    if j==1:
        e.append(i)
e.sort()
n=len(e)
c=[1 for i in range(n)]
for i in range(n):
    for j in range(i+1,n):
        if c[j]==0:
            continue
        if e[j]%e[i]==0:
            c[j]=0
print(len([i for i in c if i]))
#print(e,c,sep='\n')

Submission status: Wrong Answer

Solution code:
import sys 
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))

def main():
    n = I()
    a = LI()
    ava = [1]*n

    for i in range(n):
        x = a[i]
        for j in range(i+1,n):
            if not ava[i] and not ava[j]:
                break
            y = a[j]
            if ava[i]:
                if not x%y:
                    ava[i] = 0
            if ava[j]:
                if not y%x:
                    ava[j] = 0    
    print(ava.count(1))
    return
 
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
A=sorted(map(int,input().split()))
if n==1:
	print(1)
else:
	L=[-float('inf')]
	c=0
	for i in range(n):
		#print(str(A[i])+'だよ'
		if A[i]!=L[-1]:
			flag=0
			j=0
			while j<len(L) and L[j]<=A[i]//2:
				#print(A[i],L[j])
				if A[i]%L[j]==0:
					flag=1
					break
				j+=1
			if flag==0:
				#print(2,2,A[i])
				L.append(A[i])
				c+=1
	print(c)
	#print(L)

Submission status: Wrong Answer

Solution code:
import collections


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

    A.sort()

    sames = 0
    C = collections.Counter(A)
    for v in C.values():
        if v > 1:
            sames += 1

    a_max = A[-1]
    dp = [True] * a_max
    A = set(A)

    for a in A:
        if dp[a - 1]:
            tmp_a = a * 2
            while tmp_a < a_max + 1:
                dp[tmp_a - 1] = False
                tmp_a += a

    r = 0
    for a in A:
        if dp[a - 1]:
            r += 1

    print(r - sames)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
d=dict()
for i in a:
    if i in d:
        d[i]+=1
    else:
        d[i]=1
e=list()
for i,j in d.items():
    if j==1:
        e.append(i)
e.sort()
n=len(e)
c=[1 for i in range(n)]
for i in range(n):
    if c[i]==0:
        continue
    for j in range(i):
        if e[i]%e[j]==0:
            c[i]=0
            break
print(len([i for i in c if i]))
#print(e,c,sep='\n')