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
from collections import Counter


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)

MOD = 10 ** 9 + 7
INF = float("inf")


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

    S = list(count.keys())
    double = []
    for s in S:
        if count[s] > 2:
            double.append(s)
    double = set(double)
    S = set(S)
    if 1 in S:
        print(1)
        return

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

        # divisors.sort()
        return divisors

    answer = 0
    for a in A:
        if a in double:
            continue

        divisors = make_divisors(a)

        cnt = 0
        for div in divisors:
            if div in S:
                break
            else:
                cnt += 1

        if cnt == len(divisors):
            answer += 1
    print(answer)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
M = int(input())
A=list(map(int,input().split()))
A.sort()
ma=A[-1]
is_prime = [True] * (ma + 1)
for i in A:
    if not is_prime[i]:
        continue
    for j in range(i * 2, ma + 1, i):
        is_prime[j] = False
k=[i for i in range(ma + 1) if is_prime[i]]
N=[]
if len(A)==1:
    print(0)
else:
    if A[0] !=A[1]:
        N.append(A[0])
    for i in range(1,len(A)-1):
        if A[i-1]!=A[i] and A[i]!=A[i+1]:
            N.append(A[i])
    if A[len(A)-2] != A[len(A)-1]:
        N.append(A[len(A)-1])
    s=set(k) & set(N)
    print(len(s))

Submission status: Wrong Answer

Solution code:
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    N = int(input())
    A = list(map(int, input().split()))

    #output
    from collections import Counter
    M = pow(10, 6) + 1
    B = [True] * (M+1)
    A = sorted(set(A))
    C = Counter(A)

    answer = 0
    for a in A:
        if C[a] > 1:
            continue
        elif B[a]:
            answer += 1
            for j in range(a, M, a):
                B[j] = False

    print(answer)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# O(N*sqrt(A))
n,*a=map(int,open(0).read().split())
from collections import defaultdict, deque

dd=defaultdict(set)

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]

for q in a:
    dd[q]=set(make_divisors(q))
cnt=0
a.sort()
b=deque(a)
while b:
    p=b.pop()
    if len(dd[p]&set(b))==0:
        cnt+=1
print(cnt)

Submission status: Wrong Answer

Solution code:
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    N = int(input())
    A = list(map(int, input().split()))

    #output
    from collections import Counter
    M = max(A) + 1
    B = [True] * (M+1)
    A = sorted(A)
    C = Counter(A)

    answer = 0
    for a in A:
        if C[a] > 1:
            continue
        elif B[a]:
            answer += 1
            for j in range(a, M+1, a):
                B[j] = False

    print(answer)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
used = [0 for _ in range(int(1e6+1))]

def main():
    ans = 0
    for i in A:
        used[i] += 1
        for j in range(i+i, len(used), i):
            if used[j] != 0:
                break
            used[j] += 1
    for a in A:
        if used[a] == 1:
            ans += 1
    print(ans)
main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
Amax = A[-1]
dp = [1]*(Amax+1)
ans = 0
for i in range(len(A)):
  p = A[i]
  if dp[p] == 1:
    ans += 1
    for q in range(Amax//p+1):
      dp[p*q] = 0
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
Amax = A[-1]
dp = [1]*(Amax+1)
ans = 0
for i in range(len(A)):
  p = A[i]
  if dp[p] == 1:
    ans += 1
    for q in range(Amax//p+1):
      dp[p*q] = 0
print(ans)
print(dp)

Submission status: Wrong Answer

Solution code:
M = int(input())
A=list(map(int,input().split()))
A.sort()
ma=A[-1]
is_prime = [True] * (ma + 1)
for i in A:
    if not is_prime[i]:
        continue
    for j in range(i * 2, ma + 1, i):
        is_prime[j] = False
k=[i for i in range(ma + 1) if is_prime[i]]
N=[A[0]]
for i in range(1,len(A)):
    if A[i-1]!=A[i]:
        N.append(A[i])    
s=set(k) & set(N)
print(len(s))

Submission status: Wrong Answer

Solution code:
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    N = int(input())
    A = list(map(int, input().split()))

    #output
    from collections import Counter
    M = max(A) + 1
    B = [True] * (M)
    A = sorted(A)
    C = Counter(A)

    answer = 0
    for a in A:
        if C[a] > 1:
            continue
        elif B[a]:
            answer += 1
            for j in range(a, M, a):
                B[j] = False

    print(answer)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    N = int(input())
    A = list(map(int, input().split()))

    #output
    from collections import Counter
    M = max(A) + 1
    B = [True] * (M)
    A = sorted(A)
    C = Counter(A)

    answer = 0
    for a in A:
        if a == 1:
            print(0)
            break
        if C[a] > 1:
            continue
        elif B[a]:
            answer +=1
            for j in range(a, M, a):
                B[j] = False
        elif not B[a]:
            continue

    print(answer)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import copy
N = int(input())
c=list(map(int, input().split()))
count = 0
for i in range(N):
  b = []
  m = copy.copy(c)
  a = c[i]
  m.pop(i)
  m.sort()
  for j in range(N-1):
    if m[j]>c[i]:
      count+=1
      break
    elif c[i]%m[j]!=0:
      continue
    elif c[i]%m[j]==0:
      break
      
print(count)

Submission status: Wrong Answer

Solution code:
import collections
import math
import sys
sys.setrecursionlimit(10**6)
 
#  = input()
n  = int(input())
#  = map(int, input().split())
l  = list(map(int, input().split()))
#  = [int(input()) for i in range(N)]
#
c = collections.Counter(l)
l = sorted(c.keys())

if len(l) == 1:
    print(0)
    exit()

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

sosu = []
sosu.append(l.pop(0))
x = sosu[-1]
i1 = 0
while i1 < math.sqrt(len(l)):
    i1 += 1
    i = 0
    while i < len(l):
        #print(x, i, l)
        if l[i] % x == 0:
            l.pop(i)
        else:
            i += 1
    
    sosu.append(l.pop(0))
    x = sosu[-1]
  
#print(sosu, l)
print(len(sosu) + len(l))

Submission status: Wrong Answer

Solution code:
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    N = int(input())
    A = list(map(int, input().split()))

    #output
    from collections import Counter
    M = max(A) + 1
    B = [True] * (M)
    A = sorted(A)
    C = Counter(A)

    answer = 0
    for a in A:
        if C[a] > 1:
            continue
        elif B[a]:
            answer +=1
            for j in range(a, M, a):
                B[j] = False
        elif not B[a]:
            continue

    print(answer)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n = II()
    a = LI()
    dp = [True] * (10 ** 6 + 1)
    a.sort()
    ans = 0
    for i in a:
        if dp[i]:
            ans += 1
            dp[i] = False
            
            for j in range(i * 2, 10 ** 6 + 1, i):
                dp[j] = False
    print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
n=int(input())

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

a.sort()

if n > 1:
    if a[0] == a[1]:
        ans = 0
    else:
        ans = 1
else:
    print(1)
    exit()

for i in range(1,n):
    flag = True
    for j in range(i):
        if a[i] % a[j] == 0:
            flag = False
            break
        if int(a[i]**0.5)+1 < a[j]:  
            break
    if i == n-1:
        if flag and a[i] != a[i-1]:
            ans += 1
    else:
        if flag and a[i] != a[i-1] and a[i] != a[i+1]:
            ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
import math
import sys
sys.setrecursionlimit(10**6)
 
#  = input()
n  = int(input())
#  = map(int, input().split())
l  = list(map(int, input().split()))
#  = [int(input()) for i in range(N)]
#
c = collections.Counter(l)
l = sorted(c.keys())

if len(l) == 1 or l[0] == 1:
    print(0)
    exit()

sosu = []
sosu.append(l.pop(0))
x = sosu[-1]
i1 = 0
while i1 < math.sqrt(len(l)):
    i1 += 1
    i = 0
    while i < len(l):
        #print(x, i, l)
        if l[i] % x == 0:
            l.pop(i)
        else:
            i += 1
    
    sosu.append(l.pop(0))
    x = sosu[-1]
  
#print(sosu, l)
print(len(sosu) + len(l))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())
lstA = []
dctA = {}
for n in input().split():
  i = int(n)
  lstA.append(i)
  if i in dctA:
    dctA[i] += 1
  dctA[i] = 0
lstA.sort()

Submission status: Wrong Answer

Solution code:
import collections
import math
import sys
sys.setrecursionlimit(10**6)
 
#  = input()
#n  = int(input())
#  = map(int, input().split())
#l  = list(map(int, input().split()))
#  = [int(input()) for i in range(N)]
#
n = 5
l = [33, 18, 45, 28, 8, 19, 89, 86, 2, 4]
c = collections.Counter(l)
l = sorted(c.keys())

if len(l) == 1 or l[0] == 1:
    print(0)
    exit()

sosu = []
sosu.append(l.pop(0))
x = sosu[-1]
i1 = 0
while i1 < math.sqrt(len(l)):
    i1 += 1
    i = 0
    while i < len(l):
        #print(x, i, l)
        if l[i] % x == 0:
            l.pop(i)
        else:
            i += 1
    
    sosu.append(l.pop(0))
    x = sosu[-1]
  
print(len(sosu) + len(l))

Submission status: Wrong Answer

Solution code:
import sys
N=int(input())
a=[int(x) for x in input().rstrip().split()]
# s=set(a)
s=[]
a.sort()
ans=0
max_val=max(a)
min_val=min(a)
if 2<=a.count(min_val):
  print(0)
  sys.exit()

for i in a:
  if i in s:
    continue
  ans+=1
  now=i
  cnt=1
  s.append(now)
  while(now*cnt<=max_val):
    cnt+=1
    if now*cnt<=max_val:
      s.append(now*cnt)

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def main():
    n, *a = map(int, open(0).read().split())
    if n == 1:
        print(1)
        return
    a = sorted(a)
    m = max(a) + 1
    l = [0] * m
    for i in a:
        if l[i] > 1:
            continue
        for j in range(i, m, i):
            l[j] = 2
        l[i] -= 1

    ans = sum(l[i] == 1 for i in a)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n, *a = map(int, open(0).read().split())
    if n == 1:
        print(1)
        return

    m = max(a) + 1
    l = [0] * m
    for i in a:
        if l[i] > 1:
            continue
        for j in range(i, m, i):
            l[j] = 2
        l[i] -= 1

    ans = sum(l[i] == 1 for i in a)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = []
c = 0
for n in input().split():
  i = int(n)
  A.append(i)
A.sort()
for i in range(N):
  Ai = A[i]
  if i != N - 1:
    if Ai == A[i + 1]:
      continue
  flg = True
  for j in range(i):
    Aj = A[j]
    q,m = divmod(Ai,Aj)
    if m == 0:
      flg = False
      break
    if q == 1:
      break
  if flg:
    c += 1
print(c)

Submission status: Wrong Answer

Solution code:
def main():
    n, *a = map(int, open(0).read().split())
    if n == 1:
        print(1)
        return

    m = max(a) + 1
    l = [0] * m
    for i in a:
        for j in range(i, m, i):
            l[j] += 2
        l[i] -= 1

    ans = sum(l[i] == -1 for i in a)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def resolve():
    '''
    code here
    '''
    import collections
    N = int(input())
    A_list = [int(item) for item in input().split()]

    A_cnt_dict = dict(collections.Counter(A_list))

    B_list = []
    for i, v in A_cnt_dict.items():
        if i == 1:
            if v == 1:
                B_list.append(i)
                break
            else:
                break

        elif v == 1:
            B_list.append(i)

    B_list.sort()
    cnt = 0

    if B_list:
        dp = [True for item in range(B_list[-1]+1)]
        for item in B_list:
            if dp[item]: 
                cnt += 1
                temp = item
                while temp <= B_list[-1]:
                    dp[temp] = False
                    temp += item

    print(cnt)

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
n,*a=map(int,open(0).read().split())
a.sort()
for i in range(n):
    for j in range(n):
        if i==j or a[j]>a[i]/2:
            continue
        if a[i]%a[j]==0:
            n-=1
            break
print(n)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def resolve():
    '''
    code here
    '''
    import collections
    N = int(input())
    A_list = [int(item) for item in input().split()]

    A_cnt_dict = dict(collections.Counter(A_list))

    B_list = []
    for i, v in A_cnt_dict.items():
        if i == 1:
            if v == 1:
                B_list.append(i)
            else:
                break

        elif v == 1:
            B_list.append(i)

    B_list.sort()
    cnt = 0

    if B_list:
        dp = [True for item in range(B_list[-1]+1)]
        for item in B_list:
            if dp[item]: 
                cnt += 1
                temp = item
                while temp <= B_list[-1]:
                    dp[temp] = False
                    temp += item

    print(cnt)

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

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

ans = 0
A.sort()
#print(A)
for i in range(1,N+1):
  for j in range(1,N+1):
    if A[i-1] == A[j-1]:
      break
    if A[i-1] % A[j-1] == 0 and not i==j:
      break
    if i<j or A[i-1]/2 < A[j-1]:
      
      ans += 1
      break
    if j == N:
    
      ans += 1
    
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
A = list(map(int,input().split()))
aa = np.array(A)
aa = np.sort(aa)
for i in range(len(aa)):
  judge = True
  j = i+1
  while True:
    if len(aa) <= j:
      break
    if aa[j]%aa[i] == 0:
      if aa[j] == aa[i]:
        aa = np.delete(aa,i,0)
      else:
        aa = np.delete(aa,j,0)
    j += 1

print(len(aa))

Submission status: Wrong Answer

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

for i in a:
    cnt[i] += 1
    
unique = []

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

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

for i in unique:
    for j in range(i*2, 10**6 + 1, i):
        cnt[j] = 1
    
ans = 0

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

Submission status: Wrong Answer

Solution code:
def resolve():
    '''
    code here
    '''
    import collections
    N = int(input())
    A_list = [int(item) for item in input().split()]

    A_cnt_dict = dict(collections.Counter(A_list))

    B_list = []
    for i, v in A_cnt_dict.items():
        if v == 1:
            B_list.append(i)

    B_list.sort()
    cnt = 0
    
    if B_list:
        dp = [True for item in range(B_list[-1]+1)]
        for item in B_list:
            if dp[item]: 
                cnt += 1
                temp = item
                while temp <= B_list[-1]:
                    dp[temp] = False
                    temp += item

    print(cnt)

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

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

ans = 0
A.sort()
#print(A)
for i in range(1,N+1):
  for j in range(1,N+1):
      
    if A[i-1] % A[j-1] == 0 and not i==j:
      break
    if i<j or A[i-1]/2 < A[j-1]:
      ans += 1
      break
    if j == N:
      ans += 1
    
print(ans)

Submission status: Wrong Answer

Solution code:
def resolve():
    '''
    code here
    '''

    N = int(input())
    A_list = [int(item) for item in input().split()]
    A_list.sort()
    
    dp = [True for item in range(A_list[-1]+1)]

    cnt = 0
    for item in A_list:
        if dp[item]: 
            cnt += 1
            temp = item
            while temp <= A_list[-1]:
                dp[temp] = False
                temp += item

    print(cnt)

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
import sys, math, itertools, collections, bisect 
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8') 
inf = float('inf') ;mod = 10**9+7 
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n = int(input())
A = list(map(int, input().split()))
cnt = [0]*n
A.sort(reverse=True)
if A.count(A[0]) == len(A):
    print(0)
    exit()
max_A = max(A)
for i in range(n):
    j = 1
    while True:
        if A[i]*j in A:
            cnt[A.index(A[i]*j)] += 1
        else:
            pass
        if A[i]*j > max_A:
            break
        j += 1
print(cnt.count(1))
#print(cnt)

Submission status: Wrong Answer

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

cnt = Counter(p)

ps = set(p)
plst = list(ps)
plst.sort(reverse=True)
temp = plst[:]
jdg = [True]*N
ans = 0
while temp:
    q = temp.pop()
    q2 = jdg.pop()
    if not q2: continue

    for j, i in enumerate(temp):
        if i%q==0: jdg[j]=False
    if cnt[q] == 1: ans += 1
print(ans)

Submission status: Wrong Answer

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

d = {}
for ai in a:
  if ai in d:
    d[ai] += 1
  else:
    d[ai] = 1
d = sorted(d.items())
#print(d)

e = [True for _ in range(maxa+1)]
for ai,c in d:
  if c > 1:
    e[ai] = False
  else:
    for i in range(2,maxa//ai+1):
      e[ai*i] = False

ans = 0
for ai,_ in d:
  if e[ai]:
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jun 14 21:14:26 2020

@author: NEC-PCuser
"""

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

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

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


count = 0
for i in A:
    if a[i - 1] == 1:
        count+=1

print(count)

Submission status: Wrong Answer

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

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


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


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

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

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

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

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

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

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

    print(ans)


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

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

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

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

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

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

    def test_1original_3(self):
        test_input = """90
617 279 402 110 487 288 34 58 989 681 964 387 955 376 821 155 291 282 266 252 189 190 94 765 158 264 631 69 604 366 605 241 560 990 86 683 784 260 373 101 780 54 71 620 173 692 101 344 978 784 520 416 778 973 222 260 847 733 933 837 441 696 363 684 19 405 997 56 42 654 431 7 803 974 910 326 110 846 987 789 569 381 362 1 387 583 279 779 737 349
"""
        output = """1"""
        self.assertIO(test_input, output)


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

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

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int, input().split()))
nux = max(A)
B = set(A)
A.sort()
ans = 0
table = [True]*(nux+1)
for s in B:
    if table[s] == False:
        continue
    if A.count(s) == 1:
        ans += 1
    i = 1
    while i*s <= nux:
        table[i*s] = False
        i += 1

print(ans)

Submission status: Wrong Answer

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

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


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


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

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

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

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

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

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

    print(ans)


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

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

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

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

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

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

    def test_1original_3(self):
        test_input = """90
617 279 402 110 487 288 34 58 989 681 964 387 955 376 821 155 291 282 266 252 189 190 94 765 158 264 631 69 604 366 605 241 560 990 86 683 784 260 373 101 780 54 71 620 173 692 101 344 978 784 520 416 778 973 222 260 847 733 933 837 441 696 363 684 19 405 997 56 42 654 431 7 803 974 910 326 110 846 987 789 569 381 362 1 387 583 279 779 737 349
"""
        output = """1"""
        self.assertIO(test_input, output)


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

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

Submission status: Wrong Answer

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

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


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


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

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

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

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

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

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

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

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

    print(ans)


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

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

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

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

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

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

    def test_1original_3(self):
        test_input = """90
617 279 402 110 487 288 34 58 989 681 964 387 955 376 821 155 291 282 266 252 189 190 94 765 158 264 631 69 604 366 605 241 560 990 86 683 784 260 373 101 780 54 71 620 173 692 101 344 978 784 520 416 778 973 222 260 847 733 933 837 441 696 363 684 19 405 997 56 42 654 431 7 803 974 910 326 110 846 987 789 569 381 362 1 387 583 279 779 737 349
"""
        output = """1"""
        self.assertIO(test_input, output)


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

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