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:
n = int(input())
a = list(map(int,input().split()))
a = list(set(a))
a.sort(reverse=True)
n=len(a)
counter = 0
if n==1:
  print(counter)
else:
  for i in range(n):
    start = 0
    for j in range(i+1,n):
      if a[i] % a[j] == 0:
        start = 1
        break
    if start == 0:
      counter+=1
  print(counter)

Submission status: Wrong Answer

Solution code:
import numpy as np
_,*a=map(int,open(0).read().split())
a,c=np.unique(a,return_counts=True)
i = 0
a = a[c==1]
while len(a):
    i+=1
    a = a[a%a[0] != 0]
print(i)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
a = list(set(a))
a.sort(reverse=True)
n=len(a)
counter = 0
if n==1:
  print(counter)
else:
  for i in range(n):
    start = 0
    for j in range(i+1,n):
      if a[i] % a[j] == 0:
        start = 1
    if start == 0:
      counter+=1
  print(counter)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort(reverse=True)
counter = 0
for i in range(n):
  start = 0
  for j in range(i+1,n):
    if a[i] % a[j] == 0:
      start = 1
  if start == 0:
    counter+=1
print(counter)

Submission status: Wrong Answer

Solution code:
import numpy as np
n,*a=map(int,open(0).read().split())
a, c = np.unique(sorted(a), return_counts=True)
a = a[c==1]
i = 0
while len(a):
    a = a[a%a[0] != 0]
    i+=1
print(i)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

from collections import Counter
cnt = Counter(a)

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

limit = a[-1]
is_prime = [0] * (limit + 1)

for aa in a:
    is_prime[aa]=1

for i in range(2, limit + 1):

    if is_prime[i]==0:
        continue
    for j in range(i * 2, limit + 1, i):
        is_prime[j] = 0

ans=0

for i in range(1,limit+1):
    if is_prime[i] and cnt[i] < 2:
        ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
if a[0] == 1:
    print(1)
    exit()
p = [False for i in range(a[-1]+1)]
kaburi = set()
for i in range(n):
    if p[a[i]]:
        kaburi.add(a[i])
    p[a[i]] = True
for i in range(2,a[-1]+1):
    if not p[i]:
        continue
    for j in range(i*2,a[-1]+1,i):
        p[j] = False
ans = 0
for i in range(a[-1]+1):
    if p[i] and not i in kaburi:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Jun 20 16:25:37 2020

@author: naoki
"""
import math

N = int(input()) # the number of integers
A = list(map(int,input().split())) # the row of integers
A.sort() # sorting the contents of the row from small numbers 
dest = int(math.sqrt(A[N-1])) # teh range of calculation
prime_list = []
"""
# the smallest number is not divided by any numbers in the row except for the same number 
for i in range(N): # the divided number
    k=0
    while  (A[i] % A[k] != 0 or k == i) and k<=min(i+1,N-1): # if divisible, drop out the loop                  
        if k==min(i+1,N-1):
            count+=1
            break
        else:
            k+=1
"""
while True:
    if A[0] >= dest:
        prime_list.append(A[0])
        break
    prime_list.append(A[0])
    i = 0 
    while True:
        if i >= len(A):
            break
        elif A[i] % A[0] == 0:
            A.pop(i) # 
        i+=1
    
print(len(prime_list))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
count=0
for i in range(1,n):
	sum=0
	for j in range(0,i):
		if a[i] % a[j] != 0:
			sum=sum+1
			print(i,j,a[i],a[j])
	if sum==i:
		count=count+1		
if count==0:
	print(count)
else:
	print(count+1)

Submission status: Wrong Answer

Solution code:
import collections
n = int(input())
a = list(map(int,input().split()))
c = collections.Counter(a)
p = sorted(c.items())
ans = 0
kouho = set()

for k ,v in p:
    if v != 1:
        kouho.add(k)
        continue
    m = k
    flag = False
    for i in range(2,int(m**0.5)+1):
        if m%i == 0:
            if i in kouho or m//i in kouho:
                flag = True
                break
    if not flag:
        ans += 1
    kouho.add(m)
print(ans)

Submission status: Wrong Answer

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

A.sort(reverse=True)

ans = 0
for i, a in enumerate(A):
    flag = True
    for j in A[i + 1:]:
        if a % j == 0:
            flag = False
            break

    if A[i] == A[i - 1]:
        if A[i] % A[i - 1] == 0:
            flag = False

    if flag:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = sorted(map(int, input().split()), reverse=True)
NG = 0

for i in range(N):
    for j in range(i+1, N):
        if A[i] % A[j] == 0:
            NG += 1
            break

if A[0] == A[N-1]:
    NG += 1

res = N - NG
print(res)

Submission status: Wrong Answer

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

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]


count = 0
for i in A:
    others = A - {i}
    divs = set(make_divisors(i))
    if len(others & divs) == 0:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
def noWeight(y):
    ya = set(y)
    yb = []
    for a in range(len(y)-1):
        if y[a] == y[a+1]:
            yb.append(y[a])
    y = ya-set(yb)
    return list(y)
    

x = int(input())
y = list(map(int, input().split()))
y = noWeight(y)
y.sort()
x = len(y)
tf = [bool(z+1) for z in range(x)]

for a in range(x-1):
    if tf[a]==True:
        for b in range(a+1,x):
            if tf[b]==True:
                if y[a]==y[b]:
                    tf[a]=False
                if y[b]%y[a]==0:
                    tf[b]=False

print(sum(tf))

Submission status: Wrong Answer

Solution code:
"""
    Satwik_Tiwari ;) .
    16 june , 2020  - Tuesday
"""

#===============================================================================================
#importing some useful libraries.
from __future__ import division, print_function

from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase


import bisect
from heapq import *
from math import *
from collections import deque
from collections import Counter as counter  # Counter(list)  return a dict with {key: count}
from itertools import combinations as comb # if a = [1,2,3] then print(list(comb(a,2))) -----> [(1, 2), (1, 3), (2, 3)]
from itertools import permutations as permutate
from bisect import bisect_left as bl
#If the element is already present in the list,
# the left most position where element has to be inserted is returned.
from bisect import bisect_right as br
from bisect import bisect
#If the element is already present in the list,
# the right most position where element has to be inserted is returned

#==============================================================================================

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


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

# inp = lambda: sys.stdin.readline().rstrip("\r\n")

#===============================================================================================
#some shortcuts

mod = 1000000007
def inp(): return sys.stdin.readline().rstrip("\r\n") #for fast input
def out(var): sys.stdout.write(str(var))  #for fast output, always take string
def lis(): return list(map(int, inp().split()))
def stringlis(): return list(map(str, inp().split()))
def sep(): return map(int, inp().split())
def strsep(): return map(str, inp().split())
def graph(vertex): return [[] for i in range(0,vertex+1)]
def zerolist(n): return [0]*n
def nextline(): out("\n")  #as stdout.write always print sring.
def testcase(t):
    for p in range(t):
        solve()
def printlist(a) :
    for p in range(0,len(a)):
        out(str(a[p]) + ' ')
def lcm(a,b): return (a*b)//gcd(a,b)
def power(a,b):
    ans = 1
    while(b>0):
        if(b%2==1):
            ans*=a
        a*=a
        b//=2
    return ans
def ncr(n,r): return factorial(n)//(factorial(r)*factorial(max(n-r,1)))
def isPrime(n) : # Check Prime Number or not
    if (n <= 1) : return False
    if (n <= 3) : return True
    if (n % 2 == 0 or n % 3 == 0) : return False
    i = 5
    while(i * i <= n) :
        if (n % i == 0 or n % (i + 2) == 0) :
            return False
        i = i + 6
    return True

#===============================================================================================
# code here ;))

def solve():
    n = int(inp())
    a = lis()
    if(a.count(1) > 0):
        print(0)
        return
    m = max(a)
    cnt = [0]*(m+1)

    for i in range(0,n):
        num = a[i]
        for j in range(num,m+1,num):
            cnt[j] +=1
        # print(num,cnt)
    ans= 0
    for i in range(n):
        if(cnt[a[i]] == 1):
            # print(a[i])
            ans +=1
    print(ans)





testcase(1)
# testcase(int(inp()))

Submission status: Wrong Answer

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

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]

count = 0
for i in A:
  others = A - {i}
  divs = set(make_divisors(i))
  if len(others & divs) > 0:
    count += 1
    
print(count)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    MAX = A[-1]
    dp = [1] * (MAX + 5)
    ANS = 0
    for i in range(N):
        if dp[A[i]] == 0:
            continue
        for j in range(MAX):
            if A[i]*j > MAX:
                break
            dp[A[i]*j] = 0
        dp[A[i]] = 0
        if i < N-1 and A[i] == A[i+1]:
            continue
        ANS += 1
    print(ANS)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    MAX = A[-1]
    dp = [1] * (MAX + 5)
    ANS = 0
    for i in range(N):
        if dp[A[i]] == 0:
            continue
        for j in range(MAX):
            if i*j > MAX:
                break
            dp[i*j] = 0
        dp[A[i]] = 0
        if i < N-1 and A[i] == A[i+1]:
            continue
        ANS += 1
    print(ANS)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
number = int(input())
values = [i+2 for i in range(2*10**5)]
# values = list(map(int, input().split()))

maxV = 10**6+1
dp = [0]*(maxV)

for a in values:
    i = 1
    if dp[a] > 1:
        continue
    while i * a < maxV:
        i_a = i * a
        dp[i_a] = dp[i_a] + 1
        i += 1

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

print(count)

Submission status: Wrong Answer

Solution code:
number = int(input())
values = [i+2 for i in range(2*10**5)]
# values = list(map(int, input().split()))

maxV = 10**6+1
dp = [0]*(maxV)

for a in values:
    i = 1
    if dp[a] > 0:
        dp[a] = dp[a] + 1
        continue
    while i * a < maxV:
        i_a = i * a
        dp[i_a] = dp[i_a] + 1
        i += 1

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

print(count)

Submission status: Wrong Answer

Solution code:
number = int(input())
# values = [i+2 for i in range(2*10**5)]
values = list(map(int, input().split()))

maxV = 10**6+1
dp = [0]*(maxV)

for a in values:
    if a == 1:
        print(1)
        exit()
    i = 1
    if dp[a] > 1:
        continue
    while i * a < maxV:
        i_a = i * a
        dp[i_a] = dp[i_a] + 1
        i += 1

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

print(count)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=sorted(list(map(int,input().split())))
X=[A[0]]
if N>1 and A[0]==A[1]:
  ans=0
else:
  ans=1
f=True
if A[0]==1:
  print(1)
  exit(0)
for i in range(1,N):
  if A[i]==A[(i+1)%N]:
    f=False
    continue
  
  F=True
  for x in X:
    if A[i]%x==0:
      F=False
      break
  if F:
    X.append(A[i])
    if f:
      ans+=1
  f=True
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
n = int(input())
a = [int(x) for x in input().split()]
list(set(a))#重複を削除
a.sort()#ソート
count = 0
if(n == 1):
  print(1)
  sys.exit()
for i in range(1,n):
  if(a.count(a[i]) >= 2):
    continue
  if(2 in a and a[i] % 2 == 0):
    continue
  flg = False
  for j in range(i):
    #他の要素で割り切れる場合リストから削除
    if(a[j] % a[i] == 0):
      flg = True
      a.pop(j)
      j -= 1
      break
  if(flg == False):
    count += 1

if(a[0] != a[1]):
  count += 1
print(count)

Submission status: Wrong Answer

Solution code:
import sys
n = int(input())
a = [int(x) for x in input().split()]
list(set(a))#重複を削除
a.sort()#ソート
count = 0
if(n == 1):
  print(1)
  sys.exit()
for i in range(1,n):
  if(a.count(a[i]) >= 2):
    continue
  if(2 in a and a[i] % 2 == 0):
    continue
  flg = False
  for j in range(i):
    #他の要素で割り切れる場合リストから削除
    if(a[j] % a[i] == 0):
      flg = True
      a.pop(j)
      break
  if(flg == False):
    count += 1

if(a[0] != a[1]):
  count += 1
print(count)

Submission status: Wrong Answer

Solution code:
import sys
n = int(input())
a = [int(x) for x in input().split()]
list(set(a))#重複を削除
a.sort()#ソート
count = 0
if(n == 1):
  print(1)
  sys.exit()
for i in range(1,n):
  #２が含まれている場合偶数をとばす
  if(2 in a and a[i] % 2 == 0):
    continue
  flg = False
  for j in range(i):
    if(a[i] % a[j] == 0):
      flg = True
      break
  if(flg == False):
    count += 1
count += 1
print(count)

Submission status: Wrong Answer

Solution code:
#maspyさんを参考に
import sys
#import numpy as np
#from numba import njit
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# この最適化がよくわからん。Numpyループなら行けるらしい
# 400msくらいは最低でもかかるけど、N=10^5でも2でも変わらんと言う
#@njit('(i4[::1],)', cache=True)
def solve(A):
  # エラトステネス古いって値側のバリエーションとして配列をとるんや
  # maxA = 10**6って言うのがポイントっぽいなあ。。
    count = np.zeros(10**6 + 10, np.int32)
    for x in A:
        if count[x] > 1:
            continue
        count[::x] += 1
    ret = 0
    for x in A:
        ret += count[x] == 1
    return ret

def solve2(A):
  count = [0] * (10**6 + 10)
  for x in A:
    if count[x] > 1:
      continue
    for a in range(0,len(count),x):
      count[a] += 1
  ret = 0
  for x in A:
    ret += 1 if count[x] == 1 else 0
  return ret
  
#A = np.array(read().split(), np.int32)[1:]
A = list(map(int, input().split()))
print(solve2(A))

Submission status: Wrong Answer

Solution code:
n = int(input())
m = list(map(int,input().split()))
l=set(m)
l = [i for i in l]
l.sort()
ans=[True for i in range(max(l)+1)]
#print(ans,len(ans))

p=0
#print(l,l[n])
#print(max(l))
while(p<len(l)):
    
    if(ans[l[p]]==True):
        
        for i in range(l[p]*2,max(l)+1,l[p]):
            ans[i]=False
            
    p+=1
        
ans[0]=False;ans[1]=False

c=0
#print(ans)
for j in l:
    if(ans[j]==True):
        c+=1
if(len(m) - len(l)==n-1):print(0)        
else:print(c)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import groupby

readline = sys.stdin.buffer.readline
readline()
b = list(map(int, readline().split()))

b.sort()
# print(b)

x = len(b)
c = [(k, len(tuple(L))) for k, L in groupby(b)]
# print(c)
s = [False] * x
for i, v in enumerate(c):
  if v[1] > 1:
    x -= v[1]
    continue
  for j, vv in enumerate(c[i+1:], i):
#     print(vv[0], v[0])
    if s[j]:
        continue
    if not vv[0] % v[0]:
      x -= 1
      s[j] = True
      break
print(x)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import groupby

readline = sys.stdin.buffer.readline
readline()
b = list(map(int, readline().split()))

b.sort()
# print(b)

x = len(b)
c = [(k, len(tuple(L))) for k, L in groupby(b)]
# print(c)
s = set()
for i, v in enumerate(c):
  if v[1] > 1:
    x -= v[1]
    continue
  for vv in c[i+1:]:
#     print(vv[0], v[0])
#     if v[0] < vv[0] * 2:
#       break
    if vv[0] not in s and not vv[0] % v[0]:
      x -= 1
      s.add(vv[0])
      break
print(x)

Submission status: Wrong Answer

Solution code:
input()
sorted([int(x) for x in input().split()])

Submission status: Wrong Answer

Solution code:
import sys
from itertools import groupby

readline = sys.stdin.buffer.readline
readline()
b = list(map(int, readline().split()))

b.sort(reverse=True)
# print(b)

x = len(b)
c = [(k, len(tuple(L))) for k, L in groupby(b)]
# print(c)
for i, v in enumerate(c):
  if v[1] > 1:
    x -= v[1]
    continue
  for vv in c[-1:i:-1]:
    print(v[0], vv[0])
    if not v[0] % vv[0]:
      x -= 1
      break
print(x)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
c = [0]*1000001

for i in range(n):
  for j in range(1,1000001//a[i]):
    c[j*a[i]] += 1

ans = 0
for k in a:
  if c[k] == 1:
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import groupby

readline = sys.stdin.buffer.readline
a = map(int, readline().split())
b = list(map(int, readline().split()))
b.sort(reverse=True)
# print(b)

x = len(b)
c = [(k, len(list(L))) for k, L in groupby(b)]
# print(c)
for i, v in enumerate(c):
  if v[1] > 1:
    x -= v[1]
    continue
  for vv in c[i+1:]:
    if not v[0] % vv[0]:
      x -= 1
      continue
print(x)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import groupby

readline = sys.stdin.buffer.readline
a = map(int, readline().split())
b = list(map(int, readline().split()))
b.sort(reverse=True)
# print(b)

x = len(b)
c = [(k, len(list(L))) for k, L in groupby(b)]
# print(c)
for i, v in enumerate(c):
  if v[1] > 1:
    x -= v[1]
    break
  for vv in c[i+1:]:
    if not v[0] % vv[0]:
      x -= 1
      break
print(x)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import groupby

readline = sys.stdin.buffer.readline
a = map(int, readline().split())
b = list(map(int, readline().split()))
b.sort(reverse=True)
print(b)

x = len(b)
c = [(k, len(list(L))) for k, L in groupby(b)]
# print(c)
for i, v in enumerate(c):
  if v[1] > 1:
    x -= v[1]
    break
  for vv in c[i+1:]:
    if not v[0] % vv[0]:
      x -= 1
      break
print(x)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)
max_a=A[0]
dp=[True]*(max_a+1)
ans=0
for i in range(N):
  a=A[i]
  #print(a)
  if dp[a]==True: 
    if i==N-1:
      ans+=1
    elif a!=A[i+1]:
      ans+=1
    
    k=a
    while k<=max_a:
      dp[k]=False    
      k+=a
print(ans)

Submission status: Wrong Answer

Solution code:
x = int(input())
y = list(map(int, input().split()))

y.sort()
ans = []
while len(y) != 0:
    judge = y.pop(0)
    remove = []
    if len(y) == 0:
        ans.append(judge)
        break;
    if judge != y[0]:
        ans.append(judge)
    for i in y:
        if i % judge == 0:
            remove.append(i)
    y = list(set(y) - set(remove))
        
print(len(ans))

Submission status: Wrong Answer

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

def eratosthenes(A):
    P=[]

    while len(A)>0:
        prime = min(A)
        x=0
        if A.count(prime)>1:
            x +=1

        P.append(prime)

        i = 0
        while i < len(A):
            if A[i] % prime ==0:
                A.pop(i)
                continue
            i += 1
            
    return len(P)-x
if A.count(1) ==0:
    print(eratosthenes(A))
elif A.count(1)==1:
    print(1)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
x = int(input())
y = list(map(int, input().split()))

ans = 0

for i, j in enumerate(y):
    for k, l in enumerate(y):
        if k != i or j % l == 0:
            break;
    else:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

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

    l=[0]*(10**6+5)

    for i in A:
        if l[i]!=0:
            l[i]+=1
            continue
        for j in range(1,10**6//i):
            l[j*i]+=1
    
    cnt=0
    for i in A:
        if l[i]==1:
            cnt+=1
    print(cnt)




    
resolve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

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

    l=[0]*(10**6+5)

    for i in A:
        if l[i+1]!=0:
            l[i+1]+=1
            continue
        for j in range(1,10**6//i):
            l[j*i+1]+=1
    
    cnt=0
    for i in A:
        if l[i+1]<=1:
            cnt+=1
    print(cnt)




    
resolve()

Submission status: Wrong Answer

Solution code:
import argparse
import collections
import logging.config
import sys
import csv
import numpy as np

def tester(n, a):
  cnt = 0
  for i in range(n):
    tester = 1
    for j in range(i):
      if (i != j) and (a[i]%a[j] == 0):
        tester = 0
        break
    cnt += tester
  return (cnt)

  
  
def main():
    sa = input()
    n = int(sa)
    a = []
    sb = input().split()
    for d in sb:
      a.append(int(d))
    a.sort()
    print (tester(n,a))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

for a in set(A):
    for k in range(2*a,MAX+1,a):
        dp[k] = False
B = sorted(A)
for i in range(len(B)-1):
    if B[i] == B[i+1]:
        dp[B[i]] = False

print(sum(dp[a] for a in set(A)))
print(dp)

Submission status: Wrong Answer

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

for a in set(A):
    for k in range(2*a,MAX+1,a):
        dp[k] = False
B = sorted(A)
for i in range(len(B)-1):
    if B[i] == B[i-1]:
        dp[B[i]] = False

print(sum(dp[a] for a in set(A)))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(4100000)

import math

import logging

logging.basicConfig(level=logging.DEBUG)

logger = logging.getLogger(__name__)

from collections import Counter


def resolve():
    # S = [x for x in sys.stdin.readline().split()][0]  # 文字列 一つ
    N = [int(x) for x in sys.stdin.readline().split()][0]  # int 一つ
    # N, D = [int(x) for x in sys.stdin.readline().split()]  # 複数int
    a_list = [int(x) for x in sys.stdin.readline().split()]  # 複数int

    # grid = [list(sys.stdin.readline().split()[0]) for _ in range(N)]  # 文字列grid
    # v_list = [int(sys.stdin.readline().split()[0]) for _ in range(N)]
    # grid = [[int(x) for x in sys.stdin.readline().split()]
    #         for _ in range(N)]  # int grid

    logger.debug('{}'.format([]))
    counter = Counter(a_list)

    sorted_list = sorted(counter.keys())
    n_keys = len(sorted_list)
    is_prime_list = [True for _ in range(len(sorted_list))]

    count = 0

    for i, v in enumerate(sorted_list):
        tmp = counter[v]
        if tmp >= 2:
            count += tmp
        if is_prime_list[i]:
            for j in range(i + 1, n_keys):
                tmp = sorted_list[j]
                if is_prime_list[j] and tmp % v == 0:
                    is_prime_list[j] = False
                    count += counter[tmp]

    print(N - count)


if __name__ == "__main__":
    resolve()

# AtCoder Unit Test で自動生成できる, 最後のunittest.main は消す
# python -m unittest template/template.py で実行できる
# pypy3 -m unittest template/template.py で実行できる

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """5
24 11 8 3 16"""
        output = """3"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """4
5 5 5 5"""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """10
33 18 45 28 8 19 89 86 2 4"""
        output = """5"""
        self.assertIO(input, output)

Submission status: Wrong Answer

Solution code:
n=int(input())
from collections import Counter as co
l=co(map(int,input().split()))
ans=set()
for k in l:
    if l[k]>=2:ans.add(k)
    for j in range(2*k,2*10**5+1,k):
        if j in l:
            ans.add(j)
        
        
print(len(l)-len(ans))

Submission status: Wrong Answer

Solution code:
n=int(input())
from collections import Counter as co
l=co(map(int,input().split()))
ans=set()
for k in l:
    if l[k]>=2:ans.add(k)
    for j in range(2*k,2*10**5+1,k):
        if j in l:
            ans.add(j)
        
        
print(n-len(ans))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
bag = set()
for i in range(N):
    time = 2
    while A[i]*time <= max(A):
        bag.add(A[i]*time)
        time += 1
if bag == set():
    print(0)
    exit()

count = 0
for i in range(N):
    if A[i] in bag:
        count += 1
print(N-count)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
import math
import string
import collections
from collections import Counter
from collections import deque
from decimal import Decimal
import sys
import fractions
from operator import itemgetter
import itertools
import copy


def readints():
    return list(map(int, input().split()))


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]

n = int(input())
a = readints()
tmp = [False]*(10**6+100)
a_so = sorted(a)
# print(a_so)
cnt = 0
for i in range(len(a_so)):
    if tmp[a_so[i]]:
        continue
    if (i+1 >= len(a_so)) or (a_so[i] != a_so[i+1]):
        cnt += 1
    for j in range(1, 10**5):
        if a_so[i]*j >= len(tmp):
            break
        tmp[a_so[i]*j] = True
print(cnt)

Submission status: Wrong Answer

Solution code:
a=int(input())
b=list(map(int,input().split()))
ans=0
for i in b:
  if len([j for j in b if not i%j==0])==a:
    break
  else:
    ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
n = int(sys.stdin.readline().rstrip("\n"))
a = [int(s) for s in sys.stdin.readline().rstrip("\n").split()]
a.sort()
a_true = [True]*n
a_set = set(a)
if 1 in a or len(a_set) == 1:
    print(0)
else:
    a_max = a[n-1]
    i = 0
    while i < n-1:
        if a[i] == a[i+1]:
            a_true[i] = False
            a_true[i+1] = False
            i += 1
        else:
            break
    while a[i]*2 <= a_max:
        for j in range(i+1,n):
            if a[j] % a[i] == 0:
                a_true[j] = False
        i += 1
    while i < n-1:
        if a[i] == a[i+1]:
            a_true[i] = False
            a_true[i+1] = False
        i += 1
    print(len([i for i in range(0, n) if a_true[i]]))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
f=[1]*(10**6+1)
from collections import Counter
c=Counter(a)
ans=0
for ai in a:
  if c[ai]==1 and f[ai]==1:ans+=1
  if f[ai]==1:
    for i in range(ai,10**6,ai):
      f[i]=0
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
C = {}
for i in range(N):
    a = A[i]
    if a not in C:
        C[a] = 0
    C[a] += 1
A = []
for a in C:
    if C[a]==1:
        A.append(a)
if len(A)==0:
    print(0)
else:
    A = sorted(A)
    N = len(A)
    amax = A[-1]
    P = [0 for _ in range(amax+1)]
    for i in range(N):
        P[A[i]] = 1
    for i in range(N):
        a = A[i]
        if P[a]==1:
            for j in range(a*2,amax+1,a):
                P[j] = 0
    print(sum(P))