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
input = sys.stdin.readline

n=int(input())
L=list(map(int,input().split()))
L.sort()
hb = L[-1]
dp = [-1 for i in range(hb+1)] 
print(L)
for i in L:
    if dp[i]!=0:
        if dp[i]==1:
            dp[i]=0
            continue
        dp[i]=1
        for j in range(2*i,hb+1,i):
            dp[j]=0
ans=0
for i in L:
    if dp[i]==1:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import math

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

    A.sort()

    Amax=max(A)

    dp=[True for _ in range(Amax)]

    a=A.pop(0)
    res=0
    for i in range(1,Amax+1):
        if i==a and dp[i-1]==True:
            m=1
            res+=1
            while (a*m-1)<=Amax-1:
                dp[a*m-1]=False
                m+=1
            if len(A)==0:
                break
            else:
                a=A.pop(0)
                if i==a:
                    res-=1
                    while i==a and len(A)>0:
                        a=A.pop(0)
                if len(A)==0:
                    break

        elif i==a and dp[i-1]==False:
            if len(A)==0:
                break
            else:
                a=A.pop(0)

        if i > math.sqrt(Amax):
            break
    for i in A:
        if dp[i-1]==True and a!=i:
            res+=1

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

Submission status: Wrong Answer

Solution code:
from collections import deque
import math

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

    A.sort()

    Amax=max(A)

    dp=[True for _ in range(Amax)]

    a=A.pop(0)
    res=0
    for i in range(1,Amax+1):
        if i==a and dp[i-1]==True:
            m=1
            res+=1
            while (a*m-1)<=Amax-1:
                dp[a*m-1]=False
                m+=1
            if len(A)==0:
                break
            else:
                a=A.pop(0)
                if i==a:
                    res-=1
                    while i==a and len(A)>0:
                        a=A.pop(0)
                if len(A)==0:
                    break

        elif i==a and dp[i-1]==False:
            if len(A)==0:
                break
            else:
                a=A.pop(0)

        if i > math.sqrt(Amax):
            break

    for i in A:
        if dp[i-1]==True:
            res+=1

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

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
a.sort()
check = [1] * n
cnt = Counter(a)

for i in range(n - 1):
    if cnt[a[i]] > 1: check[i] = 0
    if check[i] == 0:continue
    
    for j in range(i + 1, n):
        if a[j] % a[i] == 0:check[j] = 0

ans = sum(check)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
import math

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

    A.sort()

    Amax=max(A)

    dp=[True for _ in range(Amax)]

    a=A.pop(0)
    res=0
    for i in range(1,Amax+1):
        if i==a and dp[i-1]==True:
            m=1
            res+=1
            while (a*m-1)<=Amax-1:
                dp[a*m-1]=False
                m+=1
            if len(A)==0:
                break
            else:
                a=A.pop(0)
                if i==a:
                    res-=1
                    while i==a and len(A)>0:
                        a=A.pop(0)
                if len(A)==0:
                    break

        elif i==a and dp[i-1]==False:
            if len(A)==0:
                break
            else:
                a=A.pop(0)

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

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
a.sort()
check = [1] * n
cnt = Counter(a)

for i in range(n - 1):
    for j in range(i + 1, n):
        if a[j] % a[i] == 0:check[j] = 0

ans = sum(check)
for key, val in cnt.items():
    if val > 1:ans -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
List=list(map(int,input().split()))
b=[]
q=0
List=sorted(List)
M=List[len(List)-1]/2
while (List[0]<=M and len(List)>1):
    p=List[0]
    for i in range(0,len(List)):
        if List[i]%p!=0:
            b.append(List[i])
    if List[0]!=List[1]:
        p+=1
    List=b
    b=[]
    if len(List)==0:
        break
    M=List[len(List)-1]/2
if len(List)>0:
    y=[x for x in set(List) if List.count(x)==1]
    q+=len(y)
print(q)

Submission status: Wrong Answer

Solution code:
#! env python
# -*- coding: utf-8 -*-

import os
import sys


# atcoder.main
# Date: 2020/06/19
# Filename: main 
# Author: acto_mini

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

    remove_index = list()
    ans = 0

    for i in range(N - 1):
        flag = True
        if i in remove_index:
            continue

        for j in range(i + 1, N):
            if A[j] % A[i] == 0:
                remove_index.append(j)

            if A[i] % A[j] == 0:
                remove_index.append(i)
                flag = False
                break

        if flag: ans += 1

    # print(remove_index)
    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#! env python
# -*- coding: utf-8 -*-

import os
import sys


# atcoder.main
# Date: 2020/06/19
# Filename: main 
# Author: acto_mini

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

    remove_index = list()
    ans = 0

    for i in range(N - 1):
        flag = True
        if i in remove_index:
            continue

        for j in range(i + 1, N):
            if A[j] % A[i] == 0:
                remove_index.append(j)

            if A[i] % A[j] == 0:
                remove_index.append(i)
                flag = False
                break

        if flag: ans += 1

    print(remove_index)
    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

while True:
  if i>=len(A)-1:
    break
  a = A[i]
  same_num = 0
  j = i+1
  
  while True:
    if j>=len(A)-1:
      break
    elif A[j]==a:
      same_num+=1
      del A[j]
      ##continue
    elif A[j]%a==0:
      del A[j]
    else:
      j+=1
      
  if same_num>0:
    del A[i]
  else:
    i+=1
    
print(len(A))

Submission status: Wrong Answer

Solution code:
import sys

def Not_Divisible(n,p):
    maxp = max(p)
    dp = [True for _ in range(maxp+1)]
    for a in p:
        t =2
        while a*t <= maxp:
            if dp[a*t] == True :
                dp[a*t] = False
            t+=1
    k=0
    for d in p:
        if dp[d] == True:
            k+=1
    return k


def main():
    input = sys.stdin.readline
    
    inp1 = input().rstrip().split()
    n = int(inp1[0])

    inp2 = input().rstrip().split()
    p = tuple(map(int,inp2))
    print(Not_Divisible(n,p))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

cnt = 0

for a in a_int_list:
    flg = 0
    for a_tmp in a_int_list:
        if((a != a_tmp) and (a % a_tmp == 0)):
            flg = 1
            break
    if(flg == 0):
        cnt += 1
    
print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
List = list(map(int, input().split()))
res = 0
New_List = sorted(List)
Flag = [1]*N

def checkf(x, List):
  for j in range(N):
    if x < j:
      break
    else:
      if x == List[j]:
        return True
  return False
for i in range(2, N-1):
  for j in range(i+1,N):
    if New_List[i] == New_List[j]:
      Flag[i] = 0
      Flag[j] = 0
A = New_List[N-1]
for i in range(2,A):
  if checkf(i, New_List):
    for j in range(N):
      if New_List[j]  == i :
        pass
      elif New_List[j] % i == 0:
        Flag[j] = 0
  if i > New_List[N-1]**0.5:
    break
res = Flag.count(1)
print(Flag,res)

Submission status: Wrong Answer

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

l=[]
As.sort()
prev=0
for Ai in As:
    if Ai == prev:
        if len(l)>0 and l[-1]==prev:
            l.pop()
        continue
    for e in l:
        if Ai%e==0:
            break
    else:
        l.append(Ai)
    prev=Ai
    
print(len(l))

Submission status: Wrong Answer

Solution code:
N = int(input())
List = list(map(int, input().split()))
res = 0
New_List = sorted(List)
Flag = [1]*N
for i in range(1,N):
  if New_List[i] > New_List[N-1]/2:
    break
  else:
    if Flag[i] ==1:
      for j in range(i,N):
        if New_List[i] == New_List[j]:
          Flag[i] = 0
          Flag[j] = 0
        if Flag[j] == 1:
          if New_List[i] % New_List[j] == 0:
            Flag[i] = 0
          else:
            pass
        elif Flag[j] == 0:
          pass
    else:
      pass
res = Flag.count(1)
print(res)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
cnt = N
for i in range(1,len(A)):
  for j in range(i-1):
    if A[i] % A[j] == 0:
      cnt -= 1
      break
print(cnt)

Submission status: Wrong Answer

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

c = sorted(list(set(b)))
can_div = []
if len(c) == 1:
  print(0)
else:
  for i1,k1 in enumerate(c):
    i1 += 1
    for i2,k2 in enumerate(c[0:i1]):
      if max(c[0:i1]) % k2 == 0 and max(c[0:i1]) != k2:
        can_div.append(max(c[0:i1]))
  d = set(c) - set(can_div)
  print(len(list(d)))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = input()
A = A.split(' ')

for i in range(N - 1):
    for j in range(i + 1, N):
        if int(A[i]) > int(A[j]):
            A[i], A[j] = A[j], A[i]
total = 0
for i in range(N):
    chk = -1
    for j in range(i):
        if int(A[i]) / 2 < int(A[j]):
            break
        if int(A[i]) % int(A[j]) == 0:
            chk = 1
            break
    if chk == 1:
        total += 1
print(N - total)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = input()
A = A.split(' ')

for i in range(N - 1):
    for j in range(i + 1, N):
        if int(A[i]) > int(A[j]):
            A[i], A[j] = A[j], A[i]

#print(A)

total = 0
for i in range(N - 1, 0, -1):
#    print('i === ' ,i)
    chk = -1
    for j in range(i):
        if int(A[i]) / 2 < int(A[j]):
            break
                            
#        print('j =', j)
        if int(A[i]) % int(A[j]) == 0:
            chk = 1
            break

    if chk == 1:
        total += 1
print(N - total)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
L = [1] * (max(A) + 1)
ret = 0
dup = list()
for i in range(len(A)):
    if L[A[i]] == 1:
        if i < len(A) - 1 and A[i] == A[i+1]:
            dup.append(A[i])
            L[A[i]] = 0
        else:
            ret += 1
            num = 2
            while A[i] * num < len(L)  :
                L[A[i] * num] = 0
                num += 1
    
print(ret)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = input()
A = A.split(' ')

for i in range(N - 1):
    for j in range(i + 1, N):
        if int(A[i]) > int(A[j]):
            A[i], A[j] = A[j], A[i]

#print(A)

total = 0
for i in range(N - 1, 0, -1):
#    print('i === ' ,i)
    chk = -1
    for j in range(i):
#        print('j =', j)
        if (i != j) and (int(A[i]) /2 >= int(A[j])) and (int(A[i]) % int(A[j]) == 0):
            chk = 1
            break
        else:
            continue
        break

    if chk == 1:
        total += 1
print(N - total)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = input()
A = A.split(' ')

for i in range(N - 1):
    for j in range(i + 1, N):
        if int(A[i]) > int(A[j]):
            A[i], A[j] = A[j], A[i]

print(A)

total = 0
for i in range(N - 1, 0, -1):
    print('i === ' ,i)
    chk = -1
    for j in range(i):
        print('j =', j)
        if (i != j) and (int(A[i]) /2 >= int(A[j])) and (int(A[i]) % int(A[j]) == 0):
            chk = 1
            break
        else:
            continue
        break

    if chk == 1:
        total += 1
print(N - total)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = input()
A = A.split(' ')

for i in range(N - 1):
    for j in range(i + 1, N):
        if int(A[i]) > int(A[j]):
            A[i], A[j] = A[j], A[i]
            
total = 0
for i in range(N - 1, 0, -1):
    print('i === ' ,i)
    chk = -1
    for j in range(i):
        print('j =', j)
        if (i != j) and (int(A[i]) % int(A[j]) == 0):
            chk = 1
            break
        else:
            continue
        break

    if chk == 1:
        total += 1
print(N - total)

Submission status: Wrong Answer

Solution code:
N = int(input())
A_array = list(map(int, input().split()))
ans = 0
check = [0 for _ in range(10 ** 6 + 5)]
A = sorted(A_array)

for i in range(N):
  for j in range(int((len(check) - 1) / A[i])):
    if check[A[i] * (j + 1)] >= 2:
      break
    else:
      check[A[i] * (j + 1)] += 1

for i in range(len(check) - 1):
  if i + 1 in A:
    if check[i + 1] == 1:
      ans += 1
    else:
      continue
  else:
    continue

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A_array = list(map(int, input().split()))
ans = 0
check = [0 for _ in range(10 ** 6 + 5)]
A = A_array

for i in range(N):
  for j in range(int((len(check) - 1) / A[i])):
    if check[A[i] * (j + 1)] >= 2:
      break
    else:
      check[A[i] * (j + 1)] += 1

for i in range(len(check) - 1):
  if i + 1 in A:
    if check[i + 1] == 1:
      ans += 1
    else:
      continue
  else:
    continue

print(ans)

Submission status: Wrong Answer

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

maxa = max(a)
l = [0] * (maxa+1)


for i in a:

    c = 1
    while True:
        if i*c >= maxa:
            break
        l[i*c - 1] += 1
        c += 1







ans = 0

for i in set(a):
    if l[i-1] == 1:
        ans += 1

print(ans)

Submission status: Wrong Answer

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


l = [0] * max(a)


for i in a:

    c = 2
    while True:
        if i*c-1 >= max(a):
            break
        l[i*c - 1] = 1
        c += 1


sa = sorted(a)
ans = 0

for i in range(len(sa)):
    if l[sa[i]-1] == 0 and sa[i-1] != sa[i]:
        if i != 0:
            ans += 1
        else:
            if sa[i+1] != sa[i]: ans += 1 

print(ans)

Submission status: Wrong Answer

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

maxA = max(A)
ans = 0
flag = [0]*(maxA+1)

# print(flag)
for a in A:
    for ax in range(a*2,maxA+1,a):
        flag[ax] +=1

# print(flag)
for a in set(A):
    if flag[a] == 0:
        ans += 1
print(ans if ans > 1 else 0)

Submission status: Wrong Answer

Solution code:
from collections import Counter

def undivisible(A):
    m = max(A)
    dp = [True] * (m+1)
    A.sort()
    for a in A:
        if dp[a]:
            k = a * 2
            while k <= m:
                dp[k] = False
                k += a
    cnt = Counter(A)
    ans = 0
    for a in A:
        if dp[a] and cnt[a] == 1:
            ans += 1
    return ans

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

Submission status: Wrong Answer

Solution code:
from collections import Counter

def undivisible(A):
    m = max(A)
    dp = [True] * (m+1)
    A.sort()
    for a in A:
        if dp[a]:
            k = a * 2
            while k <= m:
                dp[k] = False
                k += a
    cnt = Counter(A)
    ans = 0
    for a in A:
        if dp[a] and cnt[a] == 1:
            ans += 1
    return ans

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

Submission status: Wrong Answer

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

a.sort()
dp = [True for i in range(a[-1]+1)]
count=0

for i in range(n):
    if dp[a[i]]:
        count+=1
        for j in range(1,n-i):
            if a[i]!=a[i+j]:
                break
            elif j==1:
                count-=1
            dp[a[i+j]]=False
        for j in range(a[i], a[-1], a[i]):
            dp[j]=False
        # for j in range(i + 1, n):
        #     if not a[j] % a[i]:
        #         dp[j] = False
        #     if a[j] == a[i]:
        #         dp[i] = False

#print(dp.count(True))
print(count)

Submission status: Wrong Answer

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

ans = 0
Amax = max(A)
S = [0] * (Amax+1)

for a in range(N):
    num = A[a] - 1
    if S[num] == 0:
        ans += 1
        if A[a] == A[a-1]:
            ans -= 1
    for i in range(0, Amax+1, num+1):
        if i <= Amax:
            S[i-1] = 1

print(ans)

Submission status: Wrong Answer

Solution code:
import os
import heapq
import sys
import math
import operator
from collections import defaultdict
from io import BytesIO, IOBase


"""def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)"""

"""def pw(a,b):
    result=1
    while(b>0):
        if(b%2==1): result*=a
        a*=a
        b//=2
    return result"""



def inpt():
    return [int(k) for k in input().split()]


def main():
    divisor=[False]*(1000010)
    n=int(input())
    ar=inpt()
    ar.sort()
    for i in range(n):
        if(not divisor[ar[i]]):
            for j in range(2*ar[i],ar[n-1]+1,ar[i]):
                divisor[j]=True
    ct=0
    for i in ar:
        if(divisor[i]==False):
            ct+=1
    print(ct)













BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N =int(input())
A = list(map(int, input().split()))
 
element1=[]
for u in range(N):
    for i in range(N):
        if A[u]<=A[i]:
            continue
        amari=A[u]%A[i]
        if amari  == 0 :
            
            element1.append(A[u])
a=set(A)^set(element1)
print(len(a))

Submission status: Wrong Answer

Solution code:
n = input()

l = list(map(int, input().split()))
l = sorted(l)
for el in l:
    tmp = l.pop(0)
    for el2 in l:
        if el2 % tmp == 0:
            l.remove(el2)
    if len(l) != 0:
        l.append(tmp)


print(len(l))

Submission status: Wrong Answer

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

element1=[]
for u in range(N):
    for i in range(N):
        amari=A[u]%A[i]
        if A[u]<=A[i]:
            continue
        if amari  == 0 :
            
            element1.append(A[u])
a=set(A)^set(element1)
print(len(a))

Submission status: Wrong Answer

Solution code:
N = int(input())
suretsu = list(map(int, input().split()))
# N = 5
# suretsu = [24, 11, 8, 3, 16]
count = 0
shugo = set(suretsu)
suretsu = list(shugo)

for i in range(len(suretsu)):
    check = suretsu[i]
    hako = []
    for j in range(len(suretsu)):
        waru = suretsu[j]
        if i == j:
            hako.append(2)
            continue
        elif check % waru == 0:
            hako.append(0)
        elif check % waru:
            hako.append(1)
    if 1 in hako and not 0 in hako:
        count += 1

print(count)

Submission status: Wrong Answer

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

a.sort()
out = 0
if not a[0] in a[1:]:
    out += 1

for i in range(n):
    for j in range(i):
        if not a[i] % a[j]:
            break
        if a[i]/2 < a[j] or j == i-1:
            out += 1
            break
print(out)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=sorted(list(map(int,input().split())))
s=set(l)
for x in l:
  for i in range(2,10**6//x+3):
    if i*x in s:
      s.remove(i*x)
print(len(s))

Submission status: Wrong Answer

Solution code:
N = int(input())
suretsu = list(map(int, input().split()))
# N = 5
# suretsu = [24, 11, 8, 3, 16]
count = 0
shugo = set(suretsu)

for i in range(N):
    check = suretsu[i]
    hanbetsu = 1
    for j in shugo:
        waru = j
        if check == waru:
            continue
        elif check % waru == 0:
            hanbetsu = 0
    if hanbetsu:
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
aa = [int(x) for x in input().split()]
a = list(set(aa))
n = len(a)
a.sort()
a_max = a[-1]
divs = set()

for i in range(n-1):
    m = 2
    x = m*a[i]
    while x <= a_max:
        x = m*a[i]
        if x in a:
            divs.add(x)
        m += 1
if len(a) == len(aa):
    print(n - len(list(divs)))
else:
    print(n - len(list(divs))-1)

Submission status: Wrong Answer

Solution code:
N = int(input())
nums = [i for i in map(int, input().split(" "))]
nums = sorted(nums)

target_count = 0
for index in range(N):
    if N==1:
        target_count=1
        break
    target = nums[index]
    divisible_flag = False
    if index ==0:
        residue = target % nums[index+1]
        if residue ==0:
            divisible_flag = True
    else:
        for num in nums[:index]:
            residue = target % num
            if residue ==0:
                divisible_flag = True
                break
    if not divisible_flag:
        target_count+=1

print(target_count)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int, input().split()))
ans=0
cnt=[0]*((10**6)+1)
a.sort()
b=[]
for i in a:
    cnt[i]+=1
for i in range(10**6+1):
    if cnt[i] ==1:
        b.append(i)
cnt=[0]*((10**6)+1)
for s in b:
    for i in range(s*2,10**6+1,s):
        cnt[i]=1
for s in b:
    if cnt[s]==0:
        ans+=1
print(ans)

Submission status: Wrong Answer

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

for i in range(N):
    for j in range(N):
        if j == i:
            continue
        elif (A[i] % A[j]) == 0:
            continue
        else:
            count += 1
            break

print(count)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
A = sorted(list(map(int, input().split())))
dp = [True for i in range(max(A) + 1)]
c = Counter(A)
s = set(A)
ans = 0
for i in s:
    TMP = i * 2
    while TMP <= max(A):
        dp[TMP] = False
        TMP += i
    if c[i] == 1 and dp[i] == True:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
A = sorted(list(map(int, input().split())))
dp = [True for i in range(max(A) + 1)]
dp[0] = False
c = Counter(A)
s = set(A)
ans = 0
for i in s:
    if i == 1:
        print(1)
        exit()
    for j in range(2, (max(A) // i) + 1):
        if not dp[i * j]:
            continue
        else:
            dp[i * j] = False

for i in s:
    if c[i] == 1 and dp[i]:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A_array = [x for x in map(int, input().split())]
ans = 0

for i in range(N):
    Ai = A_array[i]
    for j, Aj in enumerate(A_array):
        if j == i:
            continue
        else:
            if Ai % Aj == 0:
                break
            elif j == N - 1:
                ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = sorted(list(map(int, input().split())))
dp = [True for i in range(max(A) + 1)]
dp[0] = False
ans = 0
for i in A:
    for j in range(2, (max(A) // i) + 1):
        if not dp[i * j]:
            continue
        else:
            dp[i * j] = False
for i in range(N):
    if A[i] == A[i - 1]:
        pass
    elif dp[A[i]]:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

A = sorted([int(i) for i in input().split()])

if len(set(A)) == 1 or A[0] == 1:
  print(0)
  exit();

cnt = 0  
while len(A) > 0:
  k = A[0]
  A = [i for i in A if i%k != 0]
  cnt +=1
  
print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())

A = sorted([int(i) for i in input().split()],reverse=True)

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

cnt = 0
for i in range(N):
  x = 0
  for j in range(i + 1, N):
    if A[i]%A[j] == 0:
      x += 1
  if x == 0:
    cnt += 1
    
print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
count = 0
for a in A:
  B = []
  for b in A:
    B.append(a%b)
    if B.count(0) == 1:
      count += 1
print(count)

Submission status: Wrong Answer

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

A.sort()
B=[1]*n

for i in range(n):
    if B[i]==1:
        for j in range(i+1,n):
            if A[j]%A[i]==0:
                B[j]=0
print(sum(B))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(set(list(map(int, input().split()))))
a.sort()
 
if len(a)==1:
    print(0)
else:
    dp = [True] * len(a)
    cnt = 0
    for i in range(len(a)):
        if dp[i]:
            for j in range(len(a)):
                if i==j:
                    continue

                if dp[j]:
                    if a[j]%a[i]==0:
                        cnt += 1
                        dp[j] = False

    ans = len(a) - cnt
    print(ans)

Submission status: Wrong Answer

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

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

def main():

    def gcd(a, b):
        while b: a, b = b, a % b
        return a
    def isPrimeMR(n):
        d = n - 1
        d = d // (d & -d)
        L = [2]
        for a in L:
            t = d
            y = pow(a, t, n)
            if y == 1: continue
            while y != n - 1:
                y = (y * y) % n
                if y == 1 or t == n - 1: return 0
                t <<= 1
        return 1
    def findFactorRho(n):
        m = 1 << n.bit_length() // 8
        for c in range(1, 99):
            f = lambda x: (x * x + c) % n
            y, r, q, g = 2, 1, 1, 1
            while g == 1:
                x = y
                for i in range(r):
                    y = f(y)
                k = 0
                while k < r and g == 1:
                    ys = y
                    for i in range(min(m, r - k)):
                        y = f(y)
                        q = q * abs(x - y) % n
                    g = gcd(q, n)
                    k += m
                r <<= 1
            if g == n:
                g = 1
                while g == 1:
                    ys = f(ys)
                    g = gcd(abs(x - ys), n)
            if g < n:
                if isPrimeMR(g): return g
                elif isPrimeMR(n // g): return n // g
                return findFactorRho(g)
    def primeFactor(n):
        i = 2
        ret = {}
        rhoFlg = 0
        while i*i <= n:
            k = 0
            while n % i == 0:
                n //= i
                k += 1
            if k: ret[i] = k
            i += 1 + i % 2
            if i == 101 and n >= 2 ** 20:
                while n > 1:
                    if isPrimeMR(n):
                        ret[n], n = 1, 1
                    else:
                        rhoFlg = 1
                        j = findFactorRho(n)
                        k = 0
                        while n % j == 0:
                            n //= j
                            k += 1
                        ret[j] = k

        if n > 1: ret[n] = 1
        if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
        return ret

    #[(p1,n1),(p2,n2),...]の形で返す
    def primeFactor2(n):
        i = 2
        ret = {}
        rhoFlg = 0
        while i*i <= n:
            k = 0
            while n % i == 0:
                n //= i
                k += 1
            if k: ret[i] = k
            i += 1 + i % 2
            if i == 101 and n >= 2 ** 20:
                while n > 1:
                    if isPrimeMR(n):
                        ret[n], n = 1, 1
                    else:
                        rhoFlg = 1
                        j = findFactorRho(n)
                        k = 0
                        while n % j == 0:
                            n //= j
                            k += 1
                        ret[j] = k

        if n > 1: ret[n] = 1
        if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
        return ret

    #約数列挙
    #10^6以下で約数の数が最大なのは720720の時(240個しかない！)
    def divisors(N):
        pf = primeFactor(N)
        ret = [1]
        for p in pf:
            ret_prev = ret
            ret = []
            for i in range(pf[p]+1):
                for r in ret_prev:
                    ret.append(r * (p ** i))
        return sorted(ret)
        
        
    
    mod=10**9+7
    N=I()
    A=LI()
    from collections import defaultdict
    dd = defaultdict(int)
    for i in range(N):
        dd[A[i]]+=1
        
    A.sort()
    
    ans=0
    for i in range(N):
        if dd[A[i]]<2:
            L=divisors(A[i])
            flag=1
            for v in L[1:-1]:
                if dd[v]:
                    flag=0
                    break
            if flag:
                ans+=1
                
    if A[0]==1:
        ans=0
                
    print(ans)
                    
        
        

                
    
    


main()