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 math

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

ans = 0
for i in range(N):
    rt = math.sqrt(A[i])
    for j in range(N):
        if i == j:
            if j == N - 1:
                ans += 1
                continue
            else:
                continue
        if A[i] % A[j] == 0:
            break
        if A[j] > rt:
            ans += 1
            break

print(ans)

Submission status: Wrong Answer

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

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

semiprime=[]

for num in b:
  flag=1
  for prime in semiprime:
    if num%prime==0:
      flag=0
      break
  
  if flag==1:
    semiprime.append(num)
    ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
if n == 1:
    print(0)
else:
    ans = n
    if a[0] % a[1] == 0:
        ans -= 1
    for i in range(1,n):
        for j in range(i):
            if a[i] % a[j] == 0:
                ans -= 1
                break
            if a[i] < a[j]*2:
                break
    print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
flag = 0
for i in range(1, n+1):
    value = a[-i]
    flag = 0
    if value == a[-i + 1]:
        flag = 1
    for j in range(i+1, n+1):
        if value%a[-j] == 0:
            flag = 1
            break
    if flag == 0:
        ans += 1
# if a[0]%a[1] == 0:
    # ans-= 1
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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



n = int(input())
a = [int(i) for i in input().split()]


sa = set(a)
c = 0

for i in range(n):
    f = True
    
    for j in make_divisors(a[i]):
        if j in sa and j != a[i]:
            f = False
            break

    if a[i] == a[i-1]:
        f = False
    if f:
        c += 1

    # if a[i] in sa:
        # sa.remove(a[i])


print(c)

Submission status: Wrong Answer

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

i=0
num=0

if min(a)==1:
    print('1')

else:

    while i<n:

        j=0
        jud=1
        while j<n:
            if i!=j:
                if a[i]>=a[j]:

                    if a[i]%a[j]==0:
                        jud=0
                        break

            j+=1

        if jud==1:
            num+=1

        i+=1

    print(num)

Submission status: Wrong Answer

Solution code:
N= int(input())
As = list(map(int,input().split()))
As= [a for a in As if As.count(a)==1]
As.sort()
import sys
if len(As)==0:
    print(0)
    sys.exit()
count=1
for i in range(1,len(As),-1):
    flg=True
    for j in range(i):
        if As[i]%As[j]==0:
            flg=False
            break
        if As[j]>As[i]**0.5:
            break
    if flg:
        count +=1
print(count)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

N = int(input())


if N == 1:
    print(int(input()))
    sys.exit()

A = set(map(int, input().split()))

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

A = np.array(sorted(A))
B = np.array([A[0]])

for i in range(len(A)-1):
    if np.all(A[i+1] % B != 0):
        B = np.append(B, A[i+1])
print(len(B))

Submission status: Wrong Answer

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

for a in A:
  if a not in B:
    if A.count(a)==1:
      B.extend([n*a for n in range(2,max(A))])
    else:
      B.extend([n*a for n in range(1,max(A))])

print(len(set(A))-len(set(A)&set(B)))

Submission status: Wrong Answer

Solution code:
import sys
import collections

def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
def TI(): return tuple(map(int,input().split()))
def RN(N): return [input().strip() for i in range(N)]


def main():
    
    N = II()
    A = LI()
    As = sorted(A, reverse=True)
    ans = N
    c = collections.Counter(As)

    if N == 1:
        print(0)
    elif len(set(A)) == 1:
        print(0)
    elif c[1] != 0:
        if c[1] == 1:
            print(1)
        else:
            print(0)
    else:
        for i in range(N-1):
            k = N-1
            if c[As[i]] >= 2:
                ans -= 1
                if i == N-2:
                    ans -= 1
            else:
                for j in range(N):
                    if k == i:
                        break
                    elif As[i] % As[k] == 0:
                        ans -= 1
                        break

                    k -= 1

        print(ans)


if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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

for i in range(1,n):
    m=len(List)
    for j in range(m):
        if (a[i]==List[-1]):
            if (flag==0):
                ans-=1
            flag=1
            break
        elif (a[i]%List[j]==0):
            flag=0
            break
        elif (a[i]/List[j]<2):
            List.append(a[i])
            flag=0
            ans+=1
        elif(j==m-1):
            List.append(a[i])
            flag=0
            ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
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
N=int(input())
hitoketa=[]
count=0
A=list(map(int,input().split()))
A=list(set(A))
if len(A)==1:
    print(0)
    exit()
A.sort()
owari=set()
#print(prime_factorize(12))
for i in range(len(A)):
    test=0
    for j in owari:
        if A[i]%j==0:
            test=1
    owari.add(A[i])
    if test==0:
        count+=1
print(count)

Submission status: Wrong Answer

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

import numpy as np

ans = 0
for i in range(N):
    if A.count(A[i]) == N:
        ans = 0
        break
        break
    c = [j for j in A[i]/np.array(A) if j.is_integer() ]
    if len(c) == 1:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
p = [a[0]]
for i in range(1,n):
    v = 1
    for j in range(len(p)):
        if a[i] < 2*a[j]:
            break
        if a[i] % a[j] == 0:
            v = 0
            break
    if v == 1:
        p.append(a[i])
ans = len(p)
for i in range(n-2):
    if a[i] == a[i+1] and a[i+1] != a[i+2] and a[i] in p:
        ans -= 1
if n > 1:
    if a[-1] == a[-2] and a[-1] in p:
        ans -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = [int(x) for x in input().split()]
from collections import defaultdict
d = defaultdict(int)
ans = 0
for i in range(N):
    d[a[i]] += 1
for i in range(1,1001):
    if d[i] == 1:
        ans += 1
        for j in range(2,2+10**6//i):
            d[j*i] = 0
    elif d[i] >= 2:
        for j in range(2,2+10**6//i):
            d[j*i] = 0
for i in range(1001,1000001):
    if d[i] >= 1:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import math


def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 1:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

import collections





n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
c = collections.Counter(a)
data = []
for e in c.most_common():
  if e[1] == 1:
    data.append(e[0])
data = sorted(data)
#data = a.copy()
prime = []
limit = math.sqrt(10**6+1)
while len(data) > 0:
  p = data[0]
  if limit <= p:
    prime += data
    break
  prime.append(p)
  data = [e for e in data if e % p != 0]
  #print(data)

print(len(prime))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
a = list(map(int, input().split()))
a.sort(reverse = True)
ans = 0
for i in range(len(a)):
    sign = []
    flg = 0
    for j in range(i, len(a)):
        if j != len(a)-1:
            flg = 1
        if i == j:
            sign.append(0)
        else:
            p = a[i]%a[j]
            if p == 0:
                sign.append(1)
            else:
                sign.append(0)
        if flg == 0:
                sign.append(1)
    print(sign)
    if sum(sign) == 0:
        ans += 1
print(ans+1)

Submission status: Wrong Answer

Solution code:
n = int(input())

from collections import defaultdict

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

d = defaultdict(int)

for el in a:
    d[el] += 1

count = 0

d = sorted(d.items(), reverse=True)
# wm = d[0][0]

while len(d):
    a, c = d.pop()
    if c == 1:
#         print(f'count {a=}, {c=}, {count=}, {d=}')
        count += 1
    if a == 1:
        break
    if len(d):
        m = d[0][0]
    else:
        m = a - 1
    if a * 2 <= m and a * a <= 10**6:
        d = [elm for elm in d if elm[0] % a]
    else:
        count += len(d)
        break

print(count)

Submission status: Wrong Answer

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

ans = 0
for i in range(N - 1, -1, -1):
    a = A[i]
    flag = True
    for j in range(i):
        if a % A[j] == 0:
            flag = False
            break
        if A[j] ** 2 > a:
            break
    if i + 1 < N and A[i] == A[i + 1]:
        flag = False
    if flag:
        ans += 1

print (ans)

Submission status: Wrong Answer

Solution code:
from collections import deque,Counter
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
N = i()
A = l()
if 1 in A:
    if A.count(1) != 1:
        print(0)
    else:
        print(1)
    exit()
A.sort(reverse=True)
A = deque(A)
ans = 0
num = 0
def dv(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
for i in range(N):
    a = A[0]
    A.popleft()
    if a in A:
        ans += 1
        if len(A) == 2:
            ans += 1
        continue
    divs = dv(a)
    if divs:
        for d in divs:
            if d in A:
                num = 1
                break
        if num :
            ans += 1
        num = 0
print(N-ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int,input().split()))
i = 0
ans = 0 
A.sort()
A.reverse()
if A[n-1] == 1:
    if A[n-2] != 1:
        print(1)
        exit()
    else:
        print(0)
        exit()
while i <= n-2:
    for j in range(i+1,n):
        if A[i] % A[j] == 0:
            break
        elif j == n - 1:
            ans = ans + 1
    i = i + 1
print(ans+1)

Submission status: Wrong Answer

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

a_l.sort()
result_list=[]
while len(a_l)>0:
  a = a_l.pop(0)
  result_list.append(a)
  tmp = []
  for _ in a_l:
    if _ % a != 0:
      tmp.append(_)
  a_l = tmp
  
count = len(result_list)
for _ in result_list:
  if _ in a_l:
    count -=1
print(len(result_list))

Submission status: Wrong Answer

Solution code:
from collections import deque

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

    A.sort()
    
    A=deque(A)
    
    escape=deque([])
    while len(A)>0:
        minute=A.popleft()
        tmp=deque([])
        
        while len(A)>0:
            maximum=A.pop()
            if maximum%minute!=0:
                tmp.appendleft(maximum)
        
        escape.append(minute)
        A=tmp

    print(len(escape))




if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[:0:-1]
def main():
    from collections import Counter
    n,*a=map(int,open(0).read().split())
    d=Counter(a)
    s=set(a)
    c=0
    for t in a:
        if d[t]<2 and all(t not in s for t in make_divisors(t)):c+=1
    print(c)
main()

Submission status: Wrong Answer

Solution code:
def main():

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

        ans = 0

        for i in range(N):
                flag = True
                for j in range(N):
                        print(i, j)
                        if i==j:
                                continue
                        elif flag == False:
                                break
                        else:
                                if A[i]%A[j]==0:
                                        flag = False
                                        break
                if flag:
                        ans+=1

        return ans

if __name__=="__main__":
        ans = main()
        print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(int(i) for i in input().split())
a.sort()
a2=[]
kotae=[]

for i in range(n):
  if 2<=len(a):
    if a[1]!=a[0]:
      kotae.append(a[0])
  else:
    kotae.append(a[0])
  kotae.append(a[0])
  for j in range(1,len(a)):
    if a[j]%a[0]!=0:
      a2.append(a[j])
  a=a2
  a2=[]
  if len(a)==0:
    break
       
print(len(kotae))

Submission status: Wrong Answer

Solution code:
import bisect
N=int(input())
A=list(sorted(set(list(map(int,input().split())))))
ans=0
N=len(A)
for i in range(N):
    B=A.copy()
    t=B[i]
    j=max(bisect.bisect_left(B,t*0.5),i)
#     print(t,j)
    del B[j:]
    arr=[]
#     print(B)
    if N>1:
        if all(list(map(lambda x: t%x!=0, B))):
            ans+=1
#             print(i)
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from collections import Counter

n = int(input().strip())
L = list(map(int, input().strip().split()))
seen = Counter()
ans=0

for x in L:
    seen[x]+=1

for x in L:
    if seen[x]>1:
        continue
    # if x==1:
    #     ans+=1
    #     continue
    tmp=2
    while tmp**2<=x:
        if x%tmp==0 and (tmp in seen or x/tmp in seen):
            break
        tmp+=1
    else:
        ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
import collections
import sys
import math


if __name__ == "__main__":
    N = int(input())
    A = [int(x) for x in input().split(" ")]
    counter = collections.Counter(A)

    if 1 in counter:
        print(0)
        sys.exit(0)

    A = [key for key, val in counter.items() if val == 1]

    A.sort()

    count = 0
    divisors = []
    for i, a in enumerate(A):
        flag = True
        for divisor in divisors:
            if a % divisor == 0:
                flag = False
                break
        if flag:
            divisors.append(a)
            count += 1
    print(count)

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 = []
    # while ds:
    l = int(sqrt(len(ds)))
    for _ in range(l):
        if not ds:
            break
        tmp = ds.pop(0)
        if not ds:
            p.append(tmp)
            break
        ds = [ d for d in ds if d % tmp != 0]
        p.append(tmp)

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

Submission status: Wrong Answer

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import deque
import pprint

inf = 10**18
mod = 10**9+7

n = int(input())
a = list(map(int, input().split()))
a.sort()
if n == 1:
    print(1)
    sys.exit()
if n == 2:
    if a[0] == a[1]:
        print(0)
    elif a[1]%a[0] == 0:
        print(1)
    else:
        print(2)
    sys.exit()

b = []
pre = a[0]
if a[0] != a[1]:
    if pre == 1:
        print(1)
        sys.exit()
else:
    if pre == 1:
        print(0)
        sys.exit()
c = collections.Counter(a)
for k,v in c.items():
    if v == 1:
        b.append(k)

judge = [False for i in range(10**6+1)]
for num in b:
    judge[num] = True
for i in range(1,(10**6)//2+1):
    if judge[i]:
        for j in range(i*2,10**6+1,i):
            judge[j] = False
ans = 0
for i in range(1,10**6+1):
    if judge[i]:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int, input().split()))
a.sort()
ans=0
L=[]
for i in range(n-1):
    if a[i]==a[i+1]:
        L.append(a[i])
    else:
        for j in L:
            if a[i]%j==0:
                break
            if j*j > a[i]:
                L.append(a[i])
                ans+=1
                break
        else:
            L.append(a[i])
            ans+=1
for i in L:
    if a[-1]%i==0:
        break
else:
    ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

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



b = sorted(list(set(A)))

x = set(b)

res = x

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

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

if N == 1:
    print(1)


daburi = []

c = sorted(A)
for i in range(1,N):
    if c[i] == c[i-1]:
        daburi.append(c[i])

daburi = set(daburi)
#print(daburi)

f = False
res = 0


i = 0

s = set(b)
for i in x:
    res+=1
    for j in x:
        if i == j: 
            continue
        if j%i== 0 :
            s.discard(j)
#            print(s)
        if len(s)==0:
            f = True
            break
    if f:
        break

print(len(s))

Submission status: Wrong Answer

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

if A.count(1) >= 1:
    print(A.count(1))
    exit()

num = [0]*1000005
for a in A:
    num[a] += 1

b = [False]*1000005
seen = [False]*1000005
cnt = 0
for a in A:
    if seen[a]:
        continue

    seen[a] = True
    if b[a] == False:
        cnt += 1
        if num[a] > 1:
            cnt -= 1

    for i in range(a, 1000005, a):
        b[i] = True
print(cnt)

Submission status: Wrong Answer

Solution code:
import math

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

a.sort()
ans = 0
for i in range(n):
    cnt = 0
    for j in reversed(range(n)):
        if i != j:
            if a[i] % a[j] != 0:
                cnt += 1
                if cnt == n-1:
                    ans += 1
            else:
                break
print(ans)

Submission status: Wrong Answer

Solution code:
import math
from collections import deque
from collections import defaultdict
import itertools as it

#自作関数群
def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	if len(res)==0:
		res = [n]
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):#階乗
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):#コンビネーション
	if n<r:
		return 0
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
def combmod(n,r,mod):
	return (fact(n)/fact(n-r)*pow(fact(r),mod-2,mod))%mod
def printQueue(q):
	r=copyQueue(q)
	ans=[0]*r.qsize()
	for i in range(r.qsize()-1,-1,-1):
		ans[i] = r.get()
	print(ans)
class UnionFind():
	def __init__(self, n):
		self.n = n
		self.parents = [-1]*n

	def find(self, x): # root
		if self.parents[x]<0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self,x,y):
		x = self.find(x)
		y = self.find(y)

		if x==y:
			return

		if self.parents[x]>self.parents[y]:
			x,y = y,x

		self.parents[x]+=self.parents[y]
		self.parents[y]=x

	def size(self,x):
		return -1*self.parents[self.find(x)]

	def same(self,x,y):
		return self.find(x)==self.find(y)

	def members(self,x): # much time
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i)==root]

	def roots(self):
		return [i for i,x in enumerate(self.parents) if x<0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()} # 1~n
def bitArr(n):#ビット全探索
	x = 1
	zero = "0"*n
	ans = []
	ans.append([0]*n)
	for i in range(2**n-1):
		ans.append(list(map(lambda x:int(x),list((zero+bin(x)[2:])[-1*n:]))))
		x+=1
	return ans;
def arrsSum(a1,a2):
	for i in range(len(a1)):
		a1[i]+=a2[i]
	return a1
def maxValue(a,b,v):
	v2 = v
	for i in range(v2,-1,-1):
		for j in range(v2//a+1): #j:aの個数
			k = i-a*j
			if k%b==0:
				return i
	return -1
def copyQueue(q):
	nq = queue.Queue()
	n = q.qsize()
	for i in range(n):
		x = q.get()
		q.put(x)
		nq.put(x)
	return nq
def get_sieve_of_eratosthenes(n):
	data = [2]
	#data = [0,0,0]
	for i in range(3,n+1,2):
		data.append(i)
		data.append(0)
	for i in range(len(data)):
		interval = data[i]
		if interval!=0:
			for j in range(i+interval,n-1,interval):
				data[j] = 0
	ans = [x for x in data if x!=0]
	#ans = data[:]
	return ans

n = readInt()
a = readInts()

if a.count(a[0])==n:
	print(0)
	exit()

maxa = max(a)+1

ans = [0]*maxa
for i in a:
	ans[i] = 1



for j in a:
	for i in range(j*2,10**6+1,j):
		if i>maxa-1:
			break
		ans[i] = 0

print(ans.count(1))

Submission status: Wrong Answer

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

ans = [1]*n

for i in range(n):
    for j in range(n):
        if a[i] % a[j] == 0:
            if i == j:
                continue
            else:
                ans[i] = 0

print(ans)

Submission status: Wrong Answer

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

from math import sqrt
from collections import Counter

n = int(input())
a = list(map(int,input().split()))
s = Counter(a)
a = sorted(s)
if s[1]==2:
    ans = 0
elif s[1]==1:
    ans = 1
else:
    ans = 0
    for i in range(len(a)):
        if s[a[i]]>1:
            continue
        j = 2
        sq = sqrt(a[i])
        while j<=sq:    
            if a[i]%j==0 and (j in s or a[i]//j in s):
                break
            j+=1
        else:
            ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
def linked_merge_sort(l): #マージソート
    if len(l) == 1:
        return
    q, r = divmod(len(l), 2)
    left = [l.pop() for _ in range(q)]
    right = [l.pop() for _ in range(q + r)]
    
    linked_merge_sort(left)
    linked_merge_sort(right)
    
    left.reverse()
    right.reverse()
    while left and right:
        if left[-1] <= right[-1]:
            l.append(left.pop())
        else:
            l.append(right.pop())
    while left:
        l.append(left.pop())
    while right:
        l.append(right.pop())
    return

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

linked_merge_sort(a)
ans=0
for i in range(n):
    jud=1
    if i==0 and n>1 and a[i]==a[i+1]:
        jud=0
    for j in range(i):
        if a[i]%a[j]==0:
            jud=0
            break
    if jud==1:
        ans+=1
print(ans)