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:
#!python3

LI = lambda: list(map(int, input().split()))

# input
N = int(input())
A = LI()

MAX = 10 ** 6


def main():
    A.sort()
    s = set()
    ans = N
    for i in range(N):
        a = A[i]
        if a in s:
            ans -= 1
            continue
        if A[(i + 1) % N] == a:
            ans -= 1
        n = MAX // a
        for i in range(1, n + 1):
            s.add(a * i)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
S = list(map(int, input().split()))
S.sort()
ans = 0
if N > 1:
    if S[0] < S[1]:
        ans += 1
else:
    ans = 1
for i in range(N-1, 0, -1):
    num = S[i]
    flg = True
    for j in range(i):
        if num%S[j] == 0:
            flg = False
            break
        elif S[j] > num**0.5:
            break
    if num%S[i-1] == 0:
        flg = False
    if flg:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

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

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

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


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

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

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

cnt = 0
for i in range(N):
    if minus_list[A[i]] == 1:
        cnt += 1
    minus_list[A[i]] += 1

prime = []

while len(A) > 1:
    prime.append(A[0])
    A = [j for j in A if j % A[0] != 0]

prime += A

print(len(prime) - cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
ls = list(map(int,input().split()))
ls.sort()
if ls.count(min(ls)) == 1:
    k = 1
else:
    k = 0
for i in range(1,n):
    for j in range(i):
        if i == j:
            continue
        if ls[i] >=2*ls[j] or ls[i] == ls[j]:
            p = ls[i]/ls[j]
            if p % 1 == 0:
                break
    else:
        k += 1
print(k)

Submission status: Wrong Answer

Solution code:
MAXA = 10**5+1
N = int(input())
A = list(map(int,input().split()))
A.append(MAXA)
A.sort()
hurui = [0]*(max(A)+2)
ans = 0
for j in range(N):
    a = A[j]
    if hurui[a] == 0 and A[j+1] != a:
        ans += 1
    for i in range(a,max(A),a):
        if hurui[i]:
            break
        hurui[i] += 1

print(ans)

Submission status: Wrong Answer

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

ans = 0
for i in range(n):
  if i == 0 and n >= 2 and a[i] == a[i+1]:
    continue
  if i == n-1 and n >= 2 and a[i] == a[i-1]:
    continue
  if i != 0 and i != n-1 and (a[i] == a[i-1] or a[i] == a[i+1]):
    continue
  ok = True
  for j in range(2, int(a[i]**(1/2))+1):
    if a[i] % j == 0:
      rem = a[i] // j
      if j in s or rem in s:
        ok = False
  if ok:
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
a.sort()

cnt = [0]*(10**6 + 1)
lst = [True]*(10**6+1)
for i in a:
    cnt[i] += 1

ans = 0
for i in a:
    if cnt[i] == 1 and lst[i]:
        ans += 1
        j = 1
        while i*j <= 10**6:
            lst[i*j] = False
            j += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect, bisect_left
N = int(input())
A = sorted(list(map(int, input().split())))
ans = 0
i = 0
while i < N:
  m = 1
  isOK = True
  while m**2 <= A[i] and isOK:
    if A[i] % m == 0:
      idx = bisect_left(A, m)
      if idx >= 0 and idx < N and A[idx] == m:
        isOK = False
      elif m != 1:
        idx = bisect_left(A, A[i]//m)
        if idx >= 0 and idx < N and A[idx] == A[i]//m:
          isOK = False
    m += 1
  if bisect(A, A[i])-bisect_left(A, A[i]) == 1 and isOK:
    ans += 1
  i += 1
print(ans)

Submission status: Wrong Answer

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

    divisors.sort()
    return divisors

N=int(input())

a_list=list(map(int,input().split()))
n_list=[0]*1000000

for a in a_list:
    #if a >= MN:
    #    pass
    #else:
    n_list[a-1]+=1

cnt=0

for a in a_list:
    y_list=make_divisors(a)[:-1]

    flag=True
    for y in y_list:
        #if y >=N:
        #    pass
        if n_list[y-1]==1:
            flag=False
            continue
    
    if n_list[a-1]>=2:
        flag=False
    
    if flag:
        cnt+=1

print(cnt)

Submission status: Wrong Answer

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

def slove():
    n = int(input())
    A = list(map(int,input().split()))
    A = sorted(A)
    ans = [1]*n
    for i in range(n):
        if ans[i] == 0:
            continue
        #print(i)
        if A[i] == A[(i+1)%n]:
            ans[i] = 0
        for j in range(i+1,n):
            if A[j] % A[i] == 0:
                ans[j] = 0
    print(sum(ans))


if __name__ == "__main__":
    slove()

Submission status: Wrong Answer

Solution code:
import numpy as np
n=int(input())
a=list(map(int,input().split()))
ans=0
aa=np.array(a)
for i in range(n):
    if np.count_nonzero(aa%a[i]==0)==1:
        ans+=1
print(ans)

Submission status: Wrong Answer

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

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]

ans = 0
for i in range(N):
    tmp = A + make_divisors(A[i])
    #print(tmp)
    #print(set(tmp))
    if len(set(tmp)) == len(tmp) - 1:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

#print(make_divisors(1000000)[:-1])
N = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(N):
  if A.count(A[i]) != 1:
    continue
  x = make_divisors(A[i])[:-1]
  p = 0
  for j in x:
    if j != 1:
      if j in A:
        p = 1
  if p == 0:
    ans += 1
  
    
print(ans)

Submission status: Wrong Answer

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

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

if Ain.count(A[0])==1:
    ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
from collections import Counter
ctr = Counter(A)
B = [k for k,v in ctr.items() if v == 1]
B.sort()
D = {b:i for i,b in enumerate(B)}

ok = [1] * len(B)
MX = 10**6+1
for b in B:
    for n in range(2*b,MX,b):
        if n in D:
            ok[D[n]] = 0
print(sum(ok))

Submission status: Wrong Answer

Solution code:
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    ans = 0
    for i in range(n):
        for j in range(i):
            if a[i] % a[j] == 0:
                break
        else:
            if i < n - 1 and a[i] != a[i + 1]:
                ans += 1
            elif i == n - 1 and a[i] != a[i - 1]:
                ans += 1
    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
a=input()
a0=a.split()
al=list()
k=0
for i in range(n):
    al.append(int(a0[i]))
print(al)
for i in range(n):
    f=0
    for j in range(n):
        if i!=j and al[i]%al[j]==0:
            f=1
            break
    if f==0:
        k=k+1
print(k)

Submission status: Wrong Answer

Solution code:
import bisect


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


n = int(input())
*A, = map(int, input().split())
A.sort()
cnt = 0
for i, a in enumerate(A):
    X = make_divisors(a)
    for x in X:
        le = bisect.bisect_left(A, x, hi=i)
        re = bisect.bisect_right(A, x, hi=i)
        if le != re:
            cnt += 1
            break
print(n - cnt)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
N = int(input())
li = [True for _ in range(0, 10**6 + 1)]
A = list(map(int, input().split()))
A.sort()
ans = 0
for i in range(N):
    if li[A[i]]:
        ans += 1
    else:
        continue
    for j in range(A[i], 10**6 + 1, A[i]):
        li[j] = False
ans -= len(A) - len(set(A))
if N == 1:
    ans = 0
print(max(0, ans))

Submission status: Wrong Answer

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

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]


m2=0
for i in range(n):
    c = make_divisors(a[i])
    c.pop()
    m=0
    for j in c:
        if j not in b:
            m+=1
        else:
            break
    if m==len(c):
        m2+=1
print(m2)

Submission status: Wrong Answer

Solution code:
s=[1,2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 
41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 
229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
def make_divisors(n):
    divisors = []
    k=int(n**0.5)+1
    for i in s:
        if i>k:
            break
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()　#小さい順位欲しいとき
    return divisors

n=int(input())
a=sorted(list(map(int,input().split())))
dic={}
for k in a:
    x=make_divisors(k)
    if k in dic:
        dic[k]=0
        continue
    f=1
    for i in x:
        if i in dic:
            f=0
            break
    if f:
        dic[k]=1
print(sum(dic.values()))

Submission status: Wrong Answer

Solution code:
num = int(input())
arr = input().split()
arr = [int(i) for i in arr]

arr = sorted(arr, reverse=True)

cnt = 0

for i in range(num-1):
  flg=0
  for j in range(num-1, i+1, -1):
    if arr[i]%arr[j]==0:
      flg=1
      break
  if flg==0: cnt += 1
    
print(cnt)

Submission status: Wrong Answer

Solution code:
#2*10**8...
from collections import Counter
n=map(int, input().split())
*a,=map(int, input().split())
sa=Counter(a)
def fct(x):
    f1=[1]
    f2=[]
    for i in range(2,min(int(x**(1/2)+7),x)):
        if x%i==0:
            f1.append(i)
            f2.append(x//i)
    return (set(f1+f2))
ans=0
for ai in sa:
    if sa[ai]>1:
        continue
    fa=fct(ai)
    ad=True
    for f in fa:
        if f in sa and f:
            ad=False
            break
    if ad:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
a=list(map(int,input().split()))
# n=10**5
# a=[i for i in range(2,10**5+2)]
# print(len(a))
a.sort()
tmp=Counter(a)
lst=[]
for i in range(n):
    if tmp[a[i]]!=1:
        continue
    for j in lst:
        if a[i]%j==0:
            break
    else:
        lst.append(a[i])
print(len(lst))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
ans = 0
for i, a in enumerate(A):
    if i != N-1:
        if a == A[i+1]:
            continue
    if i != 0:
        if a == A[i-1]:
            continue
    flag = True
    for j in range(i):
        if a % A[j] == 0:
            flag = False
            break
        elif a < A[j] ** 2:
            break
    if flag:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
if len(set(A)) == 1:
    print(0)
else:
    A.sort()
    s = set()
    counter = 0
    for a in A:
        flag = True
        for b in s:
            if a % b == 0:
                flag = False
        if flag == True:
            counter += 1
            s.add(a)
    print(counter)

Submission status: Wrong Answer

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

from math import gcd
def ngcd(lista):
    res = lista[0]
    for i in range(1,len(lista)):
        if res != 1:
            res = gcd(lista[i],res)
    return res

def main():
    n = int(input())
    a = list(map(int,input().split()))
    s = set(a)
    cnt = 0
    if ngcd(a) != 1:
        print(0)
        return 0
    for i in range(n):
        #if c[a[i]] > 1:
        #    continue
        tmp = set(make_divisors(a[i]))
        if len(tmp) - len(tmp-s) == 1:
            cnt += 1
    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# D

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

n = int(input())
a = list(map(int, input().split()))
a.sort()
max_a = a[-1]

if len(set(a)) == 1:
    print(0)
    sys.exit()

lis_prime = [False] * (max_a+1)
for a_ in a:
    lis_prime[a_] = True

primes = []
cnt = 0

for i in range(len(lis_prime)):
    if lis_prime[i]:
        primes.append(i)
        cnt += 1

        j = 2 * i
        while True:
            if j > max_a:
                break
            lis_prime[j] = False
            j += i

print(len(primes))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
c = [0]*n
a.sort()
for i in range(n-1):
    for j in range(i+1, n):
        if a[j]%a[i] == 0:
            c[j] += 1
if len(a) >= 2 and a[0]%a[1] == 0:
    c[0]+=1
print(c.count(0))

Submission status: Wrong Answer

Solution code:
import numpy as np

def main():
    n = int(input())
    A = list(map(int, input().split()))
    A.sort()
    A = np.array(A, np.int64)

    if np.all(A == A[0]):
        print(0)
        exit()
    #print(A)

    memo = [1] * n
    for i in range(n - 1):
        for j in range(i + 1, n):
            if memo[j] == 0:
                break
            if A[j] % A[i] == 0:
                memo[j] = 0

    print(memo.count(1))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

A.sort()

ls = []

for i in range(N):
    a = A[i]

    if (i + 1 < N and a == A[i + 1]) or (i - 1 >= 0 and a == A[i - 1]):
        continue
    else:
        for b in ls:
            if a % b == 0:
                break
        else:
            ls.append(a)

print(len(ls))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
from collections import Counter
seta=set(a)
ca=dict(Counter(a))
a=[k for k,v in ca.items() if v==1]
if len(a)==0:
  print(0)
  exit()
a.sort()
maxa=a[-1]
for ai in a:
  i=2
  while maxa>=i*ai:
    seta.discard(i*ai)
    i+=1
print(len(seta))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
ans = [1 for _ in range(N)]
for i in range(N - 1):
  for j in range(i + 1, N):
    if ans[j] == 0:
      continue
    if (A[j]//A[i])*A[i] == A[j]:
      ans[j] = 0
ans = sum(ans)
if N >= 2 and A[0] == A[1]:
  ans -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
from math import gcd
def main():
    n = int(input())
    A = list(map(int, input().split()))
    ans = 1
    A.sort()
    a_pre = A[0]
    res = A[0]
    for i, a in enumerate(A[1:]):
        if a == a_pre:
            ans += 1
        else:
            for b in A[:i + 1]:
                if gcd(b, a) != 1:
                    break
            else:
                ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

if A[0] != A[1]:
    ans = set([A[0]])
else:
    ans = set()

for i in range(1, N):
    flg = True
    if A[i] == A[i-1]:
        continue
    for j in ans:
        if A[i] % j == 0:
            flg = False
    if flg:
        ans.add(A[i])

print(len(ans))

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""

n = onem()

a = l()

a.sort()

aa = s(a)

ans = 0
dp = [0 for i in range(10**6+1)]
for i in range(len(aa)):
	co = 0
	f = 0
	if aa[i][1] != 1:
		f = 1
	elif dp[aa[i][0]] != 0:
		f = 1
	else:
		for _ in range(aa[i][0],10**6+1,aa[i][0]):
			dp[_] = 1
	if not f:
		ans += 1



print(ans)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
"""
すべてのjで割れない場合、カウントする。
逆に言えば、一つでもiをjで割れるようなjが存在するならば、それはカウントしない。
一番小さい数が2つあればそれはカウントしないが、基本的に一番小さい数はほかのどの数字でも割れない
Aiの制約が10**6であることから、小さい数から数えていって、10**6までの倍数の場所にマークを付ける。
初めて出てくるような数字に関して、カウントを1足してやる。
一番小さい数のコーナーケースに注意
"""
n = int(readline())
lst1 = list(map(int,readline().split()))

lst1.sort()

memo = [0]*(10**6+1)
if n == 1:
    print(1)
    exit()
if lst1[0] == lst1[1]:
    ans = -1
    if lst1[0] == 1:
        print(0)
        exit()
else:
    ans = 0
    if lst1[0] == 1:
        print(1)
        exit()
for i in lst1:
    if memo[i] == 0:
        ans += 1
        j = 1
        while i*j <= 10**6:
            memo[i*j] = 1
            j += 1
    else:
        continue

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
    sys.setrecursionlimit(10 ** 7)

    n = int(readline())
    a = list(map(int, readline().split()))
    if len(set(a)) == 1 and n > 1:
        print(0)
        exit()
    a.sort()
    memo = [True] * (2 * 10 ** 6 + 1)
    ans = 0
    for aa in a:
        if memo[aa]:
            ans += 1
            for i in range(1, 10 ** 6 + 1):
                if 10 ** 6 + 1 < i * aa:
                    break
                memo[i * aa] = False
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np

N=int(input())
lis=list(map(int, input().split()))
lis.sort(reverse=True)
arr=np.array(lis)
ans=0

for i in range(N):
    if np.count_nonzero(arr[i] % arr[i+1:] == 0) == 0:
        ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter


def enum_divs(n):
    res = []
    for i in range(1, int(n ** .5) + 1):
        if n % i == 0:
            res.append(i)
            if i != n // i:
                res.append(n // i)
    return res


N = int(input())
A = list(map(int, input().split()))
uq_A = [k for k, v in Counter(A).items() if v == 1]
set_A = set(uq_A)
ans = 0
for a in uq_A:
    if any(n in set_A - {a} for n in enum_divs(a)):
        continue
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = [int(x) for x in input().split()]
A.sort()
ans = 0
for i, a in enumerate(A):
    if i != n - 1 and A[i + 1] == a:
        continue
    do_count = True
    for j in range(i):
        b = A[j]
        if a % b == 0:
            do_count = False
            break
        if b ** 2 > a:
            break
    if do_count:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N = int(input())
A = LI()
A.sort()

cc = collections.Counter(A)
# print(cc)
chosen = []
for key in cc.keys():
    if cc[key] > 1:
        continue
    if len(chosen) == 0:
        chosen.append(key)
    else:
        for c in chosen:
            if key % c == 0:
                break
        else:
            chosen.append(key)

print(len(chosen))

Submission status: Wrong Answer

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

A.sort()
from collections import Counter
L = dict(Counter(A))

Xs = list(L.keys())
NX = len(Xs)

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

if NX!=1:
    cnt = 0
    for X in Xs:
        if B[X]>0:
            continue
        else:
            cnt += L[X]
            check = X
            t = 2
            while check*t<10**6+1:
                B[check*t]=1
                t+=1
    print(cnt)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()
A.sort(reverse=True)
q = deque(A)

# for i, a in enumerate(A):
#     b = A[i+1:]
cnt = 0
ans = 0
while q:
    a = q.popleft()
    # print(a)
    l = len(q)
    cnt = 0
    for b in q:
        # print(q)
        # print("b:", b)
        if a % b == 0:
            cnt += 1
            # print(cnt, a, b)    
    if l == 0:
        # last
        if a not in A[:-1]:
            ans += 1
    else:
        if cnt == 0:
            ans += 1
    

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
"""
普通にやると、O(N^2)かかる
エラトステネスの篩でできないか？
まず、長さ10^6+1のflag配列を用意する。初期値は全部1。
Aに含まれる値以外は0にする。
で、エラトステネスの篩と同じことをする。
"""
A = set(A)
flags = [1]*(1000001)
for i in range(1000001):
    if i not in A:
        flags[i] = 0
ans = 0
for i in range(1000001):
    if flags[i] == 1:
        ans += 1
        for j in range(i*2,1000001,i):
            flags[j] = 0

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
dat = list(map(int, input().split()))
res = 0
import collections
buf = collections.Counter(dat)
dat = []
for k in buf:
    if buf[k] == 1:
        dat.append(k)
dat.sort()
#print(dat)
res = 0
used = [False] * (1000100)

for i in range(len(dat)):
    ok = True

    if used[dat[i]]:
        ok = False
    c = 1
    v = dat[i] * c
    while v <= 1000010:
        used[v] = True
        c += 1
        v = dat[i] * c


    used[dat[i]] = True
    if ok:
        res += 1
print(res)

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline


def calc_divisors(n):
    divisors_a = []
    divisors_b = []
    for d in range(1, int(n**0.5) + 1):
        if n % d == 0:
            divisors_a.append(d)
            if n // d != d:
                divisors_b.append(n // d)
    divisors = divisors_a + divisors_b[::-1]
    return divisors


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

    S = set(A)
    if len(S) == 1:
        ans = 0
    else:
        ans = 0
        for a in A:
            divisors = calc_divisors(a)
            S.remove(a)
            ans += 1 if all(d not in S for d in divisors) else 0
            S.add(a)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
cnt=0
L=len(A)-1
for a in A:
    tmp=0
    for b in A:
        if a!=b and a%b!=0:
            tmp+=1
            if tmp==L:
                cnt+=1
print(cnt)

Submission status: Wrong Answer

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

D_SET = set()
A_SET = set(A)

for i, v in c.items():
    if v > 1:
        D_SET.add(i)

ans = 0
for a in A:
    if a in D_SET:
        continue
    # 約数列挙(1,N)も含まれる
    i = 2
    prime = []
    while i * i <= a:
        if a % i == 0:
            prime.append(i)
            prime.append(a//i)
        i += 1
    judge = True
    for x in prime:
        if x in A_SET:
            judge = False
            break
    if judge:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

ctr = Counter(A)
memo = set()
ans = 0

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

    for i in range(1, int(a ** 0.5) + 1):
        if a % i == 0:
            if (i in memo) or (a // i in memo):
                break
    else:
        if ctr[a] == 1:
            ans += 1

    memo.add(a)
        
print(ans)

Submission status: Wrong Answer

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

if n>1:
    if li[-1]==li[-2]:
        ans -= 1

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

    divisors.sort()
    return divisors

while len(li)>0:
    tmp = li.pop(0)
    se = set(make_divisors(tmp))
    l1_l2_and = set(li) & set(se)
    if len(l1_l2_and)==0:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

def is_prime(n):
    if n <= 1: return False
    for i in range(2, int(n**0.5)+1):
        if n%i == 0: return False
    return True

A.sort()
if len(A) == 1:
    print(0)
    exit()

ans = []
for i in range(n):
    if i > len(A): break
    ans.append(A[0])
    A = [j for j in A if j%A[0]!=0]
print(len(ans+A))