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:
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

N = ri()
A = rl()

A.sort()
m = A[-1]

import collections
h = collections.Counter(A)

ans = 0
for a in A:
	if a not in h:
		continue
	if h[a] == 1:
		ans += 1
	for j in range(a, m, a):
		h[j] = 0
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect as bc

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

dp = [True for _ in range(A[-1]+1)]

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
num_list = list(map(int,input().split()))
num_list = np.array(num_list)
count = 0
for i in range(n):
    a = num_list[i]
    num_list_2 = np.delete(num_list, i)
    for b in range(n-1):
        if a % num_list_2[b] == 0:
            break
        elif (b == n-2) and (a % num_list_2[b] != 0):
            count += 1
print(count)

Submission status: Wrong Answer

Solution code:
import numpy as np
 
n = int(input())
a = list(set(map(int, input().split())))
a.sort()
l = len(a)
dp = [True for _ in range(a[-1])]

for i in range(l):
    for j in range(a[i] * 2, a[-1] + 1, a[i]):
        dp[j - 1] = False
#for i, result in enumerate(dp):
#    print(i, result)
#print("#" * 15)
ans = 0
for x in a:
    #print(x)
    if dp[x - 1] == True:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

res = 0
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]) or not non_divisible[a[i]]:
        continue
    non_divisible[a[i]*2::a[i]] = 0
    res += 1
print(res if res != 1 else 0)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

c = Counter(a_list)
divisible = [True] * (10**6+1)
for el, count in c.items():
    if count!=1:
        divisible[el] = False
        continue
    else:
        for i in range(el*2, 10**6+1, el):
            divisible[i] = False
a_list = list(set(a_list))
ans = len(
    [1 for a in a_list if divisible[a]]
)    
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

M = max(A)
dp = [True] * (M + 1)
ans = 0

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

for i in A:
    if dp[i]:
        ans += 1

print(ans)

Submission status: Wrong Answer

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




MAX=max(A)
nums=[0]*(MAX)

ans=0

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

    if nums[a-1]==0:
        ans+=1
        
                
        if a>MAX//2:
            continue
            

    count=1
    num=a
    while num<=MAX:
        nums[num-1]+=1
        count+=1
        num=a*count

    if i!=0:
        if A[i-1]==a:
            continue
    if i!=N-1:
        if a==A[i+1]:
            continue
    
#print(nums)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys 
import math

N = int(sys.stdin.readline().strip())
A = list(map(int, sys.stdin.readline().strip().split()))
A.sort()
# print(A)

counts = [0 for _ in range(10**6 + 1)]
invalid = set()
for i in range(N):
    for j in range(10**6 // A[i]):
        counts[A[i]*j] += 1

ans = 0 
A_set = set(A)
for c in range(10**6+1):
    if c in A_set and counts[c] == 1:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

c = Counter(a_list)
divisible = [True] * (10**6+1)
for el, count in c.items():
    if count!=1:
        divisible[el] = False
        continue
    else:
        for i in range(el*2, 10**6+1, el):
            divisible[i] = False
a_list = list(set(a_list))
ans = len(
    [1 for isDivisible in divisible if isDivisible]
)    
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
dp = [True for _ in range(N)]

A.sort()
p = A[0]
last_check = 0

while p**2 < A[-1]:
    isFirst = True
    isSecond = False
    for i in range(last_check, N):
        if dp[i]:
            if isFirst:
                p = A[i]
                isFirst = False
                isSecond = True
            else:
                if isSecond:
                    last_check = i
                    isSecond = False
                if A[i]%p == 0:
                    dp[i] = False
cnt = 0
for i in dp:
    if i:
        cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
#import numpy as np
N = int(input())
A = list(map(int, input().split()))
A = sorted(A)#わるほう
remove_list = []

kouho = [x for x in set(A) if A.count(x) == 1]

#target = kouho[:]
if kouho != []:
    maxA = max(kouho)

for i in range(len(A)):
    if kouho == []:
        break
    maxN = int(maxA/A[i])
    for n in range(2,maxN+1):
        buf = A[i]*n
        remove_list.append(buf)
            #print(A[i]*n)
#target = kouho[:]
#kouho = list(set(kouho) - set(remove_list))
print(len(kouho))

Submission status: Wrong Answer

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

ans=0
a.sort()
for i in range(n):
    if l[a[i]]:
        for j in range(i,m+1,a[i]):
            l[j]=False
        if i==n-1:
            ans+=1
            break
        if a[i]!=a[i+1]:
            ans+=1
print(ans)

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)
      r+=1
      for j in range(i+1,n+1):
        #print(a[j])
        if af[j] ==False and 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:
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)
    k = 2
    while k*p <= max(a):
      prime_bool[k*p] = False
      k += 1

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:
N=int(input())
A=list(map(int,input().split()))
A=sorted(A)
dp=[True for i in range(max(A)+1)]
for i in A:
    for j in range(2,max(A)+1):
        dp[min(i*j,max(A))]=False
ans=0
for i in A:
    if dp[i]==True:
        ans+=1
if 2 in A and A[0]!=A[1]:
    print(ans+1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

n = int(input())
a = list(map(int, input().split()))
a.sort()
k = len(a)
ok = [0] * k
for i in range(k):
    if i < k - 1 and a[i] == a[i + 1]:
        ok[i] = 1
        ok[i + 1] = 1
        continue
    if a[i] < 2 * 100:
        for j in range(i + 1, k):
            if a[j] % a[i] == 0:
                ok[j] = 1
    else:
        times = 1
        while a[i] * times < a[-1]:
            l = bisect.bisect_left(a, a[i] * times)
            r = bisect.bisect_right(a, a[i] * times)
            if r != l:
                for idx in range(l, r):
                    ok[idx] = 1
            times += 1
# print(ok)
print(len([i for i in ok if i == 0]))
# print(ok) WAはどこ？

Submission status: Wrong Answer

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

ans=0
a.sort()
for i in range(n):
    if l[a[i]]:
        for j in range(i,m,a[i]):
            l[j]=False
        if i==n-1:
            ans+=1
            break
        if a[i]!=a[i+1]:
            ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

n = int(input())
a = list(map(int, input().split()))
a.sort()
k = len(a)
ok = [0] * k
for i in range(k):
    if i < k - 1 and a[i] == a[i + 1]:
        ok[i] = 1
        continue

    if a[i] < 2 * 100:
        for j in range(i + 1, k):
            if a[j] % a[i] == 0:
                ok[j] = 1
    else:   
        times = 1
        while a[i] * times <= a[-1]:
            r = bisect.bisect_left(a, a[i] * times + 1)
            l = bisect.bisect_left(a, a[i] * times)
            if r != l:
                for idx in range(l, r):
                    ok[idx] = 1
            times += 1
print(len([i for i in ok if i == 0]))
# print(ok) WAはどこ？

Submission status: Wrong Answer

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




MAX=max(A)
nums=[0]*(MAX)

ans=0

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

    if nums[a-1]==0:
        ans+=1
        
                
        if a>MAX//2:
            continue
            

    count=1
    num=a
    while num<=MAX:
        nums[num-1]+=1
        count+=1
        num=a*count
    
#print(nums)
print(ans)

Submission status: Wrong Answer

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

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    Amax=A[-1]+1
    dp = [True]*Amax
    ans=0
    a_temp=0
    a_tempcheck=False
    if A[0]==1:
        ans=0
    else:
        for a in A:
            if dp[a]:
                ans+=1
                for i in range(a, Amax, a):
                    dp[i] = False
                a_temp=a
            elif a_temp==a:
                if not a_tempcheck:
                    ans-=1
                    a_tempcheck=Truea_temp=a
            else:
                a_temp=a
                a_tempcheck=False
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math

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

AM = A[-1]
dp = [0]*(AM)

for x in A:
  if dp[x-1] == 0:
    temp = 2 * x
    while temp <= AM:
      dp[temp-1] += 1
      temp += x

for x in A:
  if dp[x-1] == 1:
    ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
dp = [True]*n
 
for i in range(n-1):
    for j in range(1,n-i):
        if a[i+j]%a[i] == 0:
            dp[i+j] = False

print(sum(dp))

Submission status: Wrong Answer

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

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]

avg = sum(A)/len(A)
if avg == A[0]:
	print(0)

else:
	ans = 0
	for a in A:
		for j in make_divisors(a)[1:][:-1]:
			if j in A:
				break
		else:
			ans += 1
	print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

n = int(input())
a = list(map(int, input().split()))
a.sort()
k = len(a)
ok = [0] * k
for i in range(k):
    if ok[i] == 1:
        continue
    if i < k - 1 and a[i] == a[i + 1]:
        ok[i] = 1
    if a[i] < 2 * 100:
        for j in range(i + 1, k):
            if a[j] % a[i] == 0:
                ok[j] = 1
    else:
        times = 1
        while a[i] * times < a[-1]:
            l = bisect.bisect_left(a, a[i] * times)
            r = bisect.bisect_right(a, a[i] * times)
            if r != l:
                for idx in range(l, r):
                    ok[idx] = 1
            times += 1
#print(ok)
print(len([i for i in ok if i == 0]))
# print(ok) WAはどこ？

Submission status: Wrong Answer

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


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)
    return divisors


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

S = list(set(A))

dp = [True] * (A[-1]+1)
max_a = A[-1]
P = []
for i in range(2, int((max_a**0.5//1)+1)):
    index = 1
    if dp[i] == False: continue
    P.append(i)
    while True:
        dp[i*index] = False
        index += 1
        if i * index > max_a: break


for i in range(2, max_a+1):
    if dp[i] == True: P.append(i)


if 1 in A:
    if A.count(1) == 1:
        print(1)
    else:
        print(0)
    exit()

ret = 0
D = collections.Counter(A)

A = list(set(A))
 
for a in D.keys():
    if a in P:
        if D[a] == 1:
            ret += 1
        continue
    
    f = make_divisors(a)
    flag = True
    for f2 in f[2:]:
        if D[f2] == 0: continue
        else: flag = False
    if flag: ret += 1
 
 
print(ret)

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()

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()

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

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

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

print(count)

Submission status: Wrong Answer

Solution code:
# from math import factorial,sqrt,ceil #,gcd
# from itertools import permutations,combinations,combinations_with_replacement
# from collections import deque,Counter
# from bisect import bisect_left
# from heapq import heappush,heappop
from numba import njit,jit
# from functools import lru_cache # 簡単メモ化 @lru_cache(maxsize=1000)
# from fractions import gcd

# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

import numpy as np    # numpy.lcm()
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix
# from scipy.special import comb,perm #permはnPk
# import networkx as nx
# G = Graph()

# slist = "abcdefghijklmnopqrstuvwxyz"
N = int(input())
lisA = list(map(int,input().split()))

@jit
def solve(lisA):
    lisA.sort()
    arrA = np.array(lisA)
    needcheck = np.array([])
    i = 0
    while len(arrA)>0:
        needcheck = np.append(needcheck,arrA[i])
        filter = (arrA % arrA[i] != 0)
        arrA = arrA[filter]

    ans = len(needcheck)
    if lisA[0] in lisA[1:]:
        ans -= 1
    return ans
    
print(solve(lisA))
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する
# print("{:.10f}".format(ans))
# print("{:0=10d}".format(ans))

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)
    k = max(2, p)
    while k*p <= max(a):
      prime_bool[k*p] = False
      k += 1

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:
N = int(input())
A = list(map(int, input().split()))

eratus_list = [True] * (max(A) + 1)
A.sort()
last_a = 0
for A_num in A:
    # print(eratus_list)
    if last_a == A_num:
        continue
    for i in range(A_num+A_num, max(A)+1, A_num):
        eratus_list[i] = False
    last_a = A_num
cnt = 0

for i in range(len(A)):
    # 頭悪い書き方
    if i < len(A) - 1:
        if A[i] == A[i+1]:
            continue
    if i == len(A) - 1:
        if A[i] == A[i-1]:
            continue
    if eratus_list[A[i]]:
        cnt += 1
    last_a = A_num
print(cnt)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[int(x) for x in input().split()]

def func1(a):
    a.sort()
    cnt=0
    chker=[]
    for idx,i in enumerate(a):
        candiv=False
        if idx>0 and i==a[idx-1]:
            candiv=True
            chker.append(i)
        else:
            for j in chker:
                if j*2>i:
                    break
                if i%j==0:
                    candiv=True
                    break
        if candiv==False:
            cnt+=1
            chker.append(i)
    print(cnt)
func1(a)

Submission status: Wrong Answer

Solution code:
import sys
import time
#from collections import deque, Counter, defaultdict
#from fractions import gcd
import bisect
#import heapq
import math
start=time.time()
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
inf = 10**18
MOD = 1000000007
ri = lambda : int(input())
rs = lambda : input().strip()
rl = lambda : list(map(int, input().split()))
n = rl()
a=rl()
a.sort()
b=[0]*2*10**6
for i in a:
    if b[i]==0:
        b[i]=-1
        for j in range(2,10**6):
            if i*j>10**6:
                break
            b[i*j]+=1
cnt = 0
for i in a:
    if b[i]==-1:
        cnt+=1
print(cnt)

Submission status: Wrong Answer

Solution code:
import numpy as np
 
n = int(input())
a = list(set(map(int, input().split())))
a.sort()
l = len(a)
dp = [True for _ in range(a[-1] + 1)]

for i in range(l):
    for j in range(a[i] * 2, a[-1] + 1, a[i]):
        dp[j] = False
#for i, result in enumerate(dp):
#    print(i, result)
#print("#" * 15)
ans = 0
for x in a:
    #print(x)
    if dp[x] == True:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))


n = I()
a = LI()
cnt = [0] * ((10 ** 6) + 1)
unique = []

for i in range((10 ** 6) + 1):
    if cnt[i] == 1:
        unique.append(i)


a = list(set(a))
cnt = [0] * (10 ** 6 + 1)

for ele in a:
    for m in range(ele * 2, (10 ** 6) + 1, ele):
        cnt[m] = 1

ans = 0

for ele in unique:
    if cnt[ele] == 0:
        ans += 1

print(ans)

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)
    k = p+1
    while k*p <= max(a):
      prime_bool[k*p] = False
      k += 1

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:
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()

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

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

print(count)

Submission status: Wrong Answer

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

dp = [True] * (max(a)+1)
a.sort()
cnt = 0
bef = a[0]
for i in range(len(a)):
    if i != 0 and a[i] == bef :
        continue
    if dp[a[i]] :
        for j in range(2,max(a) // a[i]+1):
            dp[a[i] * j] = False
    bef = a[i]

cnt = 0
for i in range(len(a)-1):
    if (not a[i] in a[i+1:]) and a[i]:
        cnt += dp[a[i]]
    
if a[len(a)-1] != a[len(a)-2]:
    cnt += dp[a[len(a)-1]]
print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
dp = [0 for i in range(10 ** 6 + 1)]
a_max = 0
for x in map(int, input().split()):
    a_max = max(a_max, x)
    dp[x] += 1
for i in range(len(dp)):
    if dp[i] == 0:
        continue
    elif dp[i] == 1:
        for j in range(2, (a_max // i + 2)):
            if i * j <= a_max:
                dp[i * j] = 0

print(dp.count(1))

Submission status: Wrong Answer

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

    a.sort()

    dp = [True]*int(1e6)

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


    count = 0
    for i in set(a):
        if len(set(a))==1:
            break
        if dp[i-1]==True:
            count += 1

    print(count)

Submission status: Wrong Answer

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

from collections import Counter
C = dict(Counter(A))  #辞書型にする
print('C',C)
Ckey = list(C.keys())
print('Ckey',Ckey)

B = sorted(Ckey)
print('B',B)

out=0
table=[0]*(10**6)
for i in range(len(B)):
        if table[B[i]-1]==1:
            continue
        elif C[B[i]]==1:
            out+=1
        k=1
        while k*B[i]<=10**6:
            table[k*B[i]-1]=1
            k+=1

print(out)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
if(len(a) == 1):
    print(1)
else:
    a.sort()
    flug = 1
    for j in range(n):
        numl = []
        if(j >= len(a)):
            break
        else:
            flug = 1
            for i in range(j+1, len(a)):
                if(a[i] == a[j] and flug == 1):
                    numl.append(j)
                    flug = 0
                    numl.append(i)
                elif(a[i] % a[j]==0):
                    numl.append(i)
            for i in range(len(numl)):
                a.pop(numl[-(i+1)])
            if(len(a) == 0 or a[j]*2 > a[-1]):
                break
    print(len(a))

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)
    k = p
    while k*p <= max(a):
      prime_bool[k*p] = False
      k += 1

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:
n = int(input())
a = sorted(list(map(int, input().split())))
ans = [True] * n

from collections import Counter

ca = Counter(a)

ma = max(a)

for i in range(n):
    if a[i] in ca:
        if ca[a[i]]>1:
            ans[i] = False
    for j in range(i+1,n):
        if not ans[j]:
            break
        if a[j]==a[i]:
            ans[j] = False
            continue
        if a[j]%a[i]==0:
            ans[j] = False

print(sum(a for a in ans))

Submission status: Wrong Answer

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

st = set(As)
m = As[-1]
rlt = 0
gb = set([])

for i in range(N):
  if i > 1 and As[i] == As[i-1]:
    gb.add(As[i])
    continue
  j = 2
  while As[i]*j <= m:
    if As[i]*j in st:
      gb.add(As[i]*j)
    j += 1

for a in As:
  if a not in gb:
    rlt += 1
    
print(rlt)

Submission status: Wrong Answer

Solution code:
n = int(input())
mapping = [True] * (10**6 + 10)
a = sorted(map(int, input().split()))

last = None
for i in a:
    if i == 1:
        print(1 if len(a) == len(set(a)) else 0)
        exit()
    if i == last:
        mapping[i] = False
        continue
    if not mapping[i]:
        last = i
        continue
    else:
        j = 2
        while i * j < len(mapping):
            mapping[i*j] = False
            j += 1
        last = i

print(sum([1 for i in a if mapping[i]]))

Submission status: Wrong Answer

Solution code:
import collections
n=int(input())
a=list(map(int,input().split()))
a=collections.Counter(a)
b,c=[],[]
for t in a:
  if a[t]==1:
    b.append(t)
  else:
    c.append(t)
if len(b) == 0:
  print(0)
  exit()
b.sort()
bm = b[-1]
ok = [True]*(bm+1)

#if len(c)>0:
#  c.sort()
#  for t in c:
#    if ok[t] == False: continue
#    i = 1
#    while i*t<=bm:
#      ok[i*t]=False
#      i+=1
for t in b:
  if ok[t] == False: continue
  i = 2
  while i*t<=bm:
    ok[i*t]=False
    i+=1
ans = 0
for t in b:
  if ok[t]:
    ans+=1
print(ans)

Submission status: Wrong Answer

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

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    Amax=A[-1]+1
    dp = [True]*Amax
    ans=0
    a_temp=0
    a_tempcheck=False
    if A[0]==1:
        ans=0
    else:
        for a in A:
            if dp[a]:
                ans+=1
                for i in range(a, Amax, a):
                    dp[i] = False
                a_temp=a
            elif a_temp==a:
                if not a_tempcheck:
                    ans-=1
                    a_tempcheck=True
            else:
                a_tempcheck=False
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))


n = I()
a = LI()
# 0 ~ 10 ** 6 + 1 までの数のaでの出現回数
cnt = [0] * ((10 ** 6) + 1)
unique = []

for i in range((10 ** 6) + 1):
    if cnt[i] == 1:
        unique.append(i)


a = list(set(a))  # 同じ数を排除した a
cnt = [0] * (10 ** 6 + 1)  # 0 ~ 10 ** 6 + 1 までの数の a における出現していないか/したか

# 計算量: O(n * log 10**6)
for ele in a:
    # ele 自身以外の ele の倍数について、印をつける
    for m in range(ele * 2, (10 ** 6) + 1, ele):
        cnt[m] = 1

ans = 0

for ele in unique:
    if cnt[ele] == 0:
        ans += 1

print(ans)