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:
if __name__ == "__main__":
    n = int(input())
    l_a = list(map(int, input().split()))
    s_a = list(set(l_a))

    s_a.sort()

    dub_a = [0]*max(s_a)

    for i in l_a:
        dub_a[i-1] += 1

    dp = [1]*max(s_a)

    for i in s_a:
        if 2*i > len(dp)-1:
            pass
        elif dp[2*i-1] == 0:
            pass
        else:
            for j in range(2*i-1, len(dp), i):
                dp[j] = 0


    count = 0
    for i in l_a:
        if dp[i-1]==1 and dub_a[i-1]==1:
            count += 1
    print(count)

Submission status: Wrong Answer

Solution code:
M=10**7
A=[0]*(M)
_,*l=sorted(map(int,open(0).read().split()))
for i in l:
    A[i]+=1
    if A[i]==1:
      for j in range(2*i,M,i):A[j]+=9
print(A.count(1))

Submission status: Wrong Answer

Solution code:
M=10**7;A=[0]*(M);_,*l=sorted(map(int,open(0).read().split()))
for i in l:
    A[i]+=1
    if A[i]==1:
      for j in range(2*i,M,i):A[j]=2
print(A.count(1))

Submission status: Wrong Answer

Solution code:


def main():
    n = int(input())
    a = list(map(int, input().split()))
    temp = [1]*(max(a)+1)
    temp[0] = 0
    a.sort()
    if a.count(1) == 1:
        print(1)
        exit()
    if a.count(1) >= 2:
        print(0)
        exit()
    for i in range(n-1):
        if a[i] == a[i+1]:
            temp[a[i]] = 0
        for j in range(2,(max(a)//a[i])+1):
            if a[i] * j <= max(a):
                temp[a[i] * j] = 0
    cnt = 0
    for k in a:
        if temp[k] == 1:
            cnt += 1
    print(cnt)
    print(temp)
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
c = {}
#for i in range(n):
 # c[a[i]] = c.get(a[i], 0) + 1

prime_bool = [True]*(max(a)+1)
prime_bool[0] = False
count = 0
for p in sorted(a):
  if prime_bool[p]:
    #if c[p] == 1:
     # count += 1
    #print(p)
    for j in range(2*p, max(a)+1, p):
      prime_bool[j] = False

print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
OKlist = [0]*(10**6+100)
A.sort()
for i in range(len(A)-1):
    if A[i] == A[i+1]:
        OKlist[A[i]] += 1
    elif OKlist[A[i]] == 0:
        for j in range(1,10**6+10):
            if A[i]*j > 10**6:
                break
            else:
                OKlist[A[i]*j] += 1
    else:
        OKlist[A[i]] += 1
OKlist[max(A)] += 1
cnt = 0
for i in A:
    if OKlist[i] == 1:
        cnt += 1
        
        
print(cnt)

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
a = np.sort(np.array(list(map(int, input().split()))))
max_num = np.max(a)+1
dp = np.array([True]*(max_num))

if np.all(a==a[0]):
    print(0)
elif np.count_nonzero(a==1)  == 1:
    print(1)
else:
    for i in range(1,max_num):
        if dp[i] and i in a:
            for j in np.arange(i*2, max_num, i):
                dp[j] = False
        elif np.count_nonzero(a==i) >1:
            dp[i] = False
    print(np.count_nonzero(dp[np.unique(a)] == True))

Submission status: Wrong Answer

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

if n==1:
    print(1)
elif len(set(a))==1:
    print(0)
elif 1 in a:
    print(1)
else:
    counter=0
    for i in range(len(a)):
        for j in (range(i)):
            if a[i]%a[j]==0:
                break
        else:
            counter+=1
    print(counter)

Submission status: Wrong Answer

Solution code:
import numpy as np

N = int(input())
A = list(map(int,input().split()))
A = sorted(A)
M = 10**6
Cnt = np.zeros(M)
for ai in A:
    j = ai
    while j < M:
        Cnt[j-1]+=1
        j+=ai

        
ans = 0
for ai in A:
    if Cnt[ai-1] == 1:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
li = list(map(int,input().split()))
cnt = 0

cnt_li = [0] * (10 ** 6)

for i in li:
    for j in range(i,10**6+1,i):
        if cnt_li[j-1] > 1:
            break
        else:
            cnt_li[j-1] += 1

for k in li:
    if cnt_li[k-1] == 1:
        cnt += 1

print(cnt)

Submission status: Wrong Answer

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

if len(set(a))==1:
    print(0)
elif 1 in a:
    print(1)
else:
    counter=0
    for i in range(len(a)):
        for j in (range(i)):
            if a[i]%a[j]==0:
                break
        else:
            counter+=1
    print(counter)

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
a = np.sort(np.array(list(map(int, input().split()))))
max_num = np.max(a)+1
dp = np.array([True]*(max_num))

if np.all(a==a[0]):
    print(0)
elif np.count_nonzero(a==1)  == 1:
    print(1)
else:
    for i in range(1,max_num):
        if dp[i] and i in a:
            for j in np.arange(i*2, max_num, i):
                dp[j] = False
    print(np.count_nonzero(dp[np.unique(a)] == True))

Submission status: Wrong Answer

Solution code:
if __name__ == "__main__":
    n = int(input())
    l_a = list(map(int, input().split()))
    s_a = list(set(l_a))

    s_a.sort()

    dub_a = [0]*max(s_a)

    for i in l_a:
        dub_a[i-1] += 1

    dp = [1]*max(s_a)

    for i in s_a:
        if i*2 > len(dp):
            pass
        elif dp[2*i-1] == 0:
            pass
        else:
            for j in range(2*i-1, len(dp), i):
                dp[j] = 0


    count = 0
    for i in l_a:
        if dp[i-1]==1 and dub_a[i-1]==1:
            count += 1
    print(count)

Submission status: Wrong Answer

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

if len(a)==1:
    print(0)
elif 1 in a:
    print(1)
else:
    counter=0
    counter_set=set()
    for i in range(len(a)):
        for j in (range(i)):
            if a[i]%a[j]==0:
                break
        else:
            counter+=1
            counter_set.add(a[i])
    print(counter)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    A = sorted(A)
    arr = [False]*(10**6+1)
    flag = [False]*(10**6+1)
    size = len(A)
    for a in A:
        if not arr[a]:
            arr[a] = True
        else:
            if not flag[a]:
                size -= 1
                flag[a] = True
            size -= 1
    # 同じ数は削除しておく
    i = 0
    while i<size+1:
        for j in range(i+1,size):
            if arr[A[j]] and A[j]%A[i]==0:
                arr[A[j]] = False
                size -= 1
        i += 1
    print(size)

main()

Submission status: Wrong Answer

Solution code:
import numpy as np

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

non_divisible = np.ones(a[-1]+1, dtype=np.int8)
non_divisible[0] = 0
for i in range(n):
    if i != 0 and a[i] == a[i-1]:
        continue
    non_divisible[a[i]*2::a[i]] = 0

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

print(res if res != 1 else 0)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())))
MA = (max(a) + 1)
ans = [0] * MA

from collections import Counter
ca = Counter(a)
for i in range(n):
    if ca[a[i]] > 1:
        continue
    for j in range(a[i],MA,a[i]):
        ans[j] += 1
        
print(sum(ans[i]==1 for i in a if ca[i]==1))

Submission status: Wrong Answer

Solution code:
if __name__ == "__main__":
    n = int(input())
    l_a = list(map(int, input().split()))
    s_a = list(set(l_a))

    s_a.sort()

    dp = [1]*max(s_a)

    for i in s_a:
        if i*2 > len(dp):
            pass
        elif dp[2*i-1] == 0:
            pass
        else:
            for j in range(2*i-1, len(dp), i):
                dp[j] = 0


    count = 0
    for i in l_a:
        if dp[i-1]==1:
            count += 1
    if len(l_a) > len(s_a):
        count  -= len(l_a)-len(s_a)+1
    print(count)

Submission status: Wrong Answer

Solution code:
import sys

N = int(input())

if N == 1:
    print(1)
    sys.exit()
    
A = sorted(set(map(int, input().split())))

if len(A) == 1:
    print(0)
    sys.exit()
    
max = A[-1]
memo = ['Y'] * (10**6+1)
ans = 0
 
for i, A_i in enumerate(A):
    if memo[A_i] == 'N':
        continue
    for j in range(A_i, max+1, A_i):
        memo[j] = 'N'
    ans += 1
    
print(ans)

Submission status: Wrong Answer

Solution code:
import collections

n = int(input())
a = list(map(int, input().split()))
c = collections.Counter(a)
data = sorted(list(set(a)))
prime_bool = [True]*(max(a)+1)
prime_bool[0] = False
count = 0
for i in range(len(data)):
  p = data[i]
  if prime_bool[p]:
    if c[i] == 1:
      count += 1
    #print(p)
    for j in range(2*p, max(a)+1, p):
      prime_bool[j] = False



print(count)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    A = sorted(A)
    arr = [False]*(10**6+1)
    flag = [False]*(10**6+1)
    size = len(A)
    for a in A:
        if not arr[a]:
            arr[a] = True
        else:
            if not flag[a]:
                size -= 1
                flag[a] = True
            size -= 1
    # 同じ数は削除しておく
    i = 0
    while i<size:
        for j in range(i+1,size):
            if arr[A[j]] and A[j]%A[i]==0:
                arr[A[j]] = False
                size -= 1
        i += 1
    print(size)

main()

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
a = np.sort(np.array(list(map(int, input().split()))))
max_num = np.max(a)+1
dp = np.array([True]*(max_num))

if np.all(a==a[0]):
    print(0)
else:
    for i in range(1,max_num):
        if dp[i] and i in a:
            for j in np.arange(i*2, max_num, i):
                dp[j] = False
    print(np.count_nonzero(dp[a] == True))

Submission status: Wrong Answer

Solution code:
a = int(input())
b = list(map(int,input().split()))
#A1 が割り切れる場合を探す
#割り切れたらA1は元の除外
#A2が割り切れる場合を探す
#割り切れなかったらA2は「割り切れないリスト」に追加、元のリストから除外
#割り切れないリストの個数をカウントする
div_try = []
cant_div = []
for num_1 in range(0,a-1):
  for num_2 in range(num_1+1,a):
    #割り切れるのか確認
    if b[num_1] == b[num_2]:
      div_try.append(True)
    else:
      if b[num_1] % b[num_2] == 0:
        #割り切れたらTrueを結果として保持
        div_try.append(True)
      else:
        #割り切れなかったらFalseを結果として保持
        div_try.append(False)
      #一回も割り切れなかったら、割り切れてないリストに数字を追加する
  if (True not in div_try):
    cant_div_num = b[num_1]
    cant_div.append(cant_div_num)
  div_try = []
#割り切れないリストの個数をカウントする
print(len(set(cant_div)))

Submission status: Wrong Answer

Solution code:
try:
  n  = int(input())
  As = list(map(int, input().split()))
  ans = 0
  
  for i in range(n):
    flag = True
    for j in range(n):
      if i == j:
        continue
       
      if As[i] < 2*As[j]:
        continue
      
      if As[i] % As[j] == 0:
        flag = False
        break
    if flag:
      ans += 1
  print(ans)
except EOFError:
  print(x)

Submission status: Wrong Answer

Solution code:
import bisect as bc

N = 2*10**5
A = [1 for i in range(N)]
A[0] = 10**6
 
A.sort()
 
dp = [True for _ in range(A[-1]+1)]
finished = [False for _ in range(A[-1]+1)]
 

for i in range(N):
    if not finished[A[i]]:
        finished[A[i]] = True
        ai = A[i]
        for j in range(2,A[-1]+1):
            if ai*j > A[-1]:
                break
            dp[ai*j] = False

ans = 0
for i in range(N):
    if dp[A[i]]:
        if bc.bisect_right(A,A[i]) - bc.bisect_left(A,A[i]) == 1:
            ans += 1
 
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
count = 0
wa = []
while a != []:
    t = a[0]
    if len(a) == 1:
        wa.append(t)
    elif a[0] == a[1]:
        wa.append(t)
    han = int(max(a)/t)+2
    bai = [i*t for i in range(1, han)]
    a = [i for i in a if i not in bai]
    

print(len(wa))

Submission status: Wrong Answer

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

l = sorted(a)
f = [1] * n
for i in range(len(l)):
    for j in range(i + 1, len(l)):
        if l[j] % l[i] == 0:
            f[j] = 0
        if l[i] == l[j]:
            f[i] = 0
    l = [l[k] for k in range(len(l)) if f[k] == 1]
print(sum(f))

Submission status: Wrong Answer

Solution code:
import collections

n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
c = collections.Counter(a)
data = sorted(list(set(a)))
prime_bool = [True]*(max(a)+1)
prime_bool[0] = False

for i in range(len(data)):
  p = data[i]
  if prime_bool[p]:
    #print(p)
    for j in range(2*p, max(a)+1, p):
      prime_bool[j] = False

count = 0
for i in range(len(prime_bool)):
  if prime_bool[i]:
    if c[i] == 1:
      count += 1
#print(count)
print(prime_bool)

Submission status: Wrong Answer

Solution code:
try:
  n  = int(input())
  As = list(map(int, input().split()))
  ans = 0
  
  for i in range(n):
    flag = True
    for j in range(n):
      if i == j:
        continue
       
      if As[i] > 2*As[j]:
        continue
      
      if As[i] % As[j] == 0:
        flag = False
        break
    if flag:
      ans += 1
  print(ans)
except EOFError:
  print(x)

Submission status: Wrong Answer

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
# from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint
# from statistics import mean,median,mode

INF = float("inf")

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    # lsはソート済みであること
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

def I():
    return int(input())

def MI():
    return map(int,input().split())

def RI():
    return list(map(int,input().split()))

def CI(n):
    return [ int(input()) for _ in range(n) ]

def LI(n):
    return [ list(map(int,input().split())) for _ in range(n) ]

def S():
    return input()

def MS():
    return input().split()

def RS():
    return list(input().split())

def CS(n):
    return [ input() for _ in range(n) ]

def LS(n):
    return [ list(input().split()) for _ in range(n) ]

n = I()
a = RI()

a.sort()

if 1 in a:
    c = mycount(a,1)
    if c==1:
        print(1)
        exit()
    else:
        print(0)
        exit()

na = []
for i in a:
    c = mycount(a,i)
    if c==1:
        na.append(i)
    else:
        pass

a = copy(na)

if len(a)==0:
    print(0)
    exit()

a.sort()

M = max(a)

# nまでの自然数が素数かどうかを表すリストを返す
# Sieve of Eratosthenes
def makePrimeChecker(n):
    isPrime = [True] * (n + 1)
    isPrime[0] = False
    isPrime[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if isPrime[i]:
            for j in range(i * i, n + 1, i):
                isPrime[j] = False
    return isPrime

dp = [True]*(M+1)

# for i in a:
#     dp[i] = True

for i in a:
    if dp[i]:
        for j in range(i+i,M+1,i):
            dp[j] = False

count = 0

# print(dp)

for i in a:
    if dp[i]:
        # print(i)
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
a = np.sort(np.array(list(map(int, input().split()))))
max_num = np.max(a)+1
dp = np.array([True]*(max_num))

if np.all(a==a[0]):
    print(0)
elif np.count_nonzero(a==1)  == 1:
    print(1)
else:
    for i in range(1,max_num):
        if dp[i] and i in a:
            for j in np.arange(i*2, max_num, i):
                dp[j] = False
    print(np.count_nonzero(dp[a] == True))

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
 
N = int(input())
 
 
if N == 1:
    print(1)
    sys.exit()
 
A = set(map(int, input().split()))
 
if len(A) == 1:
    print(0)
    sys.exit()
 
A = np.array(sorted(A))
B = np.array([A[0]])
 
for i in range(len(A)-1):
    if np.all(A[i+1] % B != 0):
        B = np.append(B, A[i+1])
print(len(B))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
counter_set=set()
a=list(set(a))
a.sort()
if len(set(a))==1:
    print(0)
elif 1 in a:
    print(1)
else:
    for j in range(len(a)):
        for i in range(2, int(a[j]**0.5)+1):
            if a[j] % i == 0:
                if i in counter_set:
                    break
                if i != a[j] // i:
                    if a[j]//i in counter_set:
                        break
        else:
            counter_set.add(a[j])
                
    print(len(counter_set))

Submission status: Wrong Answer

Solution code:
import numpy as np

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

Cnt = np.zeros(max(A))
for n in range(N):
    if A.count(A[n])>1:
        Cnt[A[n]-1] =2
    i=1
    while A[n]*i < max(A):
        if Cnt[A[n]*i-1] < 2:
            Cnt[A[n]*i-1] += 1
        i+=1

count = 0
for ai in A:
    if Cnt[ai-1]==1:
        count+=1
print(count)

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
a = np.sort(np.array(list(map(int, input().split()))))
max_num = np.max(a)+1
dp = np.array([True]*(max_num))

if np.all(a==a[0]):
    print(0)
else:
    for i in range(1,max_num):
        if dp[i] and i in a:
            for j in np.arange(i*2, max_num, i):
                dp[j] = False
    print(dp)
    print(np.count_nonzero(dp[a] == True))

Submission status: Wrong Answer

Solution code:
import numpy as np

def sieve_of_erastosthenes(N,A):
  input_list = [True for i in range(N)]
  sqrt = np.sqrt(A[-1])

  for i in range(len(A)): 
    if A[i] >= sqrt:
      if A[i]==A[-1]:
        input_list[i]=False
      if A[i]<A[-1] or i==len(A)-1:
        return input_list

    for s in range(1,int(A[-1]/A[i])+1): 
      if s*A[i] in A:
        j=A.index(s*A[i])
        if i!=j:
          input_list[j] = False


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


input_list = sieve_of_erastosthenes(N,A)
ans_list = [1 for i, b in enumerate(input_list) if b == True]
print(sum(ans_list))

Submission status: Wrong Answer

Solution code:
N = int(input())
#N = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
A2 = list(range(len(A)))
C = [True]*len(A)
for i in range(len(A)):
    if C[i]==False:
        continue
    a=A[i]
    a_list = [v for v in A2 if C[v] == True]
    A2=a_list[:]
    for j in range(A2.index(i)+1, len(A2)):
        if A[A2[j]]%a==0:
            C[A2[j]] = False
count = len([i for i in C if i==True])
if A[0] in A[1:]:
    count-=1
print(count)

Submission status: Wrong Answer

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

# ダブってる数
rm = 0
for i in A:
    if A.count(i) != 1:
        rm += 1

# 解説動画にあったやり方
T = [0]*(10**6+1)
for i in A:
    j = 1
    while(i*j <= 10**6):
        T[i*j] += 1
        j += 1

ans = -rm
for i in A:
    if T[i] == 1:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
_,*p=map(int,open(0).read().split())
p={*p}
print(len(p-{*[t for t in p for s in p if t%s==0 and t!=s]}))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def resolve():
	N = int(input())
	A = set(map(int, input().split()))
	if len(A)<2:
		print(0)
	else:
		Y = 0
		while True:
			Y+=1
			amin = min(A)
			A = list(filter(lambda x: x%amin>0, A))
			if len(A)<2:
				break
		print(Y+len(A))
resolve()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
count = 0
A.sort()
c=0
for k in range(len(A)-1):
    if A[k] == A[k+1]:
        del A[k]
        A.insert(0,0)
        c+=1
        if k <len(A)-2:
            if A[k+1] != A[k+2]:
                del A[k+1]
                A.insert(0,0)
                c+=1
        else:
            del A[k+1]
            A.insert(0,0)
            c+=1
del A[:c]
if len(A)>0:
    saidai = A[-1]
else:
    saidai=0
#print(A)
foo = [0 for k in range(saidai+1)]
for k in range(len(A)):
    if foo[A[k]] == 1:
        continue
    else:
        count+=1
        for j in range(A[k], saidai+1, A[k]):
            foo[j] = 1
print(count)

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
a = np.sort(np.array([int(x) for x in input().split()]))
max_num = np.max(a)+1
dp = np.array([True]*(max_num))

if np.all(a==a[0]):
    print(0)
elif np.count_nonzero(a==1)  == 1:
    print(1)
else:
    for i in range(1,max_num):
        if dp[i] and i in a:
            for j in np.arange(i*2, max_num, i):
                dp[j] = False
    print(dp)
    print(np.count_nonzero(dp[a] == True))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
count = 0
A.sort()
c=0
for k in range(len(A)-1):
    if A[k] == A[k+1]:
        del A[k]
        A.insert(0,0)
        c+=1
        if k <len(A)-2:
            if A[k+1] != A[k+2]:
                del A[k+1]
                A.insert(0,0)
                c+=1
        else:
            del A[k+1]
            A.insert(0,0)
            c+=1
del A[:c]
if len(A)>0:
    saidai = A[-1]
else:
    saidai=0
print(A)
foo = [0 for k in range(saidai+1)]
for k in range(len(A)):
    if foo[A[k]] == 1:
        continue
    else:
        count+=1
        for j in range(A[k], saidai+1, A[k]):
            foo[j] = 1
print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
M=max(a)
ok = [0]*(M+1)
a.sort()
for i in range(n):
    ok[a[i]] += 1

for i in range(n):
    if ok[a[i]] == 1:
        for g in range(a[i], M+1, a[i]):
            if g != a[i]:
                ok[g] = 0

print(ok.count(1))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = sorted(map(int, input().split()), reverse=False)
dp = [0] * (max(A)+1)

for i in range(N):
    if dp[A[i]] == 0:
        dp[A[i]] = 1
        for j in range(i+1, N):
            if dp[A[j]] == 0 and A[j] % A[i] == 0:
                dp[A[j]] = 2
print(dp.count(1))

Submission status: Wrong Answer

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
# from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint
# from statistics import mean,median,mode

INF = float("inf")

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    # lsはソート済みであること
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

def I():
    return int(input())

def MI():
    return map(int,input().split())

def RI():
    return list(map(int,input().split()))

def CI(n):
    return [ int(input()) for _ in range(n) ]

def LI(n):
    return [ list(map(int,input().split())) for _ in range(n) ]

def S():
    return input()

def MS():
    return input().split()

def RS():
    return list(input().split())

def CS(n):
    return [ input() for _ in range(n) ]

def LS(n):
    return [ list(input().split()) for _ in range(n) ]

n = I()
a = RI()

a.sort()

if 1 in a:
    c = mycount(a,1)
    if c==1:
        print(1)
        exit()
    else:
        print(0)
        exit()

na = []
for i in a:
    c = mycount(a,i)
    if c==1:
        na.append(i)
    else:
        pass

a = copy(na)

if len(a)==0:
    print(0)
    exit()

a.sort()

M = max(a)

# nまでの自然数が素数かどうかを表すリストを返す
# Sieve of Eratosthenes
def makePrimeChecker(n):
    isPrime = [True] * (n + 1)
    isPrime[0] = False
    isPrime[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if isPrime[i]:
            for j in range(i * i, n + 1, i):
                isPrime[j] = False
    return isPrime

dp = [False]*(M+1)

for i in a:
    dp[i] = True

for i in range(2,M+1):
    if dp[i]:
        for j in range(i+i,M+1,i):
            dp[j] = False

count = 0

# print(dp)

for i in a:
    if dp[i]:
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
# from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint
# from statistics import mean,median,mode

INF = float("inf")

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    # lsはソート済みであること
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

def I():
    return int(input())

def MI():
    return map(int,input().split())

def RI():
    return list(map(int,input().split()))

def CI(n):
    return [ int(input()) for _ in range(n) ]

def LI(n):
    return [ list(map(int,input().split())) for _ in range(n) ]

def S():
    return input()

def MS():
    return input().split()

def RS():
    return list(input().split())

def CS(n):
    return [ input() for _ in range(n) ]

def LS(n):
    return [ list(input().split()) for _ in range(n) ]

n = I()
a = RI()

a.sort()

if 1 in a:
    c = mycount(a,1)
    if c==1:
        print(1)
        exit()
    else:
        print(0)
        exit()

na = []
for i in a:
    c = mycount(a,i)
    if c==1:
        na.append(i)
    else:
        pass

a = copy(na)

if len(a)==0:
    print(0)
    exit()

a.sort()

M = max(a)

# nまでの自然数が素数かどうかを表すリストを返す
# Sieve of Eratosthenes
def makePrimeChecker(n):
    isPrime = [True] * (n + 1)
    isPrime[0] = False
    isPrime[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if isPrime[i]:
            for j in range(i * i, n + 1, i):
                isPrime[j] = False
    return isPrime

dp = [False]*(M+1)

for i in a:
    dp[i] = True

for i in range(1,M+1):
    if dp[i]:
        for j in range(i+i,M+1,i):
            dp[j] = False

count = 0

# print(dp)

for i in a:
    if dp[i]:
        count += 1

print(count)

Submission status: Wrong Answer

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

flg = [True for _ in range(10 ** 6 + 1)]
for i in range(n-1):
    if a[i] == a[i+1]:
        flg[a[i]] = False

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

        tmp = 1
        while tmp * a[i] <= 10 ** 6:
            flg[tmp * a[i]] = False
            tmp += 1

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
count = 0
A.sort()
c=0
for k in range(len(A)-1):
    if A[k] == A[k+1]:
        del A[k]
        A.insert(0,0)
        c+=1
        if k <len(A)-2:
            if A[k+1] != A[k+2]:
                del A[k+1]
                A.insert(0,0)
                c+=1
del A[:c]
if len(A)>0:
    saidai = A[-1]
else:
    saidai=0
#print(A)
foo = [0 for k in range(saidai+1)]
for k in range(len(A)):
    if foo[A[k]] == 1:
        continue
    else:
        count+=1
        for j in range(A[k], saidai+1, A[k]):
            foo[j] = 1
print(count)

Submission status: Wrong Answer

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

if len(set(A)) == 1:
    print(0)
    exit()

from collections import Counter
c = Counter(A)

NMAX = 10 ** 6 + 1000
dp = [True] * (NMAX + 1)
for k, v in c.items():
    if not dp[k]:
        continue
    if dp[k]:
        for i in range(k * 2, NMAX + 1, k):
            dp[i] = False
    if v > 1:
        dp[k] = False

count = 0
for k, v in c.items():
    if v > 1: continue
    if dp[k]: count += 1

print(count)

Submission status: Wrong Answer

Solution code:
from collections import Counter

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def main():
    N = ii()
    A = list(mi())
    m = max(A)
    l = [True]*(m+1)
    l[0] = l[1] = False
    c = Counter(A)
    cnt = 0

    A.sort()

    for x in A:
        y = x*2
        while y < m+1:
            l[y] = False
            y += x
    for x in A:
        if l[x] and c[x]==1:
            cnt += 1

    print(cnt)

if __name__ == '__main__':
    main()