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 glob
import os
import bisect

bn = os.path.basename(__file__).split('.')[0]
dn = os.path.dirname(__file__).split('/')

# 問題ごとのディレクトリのトップからの相対パス
REL_PATH = dn[len(dn)-2] + '\\' + dn[len(dn)-1] + '\\' + bn

# テスト用ファイル置き場のトップ
TOP_PATH = 'C:\\AtCoder'

class Common:

    problem = []
    index = 0

    def __init__(self, rel_path):
        self.rel_path = rel_path

    def initialize(self, path):
        file = open(path)
        self.problem = file.readlines()
        self.index = 0
        return

    def input_data(self):
        try:
            IS_TEST
            self.index += 1
            return self.problem[self.index-1]

        except NameError:
            return input()

    def resolve(self):
        pass

    def exec_resolve(self):
        try:
            IS_TEST
            for path in glob.glob(TOP_PATH + '\\' + self.rel_path + '/*.txt'):
                print("Test: " + path)
                self.initialize(path)
                self.resolve()
                print("\n\n")
        except NameError:
            self.resolve()


class Solver(Common):

    def resolve(self):

        N = int( self.input_data())
        A = list(map(int, self.input_data().split()))
        A_set = set(A)

        A_sorted = sorted(A)

        for a in A_set:
            left = bisect.bisect_left(A_sorted, a)
            right = bisect.bisect_right(A_sorted, a)
            if right - left > 1:
                del A_sorted[left:right]
        index = 0
        remove_list = [0]* (len(A_sorted)+1)

        for index in range(0, len(A_sorted)-1):
            if remove_list[index] == 1:
                continue
            next = bisect.bisect_left(A_sorted, A_sorted[index]*2)
            for i in range(next, len(A_sorted)):
                if A_sorted[i] % A_sorted[index] == 0:
                    remove_list[i] = 1

        count = 0
        for i in remove_list:
            count += (1 - i)
        print(str(count-1))


solver = Solver(REL_PATH)
solver.exec_resolve()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
B = [0]*N
A.sort()

for i in range(len(B)):
  for j in range(i):
    if A[i]%A[j] == 0:
      B[i] = 1
print(N-sum(B))

Submission status: Wrong Answer

Solution code:
n = int(input())
line = sorted(list(map(int,input().split())))
one = 0
for i in range(n):#one 
  if line[i] == 1:
    one += 1
  else:
    break
for i in range(n):#1にする
  for j in range(i+1,n)[::-1]:
    if line[i] != 1:      
      if line[j] == line[i]:
        line[i] = 1
        line[j] = 1
      if line[j] % line[i] == 0:
        line[j] = 1
      if i>one-1 and line[i] == 1:
        break    
linn = sorted(line)
count = 0
for i in range(n):#count
  if line[i] !=1:
    count += 1  
count += one
print(count)

Submission status: Wrong Answer

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())
    N = next(it)
    A = [next(it) for i in range(N)]

    if N == 1:
        print(1)
        return
    if A[0] == 1:
        print(0 if A[1] == 1 else 1)
        return

    ax = max(A)+1
    dp = [0]*ax
    ans = 0
    for i in range(N):
        a0 = A[i]

        dp0 = dp[a0]
        if dp0 == 0:
            dp[a0] = 1
            ans += 1

            for j in range(2*a0, ax, a0):
                if dp[j] & 1:
                    ans -= 1
                dp[j] = 2
        elif dp0 & 1:
            ans -= 1
            dp[a0] ^= 1
    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

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


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

    divisors.remove(n)
    return divisors


N = int(input())
A = list(map(int, input().split()))
X = [0] * (10**6 + 1)
for a in A:
    X[a] += 1
ans = 0
for a in A:
    if X[a] > 1:
        continue
    for d in make_divisors(a)[:-1]:
        if X[d]:
            break
    else:
        ans += 1

print(ans)

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

lisA.sort()
arrA = np.array(lisA)

needcheck = np.array([])
divable = []
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

print(ans)
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する
# print("{:.10f}".format(ans))
# print("{:0=10d}".format(ans))

Submission status: Wrong Answer

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

a = set(A)
if len(a) == 1:
    print(0)
    quit()


MOD = 10**9+7
A.append(MOD)

for i in range(N):
    for j in range(N):
        if i != j:
            if A[i] % A[j] == 0:
                A[i] = MOD

A = set(A)
print(A)
print (len(A)-1)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = lr()
A.sort()
bl = [True] * (A[-1]+1)
answer = 0
for i, a in enumerate(A):
    if i < N-1 and A[i+1] == a:
        bl[a] = False
    elif bl[a]:
        answer += 1
    next = a + a
    while next <= A[-1] and bl[next]:
        bl[next] = False
        next += a

print(answer)

Submission status: Wrong Answer

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

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

count = 1
check = 0
for i in range(1, n):
    check = 0
    for j in range(0, i):
       if a[i] % a[j] == 0:
           break
       else:
           check += 1
           if check == i:
               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()

count = 0

if len(A) != 1:
    for i in A:
        a = i
        flag = 0
        for j in A:
            if a != j:
                if a % j == 0:
                    flag = 1
                    break
        if flag == 0:
            count += 1
    
print(count)

Submission status: Wrong Answer

Solution code:

N=int(input())
A=list(map(int, input().split()))
A=sorted(A)
if max(A)==min(A):
    print(0)
    exit()



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

ans=0

for i in range(N):
    a=A[i]
    
    count=1
    num=a
    while num<=MAX:
        nums[num-1]+=1
        count+=1
        num=a*count
    
ans=0
for a in A:
    if nums[a-1]<=1:
            ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    a = sorted(list(map(int, input().split())))
    pool = set()
    count = 0
    limit = 10 ** 6 // 2 +1
    for i in range(n):
        t = a[i]
        if t in pool:
            continue
        for j in range(1, limit):
            x = t*j
            if x > limit:
                break
            pool.add(x)
        if i == n-1 or (n > i+1 and t != a[i+1]):
            count += 1
    print(count)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math

def isPrime(n):
  if n == 1:
    return False
  for k in range(2, int(math.sqrt(n)) + 1):
    if n % k == 0:
      return False
  return True

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

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

if A[0] == 1 and A[1] == 1:
  print(0)
  exit()
if A[0] == 1 and A[1] != 1:
  print(1)
  exit()

for i in range(N):
  x = A[i]
  if isPrime(x):
    if i - 1 >= 0:
      if x == A[i - 1]:
        cnt -= 1
        continue
    if i + 1 < N:
      if x == A[i + 1]:
        cnt -= 1
        continue
    continue
    
  for j in range(i + 1):
    if j == N:
      break
    y = A[j]
    if x % y == 0:
      cnt -= 1
      break
print(cnt)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
#n=2*10**5
#a=[i+2 for i in range(0,n)]
a.sort()
aa={}
for i in range(0,a[-1]+1):
  aa[i]=0
if a[0]==a[n-1]:
  print(0)
elif a[0]==1:
  print(1)
else:
  ans=0
  while len(a)!=1:
    now=a.pop(0)
    if aa[now]==0:
      ans+=1
      bai=[i*now for i in range(1,a[-1]//now+1)]
      for i in bai:
        aa[i]=1
  if aa[a[0]]==0:
    ans+=1
  print(ans)

Submission status: Wrong Answer

Solution code:
import copy

n = int(input())
al = list(map(int, input().split()))

al.sort()

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

def rmlis(ase, i):
    aset_new = ase.copy()
    x = ase[i]
    rm_cnt = 0

    for j in range(i+1, len(ase)):
        if ase[j]%x == 0:
            aset_new.pop(j - rm_cnt)
            rm_cnt += 1
    return aset_new

flag = True
k = 0
lis = al
while flag:
    lis = rmlis(lis, k)
    if k+1 >= len(lis):
        print(len(lis))
        exit()
    else:

        if lis[-1] < lis[k+1] *2:
            flag = False
            print(len(lis))
            exit()
        else:
            k += 1

Submission status: Wrong Answer

Solution code:
wkN = input()
N = int(wkN)

list1 = input().split()
numlist = []
for i in list1:
  numlist.append(int(i))
  #numlist = list(set(wklist))

count = 0
roopcnt = 0
leng = len(numlist)
#print(numlist)
if leng != 0:
  for i in range(leng):
    for n in range(leng):
      if i == n:
        continue
      if numlist[i] % numlist[n] == 0:
        break
      if n+1 == leng:
        count += 1
print(count)

Submission status: Wrong Answer

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

for i in range(N):
    for j in range(2, 10 ** 6 + 1):
        index = a[i] * j
        if index <= 10 ** 6:
            anstable[index] += 1

cnt = 0
for i in a:
    if anstable[i] == 0:
        cnt += 1

print(cnt)

Submission status: Wrong Answer

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

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

count = 0
while A:
    new = []
    b = A[0]
    for a in A[1:]:
        if a % b > 0: # bで割れなければ続投
            new.append(a)
    A = new
    count += 1


print(count)

Submission status: Wrong Answer

Solution code:
import numpy as np

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

  
n = int(input())
a_list = list(sorted(list(map(int,input().split()))))
sosuu = []
hukusuu = []

for i in range(len(a_list)-1,0,-1):
  if a_list[i] == a_list[i-1]:
    hukusuu.append(i)
    hukusuu.append(i-1)
    
hukusuu = sorted(list(set(hukusuu)),reverse=True)
for i in hukusuu:
  a_list.pop(i)

if len(a_list) == 0:
  print(0)
else:
  a_array = np.array(sorted(a_list))
  while 1:
    if len(a_array) == 0:
      break
    num = a_array[0]
    a_array = np.delete(a_array,0)
    b_array = a_array % num
    a_array = a_array*[b_array>0]
    a_array = a_array[np.nonzero(a_array)]
    sosuu.append(num)

  print(len(sosuu))

Submission status: Wrong Answer

Solution code:
#import numpy as np
#import random
#import time
from collections import defaultdict, Counter

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

def main():
    #N = 20
    #A = [random.randint(1, int(1e6)) for _ in range(int(N))]
    N = int(input())
    A = [int(c) for c in input().split(' ')]
    #t1 = time.time()
    dup_cnt = Counter(A)
    dup = set(x for x in dup_cnt if dup_cnt[x] > 1)
    A_set = set(A)
    if 1 in A_set:
        print('1')
        exit()
    A = list(A_set)
    N = len(A)
    A.sort()
#    B = [factorization(x) for x in A]
#    B.sort()

    d = defaultdict(list)
    B = []
    for x in A:
        x_fac = factorization(x)
        B.append(x_fac)
        for y in x_fac:
            d[y[0]].append(x)
    assert len(A)==len(B)
    #print(A)
    #print(B)
    #print(d)
    not_divided = set()
    for i in range(N):
        bi = A[i]
        bi_fac = B[i]
        can_divide = False
        for y in bi_fac:
            for a in d[y[0]]:
                if bi % a == 0 and bi != a:
                    #print(a,bi)
                    can_divide = True
                    break
                elif a > bi:
                    break
            if can_divide:
                break
        if can_divide or bi in dup:
            continue
        else:
            not_divided.add(bi)
    #print(A)
    #print(dup)
    #print(not_divided)
    print(len(not_divided))
    #print(time.time() - t1)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

if len(a) == 1:
    print(0)
else:
    check = [True for _ in range(10**6 + 5)]
    for i in a:
        now = 2 * i
        while (10**6 > now):
            check[now] = False
            now += i

    ans = 0
    for i in a:
        if check[i]:
            ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys


def Sieve(N, AList):
    AList.sort()
    N_NotDivisible = 0
    index = 0
    while( index < len(AList) ):
        if(len(AList)-index > 1):
            if(AList[index]!= AList[index+1]):
                N_NotDivisible+= 1
                value = AList[index]
                Max = 1
                Indices = []
                for i in range(0, len(AList)-index-1, 1 ):
                    if(AList[index+i+1]%value!=0):
                        Indices.append(AList[index+i+1])
                AList = Indices
            else:
                index = 2
                while(index < len(AList) and AList[index-1] == AList[index]):
                    index += 1

        else:
            N_NotDivisible+= 1
            break
    #print(Mins)
    return N_NotDivisible

if(__name__ == "__main__"):

    N = int( input().strip() )
    AList_str = input().strip().split()

    AList = [0] * N
    for i in range(N):
        AList[i] = int(AList_str[i])
    N_NotDivisible= Sieve(N, AList)
    print(N_NotDivisible)

Submission status: Wrong Answer

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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]


def main():
    N = int(input())
    A = [int(x) for x in input().split()]

    A.sort()

    aset = list(set(A))

    aset.sort()
    ans = 0
    s = set()
    for a in aset:
        divs = make_divisors(a)
        for div in divs:
            if div in s:
                break
        else:
            ans += 1
        s.add(a)

    c = collections.Counter(A)
    for x in c.most_common():
        if x[1] > 1:
            ans -= 1
        else:
            break

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
A=sorted(A)
numCount=0
for i in range(len(A)-1):
    count=0
    for j in range(len(A)-i-1):
        if A[len(A)-i-1]%A[j]==0:
            break
        if j==len(A)-i-2:
            numCount+=1
if N>1:
    if A[0]%A[1]!=0:
        numCount+=1
print(numCount)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
flag = [True] * n
for i, num in enumerate(a):
    if num > a[-1]**0.5:
        break
    if a[(i-1)%n]==num or a[(i+1)%n]==num:
        flag[i] = False
        continue
    for j in range(i+1, n):
        if a[j]%num==0:
            flag[j] = False
counter = 0
for i in range(len(flag)):
    if flag[i]:
        counter += 1
print(counter)

Submission status: Wrong Answer

Solution code:
def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10

    N = II()
    A = LMIIS()
    A.sort()
    ans = 0
    count = defaultdict(int)
    for a in A:
        count[a] += 1
    next_A = deque()
    for a in A:
        if count[a] == 1:
            next_A.append(a)
    A = list(next_A)
    if len(A) == 0:
        print(0)
        return
    if A[0] == 1:
        print(1)
        return


    def make_divisors(n):
        lower_divisors , upper_divisors = deque(),deque()
        for i in range(1,int(n**0.5)+1):
            if n % i == 0:
                lower_divisors.append(i)
                if i != n // i:
                    upper_divisors.appendleft(n//i)
            i += 1
        upper_divisors
        return lower_divisors + upper_divisors




    F = deque()
    for a in A:
        F.append(make_divisors(a))
    ans = 0
    Not_Divisible = [False] * (max(A)+1)
    for f in F:
        for d in f:
            if Not_Divisible[d]:
                break
        else:
            Not_Divisible[f[-1]] = True
            ans += 1
    print(ans)
    dbg(F)
    dbg(Not_Divisible)
    
main()

Submission status: Wrong Answer

Solution code:
FAST_IO = 0
if FAST_IO:
    import io, sys, atexit
    read = iter(sys.stdin.read().splitlines()).next
    sys.stdout = _OUTPUT_BUFFER = io.BytesIO()
    @atexit.register
    def write():
        sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
else:
    read = raw_input
readint = lambda: int(read())
readlist = lambda: map(int, read().split())

####
from collections import Counter
def solve(N, A):
    MAXV = 10 ** 6
    count = Counter(A)
    touch = [False] * (MAXV + 1)
    ans = 0
    for x in sorted(count):
        if not touch[x]:
            ans += 1
            for y in xrange(2 * x, MAXV + 1, x):
                touch[y] = True
    return ans
            
    

print solve(readint(), readlist())

Submission status: Wrong Answer

Solution code:
# coding=UTF-8
from collections import deque
from operator import itemgetter
from bisect import bisect_left, bisect
import itertools
import sys
import math
import numpy as np
import time
sys.setrecursionlimit(10**6)
input = sys.stdin.readline


def main():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    ans = []

    while len(a) != 0:
        now = a[0]
        cnt = 0
        arr = a.copy()
        if now ** 2 > 10 ** 6:
            arr.remove(now)
        else:
            for i in a:
                if i % now == 0:
                    if i == now:
                        cnt += 1
                    arr.remove(i)
            if cnt > 1:
                continue
        ans.append(now)
        a = arr.copy()
    print(len(ans))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
N=int(input())
alist=list(map(int, input().split()))

alist.sort()
#print(alist)
if alist.count(alist[0])==1:
    ans=1
else:
    ans=0
for i in range(1,N):
    a=alist[i]
    aaa=[a]*(i)
    x=np.array(aaa)
    y=np.array(alist[0:i])
    amari=x%y
    #print(x)
    #print(y)
    #print(amari)
    if list(amari).count(0)==0:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:

N=int(input())
A=list(map(int, input().split()))
A=sorted(A)
if max(A)==min(A):
    print(0)
    exit()



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

ans=0

for i in range(N):
    a=A[i]
    if a>MAX//2:
        break
    count=1
    num=a
    while num<=MAX:
        nums[num-1]+=1
        count+=1
        num=a*count
    
ans=0
for a in A:
    if a>MAX//2:
        if nums[a-1]<1:
            ans+=1
    else:
        if nums[a-1]<=1:
            ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
# /usr/bin/python3
# -*- coding: utf-8 -*-
from queue import Queue
from queue import LifoQueue as Stack
from math import sqrt, floor, ceil, log2, log10, pi
from fractions import gcd
from itertools import permutations, combinations
from operator import itemgetter
from functools import cmp_to_key

# from numpy import gcd


INF=1001001001
__MOD__=(10**9)+7
yn = 'YNeos'
judge = False
cnt = 0
ans = None


def lcm(a, b):
    return (a*b) // gcd(a,b)

def intinput():
    return int(input())

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

def lineinputs(func=intinput):
    datas = []
    while True:
        try:
            datas.append(func())
        except EOFError:
            break
    return datas

class ModInt():
    def __init__(self, x):
        self.__x = (x % __MOD__)
    def __add__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x + other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x + other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __radd__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x + self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x + self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __sub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x - other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x - other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rsub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x - self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x - self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __mul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rmul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __truediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rtruediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __pow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(self.__x, other.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(self.__x, other.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")
    def __rpow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(other.__x, self.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(other.__x, self.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")

    def __modinv(self, m=__MOD__):
        a = self.__x
        if a == 0:
            raise ZeroDivisionError()
        if gcd(a, m) != 1:
            raise Exception("%sの逆数は求まりません。" % a)
        b, u, v = m, 1, 0
        while b != 0:
            t = a//b;
            a -= t*b
            a, b = b, a
            u -= t * v
            u, v = v, u
        u %= m
        if u < 0:
            u += m
        return u
    def __int__(self):
        return self.__x
    def __str__(self):
        return str(self.__x)



if __name__ == '__main__':
    N = intinput()
    ds = set(mulinputs())

    if len(ds) <= 1:
        print(0)
        exit()
    ds = list(ds)
    # ds.sort()
    if ds[0] == 1:
        print(0)
        exit()
    p = []
    l = int(sqrt(len(ds)))
    # for _ in range(l):
    #     if not ds:
    #         break
    while ds:
        tmp = ds.pop(0)
        p.append(tmp)
        ds = [ d for d in ds if d % tmp != 0]

    # 出力
    print(len(p)+len(ds))

Submission status: Wrong Answer

Solution code:
N=int(input())
A=sorted(map(int,input().split()))
m=max(A)
s=set(A)
cnt=[0]*(10**6+1)
for i in range(N):
    cnt[A[i]]+=1
ng=set()
for i in range(N):
    if cnt[A[i]]>1:
        ng.add(A[i])

for i in range(N):
    if A[i] in ng:
        if A[i] in s:
            s.remove(A[i])
        continue
    if not A[i] in s:
        continue
    for j in range(2,100000):
        if A[i]*j>m:
            break
        if A[i]*j in s:
            s.remove(A[i]*j)
print(len(s))

Submission status: Wrong Answer

Solution code:
import math


def is_prime(n):
    if n <= 1:
        return False
    for b in range(2, int(math.sqrt(n))+1):
        if n % b == 0:
            return False
    return True


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

cnt = 0
A_s = sorted(A)
for i in range(N):
    if A_s.count(A_s[i]) == 1:
        if is_prime(A_s[i]):
            cnt += 1
        else:
            flg = True
            for j in range(i):
                if A_s[i] % A_s[j] == 0:
                    flg = False
            if flg:
                cnt += 1       

print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import math
import numpy as np

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

dic = Counter(a)

ans = 0

memo = {}

def seachPrimeNum(N):
    max = int(np.sqrt(N))
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum

primeNum = set(seachPrimeNum(10**6))

for ai in a:
    cnt = 0
    f = 1
    if ai not in memo:
        if ai not in primeNum:
            for i in range(1, int(math.sqrt(ai))+1):
                if ai % i == 0:
                    d = i
                    if d in dic:
                        cnt += dic[d]
                    if d == ai:
                        cnt -= 1
                    if cnt > 0:
                        f = 0
                        break
                    if i != ai // i:
                        d = ai // i
                        if d in dic:
                            cnt += dic[d]
                        if d == ai:
                            cnt -= 1
                        if cnt > 0:
                            f = 0
                            break
    else:
        f = memo[ai]
    ans += f
    memo[ai] = f

print(ans)

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 1 in a:
    print(1)
elif len(set(a))==1:
    print(0)
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))