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
import os
import itertools
from collections import deque

def main():
    if os.getenv("ENV")=='LOCAL':
        sys.stdin = open(os.path.dirname(__file__)+'/input.txt', 'r')

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

    A.sort()
    ans=0
    # for i in range(N):
    #     for j in range(N):
    #         if i != j and A[i]%A[j]==0:
    #             break
    #         elif j==N-1:
    #             ans+=1

    T=[True]*A[-1]
    T[0]=False

    for i,a in enumerate(A):
        if T[a-1]:
            j=2*a
            while j <= A[-1]:
                T[j-1]=False
                j+=a
        if not i+1==len(A):
            if A[i]==A[i+1]:
                T[a-1]=False

    for a in A:
        if T[a-1]:
            ans+=1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import collections

_ = int(input())
a = list(map(int, input().split(" ")))
a = collections.Counter(a)
a = [ k  for k,v in a.items() if v == 1]
a = sorted(a)

prime = []
while len(a) != 0:
    t = a[0]
    a = [ item for item in a if item % t != 0]
    prime.append(t)

print(len(prime))

Submission status: Wrong Answer

Solution code:
#import numpy as np
import sys
#from collections import deque
#import copy


def xnxn(n=0, flag="v"):
    """
    args:
        int n: a number of lows to read
    example:
        input   1
        retrun  1

        input   1 2 3
        return  [1,2,3]
        input   1 2 3
                4 
        return  [[1,2,3],
                [4]]
    """
    if n == 0:
        temp = list(map(int, input().split()))
        if len(temp) == 1:
            if flag == "l":
                return temp
            else:
                return temp[0]
        elif len(temp) > 1:
            return temp
    else:
        temp = [list(map(int, input().split())) for _ in range(n)]
        return temp


n = xnxn()
if n == 1:
    print(1)
    sys.exit()

a = xnxn()

a.sort()
a_max = max(a)

dp = [1] * (a_max+1)


if a[0] != a[1]:
    count = 1
else:
    count = 0
for k in range(2, a_max // a[0]+1):
    dp[a[0] * k] = 0

for i in range(1, n):
    if a[i] == a[i - 1]:
        continue
    elif dp[a[i]] == 1:
        count += 1
        for k in range(2, a_max // a[i]+1):
            dp[a[i] * k] = 0


print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())

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


b = sorted(list(A))
dp = [0]*(max(A)+4)

for i in b:
    dp[i] += 1
    if dp[i] :
        for j in range(2, max(A)//i+1):
            dp[j*i] =-1

print(dp.count(1))

Submission status: Wrong Answer

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

def main():
    n=int(input().rstrip())
    a=sorted([int(i) for i in input().split()])
    maxn=10**6+1
    dp=[0]*(maxn)
    cnt=[0]*(maxn)
    ans=0
    for i in a:
        if dp[i]:
            cnt[i]+=1
            for j in range(i*2,maxn,i):
                dp[j]=False

    for i in a:
        if dp[i] and cnt[i]==1:
            #print(i)
            ans+=1
    print(ans)

if __name__=="__main__":main()

Submission status: Wrong Answer

Solution code:
def main():
    from collections import Counter
    n, *a = map(int, open(0).read().split())
    x = Counter(a)

    y = [k for k, v in x.items() if v == 1]
    if len(y) == 0:
        print(0)
        exit()

    z = sorted(y)

    if x.get(1) is not None:
        if x.get(1) == 1:
            print(1)
            exit()
        else:
            print(0)
            exit()

    l = z[-1]
    m = [0] * (l + 1)
    for i in z:
        if m[i] == 0:
            m[i] = 1
        j = l // i
        for k in range(2, j + 1):
            m[i * k] = -1

    ans = m.count(1)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

maxA = max(a)
dp = [ 1 for _ in range(maxA+1)]
b = sorted(set(a))
count = 0

if len(b) == 1:
    print(0)
else:    
    for e in b:
        if dp[e] == 1:
            count += 1
            for i in range(e,maxA+1,e):
                dp[i] = 0

    print(count)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort()
ans=N
rem=[]
for i in range(N-1):
  if A[i]==A[i+1]:
    ans-=1
    rem+=[A[i]]
  if i!=0 and A[i]==A[i-1] and A[i]!=A[i+1]:
    ans-=1
if A[N-1]==A[N-2]:
  ans-=1
mult=[]
for i in range(N):
  B=list(range(A[i]*2,10**6+1,A[i]))
  mult+=B
mult=set(mult)
rem=set(rem)
for i in range(N):
  if A[i] in mult and A[i] not in rem:
    ans-=1
print(ans)

Submission status: Wrong Answer

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

def main():
    n=int(input().rstrip())
    a=sorted([int(i) for i in input().split()])
    maxn=10**6+1
    dp=[0]*(maxn)
    cnt=[0]*(maxn)
    ans=0
    for i in a:
        if dp[i]:
            for j in range(i*2,maxn,i):
                dp[j]=False

    for i in a:
        if dp[i] and cnt[i]==1:
            #print(i)
            ans+=1
    print(ans)

if __name__=="__main__":main()

Submission status: Wrong Answer

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

dp = [True for _ in range(A[-1]+1)]

for i in range(N):
    ai = A[i]
    for j in range(1,A[-1]+1):
        if ai*j > A[-1]:
            break
        if dp[ai*j]:
            dp[ai*j] = False

ans = 0
finish = [True for _ in range(A[-1]+1)]
for i in range(N):
    if dp[A[i]] and finish[A[i]]:
        ans += 1
        finish[A[i]] = False

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

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

for i in range(N - 1,-1,-1):
  sup = A[i] // 2 + 1
  if A[i] == A[i - 1]:
    ans -= 1
    continue
  ind = bisect.bisect(A,sup)
  for j in range(0,ind):
    if A[i] % A[j] == 0:
      ans -= 1
      break

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=sorted(list(map(int,input().split())))
a=list(set(a))
if(len(a)==1):
    print(0)
    exit()
ans=0
primeNum = []
while a:
    primeNum.append(a[0])
    tmp=a[0]
    a=[i for i in a if i % tmp != 0]
primeNum.extend(a)
ans+=len(primeNum)


print(ans)

Submission status: Wrong Answer

Solution code:
## coding: UTF-8
N = int(input())
A = sorted(list(map(int,input().split())))


#print(A)

MAX = 10**6+10
l = [True] * MAX


count = 0
last = -1
mode = 0
for i in range(len(A)):
    e = A[i]
    if(last == e):
        count -= 1
        last = -1
    if(l[e]):
        count += 1
        for j in range(MAX//e):
            l[j*e] = False
        last = e

    #print(l)

print(count)

Submission status: Wrong Answer

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

ans_list = [[1, 0] for i in range(1000001)]
for i in range(N):
    now = A[i]
    if ans_list[now][1] == 1:
        continue
    else:
        ans_list[now][1] = 1
    for j in range(2*now, 1000001, now):
        ans_list[j][0] = 0

count = 0
for i in range(N):
    now = A[i]
    if ans_list[now][0] == 1 and ans_list[now][1] == 1:
        count += 1
        
print(count)

Submission status: Wrong Answer

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

cnt = 0
l = [0]*(max(As)+1)
for A in As:
  l[A] += 1
for i in range(max(As)+1):
  if l[i]:
    cnt += l[i]==1
    for j in range(i, max(As)+1, i):
      l[i] = 0
print(cnt)

Submission status: Wrong Answer

Solution code:
import bisect

n = int(input())
a = list(map(int, input().split()))
a.sort()
k = len(a)
ok = [0] * k
for i in range(k):
    if i < k - 1 and a[i] == a[i + 1]:
        ok[i] = 1
        ok[i+1] = 1

    times = 2
    while a[i] * times < a[-1]:
        r = bisect.bisect_left(a, a[i] * times)
        l = bisect.bisect_left(a, a[i] * times)
        if r != l:
            for idx in range(l, r):
                ok[idx] = 1
        times += 1
print(len([i for i in ok if i == 0]))
# print(ok) WAはどこ？

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
d=dict()
for i in a:
    if i in d:
        d[i]+=1
    else:
        d[i]=1
e=list()
for i,j in d.items():
    if j==1:
        e.append(i)
e.sort()
n=len(e)
c=[1 for i in range(n)]
for i in range(n):
    if c[i]==0:
        continue
    for j in range(n):
        if e[i]==e[j]:
            continue
        if e[i]%e[j]==0:
            c[i]=0
print(len([i for i in c if i]))
#print(e,c,sep='\n')

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
*A, = map(int, input().split())
A.sort()
c = Counter(A)
if A[0] == 1:
    print(0)
else:
    ans = 0
    d = [0]*(10**6+1)
    for i in range(N):
        if d[A[i]] == 0:
            if c[A[i]] == 1:
                ans += 1
            j = A[i]
            while j <= (10**6):
                d[j] += 1
                j += A[i]
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

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

A.sort()

s = 0
for i in range(N):
    if i != N - 1:
        if A[i] == A[i + 1]:
            s += 1
            continue
    if i != 0:
        if A[i] == A[i - 1]:
            s += 1
            continue
    for j in range(i):
        if A[i] % A[j] == 0:
            s += 1
            break
        if A[i] < (A[j]+1)**2:
            break

print(N - s)

Submission status: Wrong Answer

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

if N == 1:
    print(1)
    exit()
    
check_list = [0] * (10**6 + 1)

cnt = 0
for i in range(len(A)):
    tmp = A[i]
    while True:
        if tmp > A[-1]:
            break
        check_list[tmp] += 1
        tmp += A[i]

for a in A:
    if check_list[a] == 1:
        cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
l=list(map(int,input().split()))
c=0
if(len(set(l))==1):
   print(0)
else:
  for i in l:
    x=0
    for j in range(1,int(math.sqrt(i))+1):
      if(i%j==0):
        if(j in l):
          x=-1
          break
    if(x==0):
      c+=1
  print(c)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n=int(input())
a=sorted(list(map(int,input().split())))
 
c=[1 for i in range(10**6+1)]
d = Counter(a)
s = list(set(a))
count = 0
if d[1] == 1:
  print(1)
elif d[1] >=2:
  print(0)
for x in s:
  t = x * 2
  while t <= 10 ** 6:
    c[t] = 0
    t += x

for x in a:
  if d[x] == 1 and c[x] == 1:
    count += 1
print(count)

Submission status: Wrong Answer

Solution code:
n=int(input())
A=list(map(int,input().split()))
A.sort()
m,ans=max(A)+1,0
li=[0 for _ in range(m)]
li[0]=1

for a in A:
  if not li[a]:
    ans += 1
    for i in range(a,m,a):
      li[i] = 1

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=sorted([int(i) for i in input().split()])
b=[0 for i in range(max(a)+1)]

ans=0
for i in a:
    if b[i]==0:
        c=i
        while i<max(a)+1:
            b[i]=c
            i+=c
    else:
        if b[i]!=c:
            ans+=1
print(n-ans)

Submission status: Wrong Answer

Solution code:
from math import sqrt
from collections import Counter


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

    ans = 0
    p = [0] * (10**6 + 1)
    c = Counter(A)

    for a in A:
        tmp = a * 2
        if tmp > 10**6:
            continue
        if p[tmp] == 1:
            continue
        while tmp <= 10**6:
            p[tmp] = 1
            tmp += a

    for a in A:
        if p[a] == 0 and c[a] == 1:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[int(x) for x in input().split()]
a.sort()
max=a[-1]
dp=[False for _ in range(max+1)]

Submission status: Wrong Answer

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

sorted_A = sorted(A)
result = 0
c = Counter(sorted_A)
# 倍数を管理するテーブル
lendp = sorted_A[-1] + 1
dp = [0] * lendp

if N == 1:
    print(0)
else:
    for a in sorted_A:
        if dp[a] == 0 and c[a] == 1:
            result += 1
            b = a
            while b < lendp:
                dp[b] += 1
                b += a

    print(result)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())))
ans = [True] * n

from collections import Counter

ca = Counter(a)
for i,c in ca.items():
    if c>1:
        for j in range(n):
            if a[j]==i:
                ans[j]=False
ma = max(a)

for i in range(n):
    for j in range(i+1,n):
        if a[i] > ma//2:
            break
        if not ans[j]:
            break
        if a[j]%a[i]==0:
            ans[j] = False

print(sum(a for a in ans))

Submission status: Wrong Answer

Solution code:
def main():
    from collections import Counter
    n, *a = map(int, open(0).read().split())
    x = Counter(a)
    y = [k for k, v in x.items() if v == 1 or k == 1]
    if len(y) == 0:
        print(0)
        exit()

    z = sorted(y)

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

    l = z[-1]
    m = [0] * (l + 1)
    for i in z:
        if m[i] == 0:
            m[i] = 1
        j = l // i
        for k in range(2, j + 1):
            m[i * k] = -1

    ans = m.count(1)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

cnt = 0
l = [False]*(max(As)+1)
for A in As:
  l[A] = True
for i in range(max(As)+1):
  if l[i]:
    cnt += 1
    for j in range(i, max(As)+1, i):
      l[i] = False
print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

A.sort()
d = deque()

ans = 0
max_A = max(A)
ban = [0]*(max_A+1)
again = list()

for i in range(N-1):
    if A[i] != A[i+1]:
        d.append(A[i])
    else:
        again.append(A[i])
if A[N-1] != A[N-2]:
    d.append(A[N-1])
else:
    again.append(A[N-1])

for num in again:
    ban_num = num
    while ban_num <= max_A:
        ban[ban_num] = 1
        ban_num += num
 
while len(d):
    num = d.popleft()
    if ban[num] != 1:
        ans += 1
        ban_num = num
        while ban_num <= max_A:
            ban[ban_num] = 1
            ban_num += num

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    AList = list(map(int, input().split()))
    AList.sort()
    AMax = AList[-1] + 1

    dp = [True] * AMax
    answer = 0

    ACheckSet = set()

    for A in AList:

        if dp[A]:
            answer = answer + 1
            ACheckSet.add(A)

            for x in range(A, AMax, A):
                dp[x] = False

        elif A in ACheckSet and answer >= 1:
            answer = answer - 1

    print(answer)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n = int(input())
arr = list(map(int, input().split()))
arr.sort()
count = 0
ap = defaultdict(int)
for i in range(n):
    if i != 0 and not ap[arr[i]]:
        count += 1
    if i == 0 or (i > 0 and arr[i] != arr[i-1]):
        for j in range(arr[i], 1000001, arr[i]):
            ap[j] = 1
print(count)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort()
#ans=[1 for _ in range(N)]
size=len(A)
for i in range(N):
  j=i+1
  while size>j:
    if A[j]%A[i]==0:
      A.remove(A[j])
      size-=1
    else:j+=1
print(size)

Submission status: Wrong Answer

Solution code:
import collections

n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
c = collections.Counter(a)
data = list(set(a))
prime_bool = [True]*(max(a)+1)
prime_bool[0] = False
old_idx = 0
for i in range(len(data)):
  p = data[i]
  if prime_bool[p]:
    for j in range(old_idx+1, i):
      prime_bool[j] = False
    old_idx = i
    k = 2
    while k*p <= max(a):
      prime_bool[k*p] = False
      k += 1

count = 0
for i in range(len(prime_bool)):
  if prime_bool[i]:
    if c[i] > 1:
      count += 1
print(prime_bool.count(True) - count)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n = int(input())
arr = list(map(int, input().split()))
arr.sort()
count = 0
ap = defaultdict(int)
for i in range(n):
    if not ap[arr[i]]:
        count += 1
    if i == 0 or (i > 0 and arr[i] != arr[i-1]):
        for j in range(arr[i], 1000001, arr[i]):
            ap[j] = 1
print(count)

Submission status: Wrong Answer

Solution code:
#!python3

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

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

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

    ax = max(A)+1
    dp = [0]*ax
    for ai in A:
        da = dp[ai]
        if da > 1:
            continue
        dp[ai] += 1
        if da == 0:
            for aj in range(2*ai, ax, ai):
                dp[aj] = 2
        #print(dp)
    print(dp.count(1))


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict

def get_prime_factors(n):
    dd = defaultdict(lambda: 0)
    if n > 1:
        i = 2
        while i * i <= n:
            if n % i == 0:
                dd[i] += 1
                n /= i
                i = 2
            else:
                i += 1
        dd[n] += 1
    return dd

def factor_with(n, A):
    idx = 0
    orig_n = n
    i = A[idx]

    while i * i <= n or idx >= len(A):
        i = A[idx]

        if A[idx] == orig_n:
            idx+= 1
        elif n % i ==0:
            n /= i
            idx = 0
        else:
            idx += 1
    return n

    
def solve(N: int, A: "List[int]"):
    
    A.sort()
    count = 0

    divs = []
    for i in range(len(A)):
        f = True

        if i + 1 < len(A):
            if A[i-1] == A[i] or A[i] == A[i+1]:
                continue
        else:
            if A[i-1] == A[i] and len(A)!=1:
                continue
               

        for div in divs:
            if A[i] % div == 0:
                f = False
                break
        if f:
            divs.append(A[i])

    count = len(divs)

        
    # dd = defaultdict(lambda: (0, 10**6+1))
    
    # for a in A:
    #     d = get_prime_factors(a)

    #     flag = True
    #     for prime, value in d.items():
    #         dd_val, dd_mn = dd[prime]
            
    #         if a % dd_mn==0:
    #             flag = False
    #             break

    #         dd[prime] = (dd_val + value, min(dd_mn, a))

    #     if flag:
    #         count+= 1

    print(count)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

N = int(input())


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

A.sort()

s=0
for i in range(len(A)):
    if i!=N-1:
        if A[i]==A[i+1]:
            s+=1
            continue
    if i!=0:
        if A[i]==A[i-1]:
            s+=1
            continue
    if i==0:
        continue
    for j in range(i):
        if A[i] % A[j] == 0:
            s += 1
            break
        if A[i]<(A[j])**2:
            break

print(N-s)

Submission status: Wrong Answer

Solution code:
n = int(input())
search = list(map(int,input().split()))
search.sort()
double = set([])
for i in range(n-1):
    if search[i+1] == search[i]:
        double.add(search[i])
dp = [1]*(search[-1]+1)
for i in search:
    k = 2*i
    while k <= search[-1]:
        if dp[k]:
            dp[k] = 0
            k += i
        else:
            break
ans = 0
for i in search:
    if i in double:
        continue
    ans += dp[i]
print(ans)

Submission status: Wrong Answer

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

t = [True] * (10 ** 6 + 1)
d = {}
for a in A:
    d.setdefault(a, 0)
    d[a] += 1
    if d[a] > 1:
        t[a] = False

for a in sorted(set(A)):
    for i in range(a + a, 10 ** 6 + 1, a):
        t[i] = False
print(t.count(True))

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
A = list(map(float, input().split()))
A = np.sort(A)
D= np.ones(N)
ans= 0
for i in range(2, 1001):
    j=0
    c=1
    g=0
    while j<len(A):
        if A[j] % i == 0:
            if A[j] == i:
                g = 1
            if g == 1:
                A = np.delete(A, j)
                j -=1
                if c == 1:
                    ans += 1
                    c = 0
            if g == 0:
                while A[j] % i == 0:
                    A[j] /= i
                if A[j] == 1:
                    A = np.delete(A, j)
                    j -=1
                    if c == 1:
                        ans += 1
                        c = 0
        j += 1
    if len(A) == 0:
        break
q = ans+len(A)
if q < 2:
    print(0)
else:
    print(q)

Submission status: Wrong Answer

Solution code:
def main():
    from collections import Counter
    n, *a = map(int, open(0).read().split())
    x = Counter(a)
    y = [k for k, v in x.items() if v == 1]
    if len(y) == 0:
        print(0)
        exit()

    z = sorted(y)

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

    l = z[-1]
    m = [0] * (l + 1)
    for i in z:
        if m[i] == 0:
            m[i] = 1
        j = l // i
        for k in range(2, j + 1):
            m[i * k] = -1

    ans = m.count(1)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, *a = map(int, open(0).read().split())
a.sort()
am = a[-1] + 1000
dp = [True] * am
ans = 0
dup = set()
for x in a:
    d = dp[x]
    if d:
        ans += 1
        for i in range(x, am, x):
            dp[i] = False
        dp[x] = None
    elif d == None:
        dup.add(d)

print(ans - len(dup))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())))
ans = [True] * n

from collections import Counter

ca = Counter(a)
for i,c in ca.items():
    if c>1:
        for j in range(n):
            if a[j]==i:
                ans[j]=False

for i in range(n):
    for j in range(i+1,n):
        if not ans[j]:
            break
        if a[j]%a[i]==0:
            ans[j] = False

print(sum(a for a in ans))

Submission status: Wrong Answer

Solution code:
from collections import Counter

input()
s = set(map(int, input().split()))
t = {k for k, v in Counter(s).items() if v == 1} 
r = int(1 in t)
if 1 not in s:
  for x in t:
    i = 2
    while i * i <= x:
      if x % i == 0 and  {i, x // i} & s:
        break
      i += 1
    else:
      r += 1
print(r)

Submission status: Wrong Answer

Solution code:
import collections

N = int(input())
A = list(map(int, input().split()))
A = collections.Counter(A)
B = []
for i in A:
    if A[i] == 1:
        B.append(i)
B = sorted(B)
if len(B) == 0:
    print(0)
    exit()
mb = B[-1]
ok = [True] * (max(B)+1)

for b in B:
    if not ok[b]:
        continue
    k = 2
    while k*b <= mb:
        ok[k*b] = False
        k += 1
        
ans = 0
for b in B:
    if ok[b]:
        ans += 1

print(ans)

Submission status: Wrong Answer

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

A.sort()
max_num = max(A)
#sub_count = [x for x in set(A) if A.count(x) > 1]


if len(set(A)) == 1:
    print(0)
else:
    i = 0
    count = 0
    while True:
        if A == []:
            break
        count += 1
        look = A[0]
        del A[0]
        del_num = []
        for j in range(len(A)):
            if A[j] % look == 0:
                del_num.append(j)
        del_num = sorted(del_num, reverse=True)
        for j in del_num:
            del A[j]
    print(count)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

T = A
for i in range(N - 1):
    T = np.append(T, A)
T = T.reshape((N, N))
U = A.reshape((N, 1))

Ans = T % U
print(Ans)
count = 0

for i in range(N):
    if np.count_nonzero(Ans[:, i] == 0) == 1:
        count += 1

print(count)

Submission status: Wrong Answer

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

B = [0]*(max(A)+1)

for i in A:
  B[i]+=1
  if B[i] == 1:
    for j in range(i*2, max(A), i):
      B[j]+=100
print(B.count(1))

Submission status: Wrong Answer

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

sorted_A = sorted(A)
result = 0

# 倍数を管理するテーブル
lendp = sorted_A[-1] + 1
dp = [0] * lendp

if N == 1:
    print(0)
else:
    for a in sorted_A:
        if dp[a] == 0:
            result += 1
            b = a
            while b < lendp:
                dp[b] += 1
                b += a

    print(result)

Submission status: Wrong Answer

Solution code:

N = int(input())


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

A.sort()

d=[A[0]]
s=0
for i in range(len(A)):
    if i!=N-1:
        if A[i]==A[i+1]:
            s+=1
            continue
    if i!=0:
        if A[i]==A[i-1]:
            s+=1
            continue
    if i==0:
        continue
    for j in range(len(d)):
        if A[i] % d[j] == 0:
            s += 1
            break
        if A[i]<(d[j])**2:
            d.append(A[i])
            break
        if j == len(d)-1:
            d.append(A[i])

print(N-s)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter
def input(): return sys.stdin.readline().rstrip()
# ----------------------------------------------------------- #

n = int(input())
A = list(int(x) for x in input().split())
A.sort()
counter = Counter(A)
ans = 0
cache = set()
for a in A:
    if a in cache:
        continue
    tmp = a
    while tmp < 10**6:
        cache.add(tmp)
        tmp += a
    if counter[a] == 1:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

A.sort()
d = deque()

ans = 0
max_A = max(A)
ban = [0]*(max_A+1)
again = list()

for i in range(N-1):
    if A[i] != A[i+1]:
        d.append(A[i])
    else:
        again.append(A[i])
if A[N-1] != A[N-2]:
    d.append(A[N-1])

for num in again:
    ban_num = num
    while ban_num <= max_A:
        ban[ban_num] = 1
        ban_num += num
 
while len(d):
    num = d.popleft()
    if ban[num] != 1:
        ans += 1
        ban_num = num
        while ban_num <= max_A:
            ban[ban_num] = 1
            ban_num += num

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
MX = 10**6
def main():
    input = sys.stdin.readline
    N = int(input())
    *A, = map(int, input().split())
    S = set(A)
    C = [0] * (MX + 1)
    for a in A:
        C[a] += 1
    ans = 0
    for a in A:
        if C[a] >= 2: continue
        for d in dv(a):
            if C[d] > 0:
                break
        else:
            ans += 1
    print(ans)

def dv(x):
    res = [1]
    for i in range(2, int(x ** 0.5) + 1):
        if x % i == 0:
            res.append(i)
            res.append(x // i)
    return res

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

def main():
    N = int(input())
    A = list(map(int, input().split()))
    
    A_dict = {}
    for a in A:
        if a in A_dict.keys():
            A_dict[a] += 1
        else:
            A_dict[a] = 1

    black_list = []
    ans = 0
    for a in sorted(A_dict.keys()):
        for b in black_list:
            if a % b == 0:
                break
            if b > a**(1/2):
                if A_dict[a] == 1:
                    ans += 1
                black_list.append(a)
                break
        else:
            if A_dict[a] == 1:
                ans += 1
            black_list.append(a)
    print(ans)
main()

Submission status: Wrong Answer

Solution code:
n=int(input())
a= list(map(int, input().split()))    
t=set([x for x in set(a) if a.count(x)>1])
print(0)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n = int(input())
arr = list(map(int, input().split()))
arr.sort()
count = 0
ap = defaultdict(int)
for i in range(1, n):
    if arr[i] == arr[i-1]:
        ap[arr[i]] = 1

for i in range(n):
    if not ap[arr[i]]:
        count += 1
        for j in range(arr[i], 1000001, arr[i]):
            ap[j] = 1
print(count)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

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

# エラトステネスの篩っぽく処理
ans_list = [True for _ in range(A[-1] + 1)]
ans = 0

# ダブリを省くために先に数える
c = Counter(A)

for a in A:
    if ans_list[a] == True:
        if c[a] == 1:
            ans += 1
        i = 2
        while a * i <= A[-1]:
            ans_list[a * i] = False
            i += 1

print(ans)

Submission status: Wrong Answer

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

a_list.sort()

tf_list=[1]*n

for i in range(n):
  for j in range(i+1,n-i):
    #print(i,j)
    if a_list[j] % a_list[i]==0:
      tf_list[j]=0
      if a_list[j] == a_list[i]:
        tf_list[i]=0
      

#print(tf_list)      
print(sum(tf_list))

Submission status: Wrong Answer

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

MAXN = max(A)
B = [False]*(MAXN+1)
for c in C:
    if c[1] == 1:
        B[c[0]] = True
ans = 0
for i in range(MAXN + 1):
    if B[i]:
        ans += 1
        B[i::i] = [False]*(MAXN//i)
print(ans)

Submission status: Wrong Answer

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

import math

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

def is_prime(n):
    if n == 1: return False

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

    return True

avg = sum(A)/len(A)
if avg == A[0]:
	print(0)

else:
	t = [0] * N
	for i in range(N):
		if M[A[i]] == 1 or is_prime(A[i]):
			M[A[i]] = 1

		else:
			for j in range(N):
				if i != j:
					if A[i] % A[j] == 0:
						t[i] = 1
						break
				if j == N - 1:
					M[A[i]] = 1
	print(N - sum(t))