Problem:


Score : 400 points

Problem Statement

Given is a number sequence A of length N.

Find the number of integers i \left(1 \leq i \leq N\right) with the following property:

For every integer j \left(1 \leq j \leq N\right) such that i \neq j , A_j does not divide A_i.

Constraints

All values in input are integers.

1 \leq N \leq 2 \times 10^5

1 \leq A_i \leq 10^6

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answer.

Sample Input 1

5
24 11 8 3 16

Sample Output 1

3

The integers with the property are 2, 3, and 4.

Sample Input 2

4
5 5 5 5

Sample Output 2

0

Note that there can be multiple equal numbers.

Sample Input 3

10
33 18 45 28 8 19 89 86 2 4

Sample Output 3

5



Sample input:
5
24 11 8 3 16


Sample output:
3

Submission status: Wrong Answer

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



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

ans=0

for i in range(N):
    a=A[i]
    if nums[a-1]==0:
        ans+=1
        
        if a>MAX//2:
            continue
    if i!=0:
        if nums[a-1]==1 and A[i-1]==a:
            ans-=1
            

    count=1
    num=a
    while num<=MAX:
        nums[num-1]+=1
        count+=1
        num=a*count
    
#print(nums)
print(ans)

Submission status: Wrong Answer

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

dellist = []
# A[0]は最小なので同じ数字を除いてそれよりも大きい他の数では割り切れない。
i = 0
while(i < len(A)):
    if A[i] > 1000:
        break
    j = i+1
    poplist = []
    while(j < len(A)):
        if A[j]%A[i] == 0: # 割り切れちゃった場合
            # A[j]をあとで消すために控える
            poplist.append(j)
            # A[i]とA[j]が同じ数字なら、最後にA[i]も消す必要があるので、
            # A[i]を削除リストに入れる
            if A[i]  == A[j]:
                dellist.append(A[i])
                
        j += 1
        
    # poplistにあるA[]を消す
    # 前から消していくと順番が狂うので、後ろから消す。参考↓
    # https://gammasoft.jp/blog/remove-multiple-elements-from-python-list/
    for k in sorted(poplist, reverse=True):
        A.pop(k)
    # A[i]で割り切れるものは探しきって、次のA[i+1]は割り切れないもの。
    # 次はA[i+1]について考える
    i += 1

# remove は、指定した要素がlistに含まれていないとエラーを吐くみたいなので、
# 重複を排除する
dellist = list(set(dellist))
    
for i in dellist:
    A.remove(i)

# print(A)
print(len(A))
# print(dellist)

Submission status: Wrong Answer

Solution code:
def main():
  n=int(input())
  a=sorted(map(int,input().split()))
  #maxa=a[-1]+1
  af=[False]*n
  #tf=[False]*maxa
  r=0
  n-=1
  for i in range(n):
    a_i=a[i]
    #print(a_i)
    if af[i] ==False:
      r+=1
      for j in range(i,n):
        if a[j] % a_i == 0:
          #print("aj:"+str(a[j]))
          af[j]=True
  if af[-1] ==False:
    r+=1
  print(r)
main()

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int,input().split()))
a2 = sorted(a,reverse = True)
c = 0
for i in range(N-1):
  d =0 #カウンタの初期化
  for j in range(N-i-1):
    if a2[i] % a2[N-1-j] == 0:
      d = 1
      break
    if a2[N-1-j]*2 > a2[i]:
      break
  if d == 0:
    c =c+1
if not a2[N-1] == a2[N-2]:
  c = c+1
print(c)

Submission status: Wrong Answer

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



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

ans=0

for i in range(N):
    a=A[i]
    if nums[a-1]==0:
        ans+=1
        #print(a)
        if i!=0:
            if nums[a-1]==1 and A[i-1]==a:
                ans-=1
                #print("aaaaa")
        if a>MAX//2:
            continue
    if i!=0:
        if nums[a-1]==1 and A[i-1]==a:
            ans-=1
            print("aaaaa")

    count=1
    num=a
    while num<=MAX:
        nums[num-1]+=1
        count+=1
        num=a*count
    
#print(nums)
print(ans)

Submission status: Wrong Answer

Solution code:
n,*a=map(int,open(0).read().split())
d=[0]*(max(a)+1)
ans=0
for i in a:
  d[i]+=1
for i in range(max(a)+1):
  if d[i]:
    if d[i]==1:
      ans+=1
    for j in range(i,max(a),i):
      d[j]=0
print(ans)

Submission status: Wrong Answer

Solution code:
import collections

n = int(input())
a = list(map(int, input().split()))
#n = 2 * 10**5
#a = [i for i in range(1, n+1)]

a.sort()
def Eratosthenes(x):
    c = collections.Counter(x)
    cnt = 0
    nmax = x[-1]
    is_prime = [True] * (nmax+1)
    for i in range(1, nmax+1):
        if not is_prime[i]:
            continue
        if i in x:
            for j in range(i*2, nmax+1, i):
                is_prime[j] = False
    for i in range(1, nmax):
        if c[i] > 1:
            is_prime[i] = False
    for i in range(1, nmax+1):
        if is_prime[i] == True and i in a:
            cnt += 1
    print(cnt)

Eratosthenes(a)

Submission status: Wrong Answer

Solution code:
import numpy as np
 
n = int(input())
a = list(set(map(int, input().split())))
a.sort()
l = len(a)
dp = [0 for _ in range(a[-1] + 1)]

for i in range(l):
    for j in range(a[i], a[-1] + 1, a[i]):
        dp[j] += 1
#for i, result in enumerate(dp):
#    print(i, result)
#print("#" * 15)
ans = 0
a = set(a)
for x in a:
    if dp[x] == 1:
        ans += 1
print(ans)

Submission status: Wrong Answer

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



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

ans=0

for i in range(N):
    a=A[i]
    if nums[a-1]==0:
        ans+=1
        print(a)
        if i!=0:
            if nums[a-1]==1 and A[i-1]==a:
                ans-=1
                #print("aaaaa")
        if a>MAX//2:
            continue
    if i!=0:
        if nums[a-1]==1 and A[i-1]==a:
            ans-=1
            print("aaaaa")

    count=1
    num=a
    while num<=MAX:
        nums[num-1]+=1
        count+=1
        num=a*count
    
#print(nums)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
l = [0] * A[-1]
for i in range(N):
    l[A[i] - 1] += 1
for i in range(N):
    if l[A[i] - 1] > 1:
        l[A[i] - 1] = 0
    elif l[A[i] - 1] == 0:
        continue
    else:
        temp = A[i]
        while True:
            temp += A[i]
            if temp > A[-1]:
                break
            l[temp - 1] = 0
print(sum(l))

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 = defaultdict(lambda : 0)
    
    for i in range(len(A)):
        if divs.get(A[i], False):
            divs[A[i]] += 1
            break

        f = True               
        for div in divs.keys():
            if A[i] % div == 0:
                f = False
                break
        if f:
            divs[A[i]] += 1
    
    for key, value in divs.items():
        if value == 1:
            count += 1
    
        
    # 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:
import math
N=int(input())
A=list(map(int, input().split()))
A=sorted(A)
if max(A)==min(A):
    print(0)
    exit()



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

ans=0

for i in range(N):
    a=A[i]
    if nums[a-1]==0:
        ans+=1
        print(a)
        if i!=0:
            if nums[a-1]==1 and A[i-1]==a:
                ans-=1
                print("aaaaa")
        if a>MAX//2:
            continue
    if i!=0:
        if nums[a-1]==1 and A[i-1]==a:
            ans-=1
            print("aaaaa")

    count=1
    num=a
    while num<=MAX:
        nums[num-1]+=1
        count+=1
        num=a*count
    
#print(nums)
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])**2:
            break
        if j == i-1:
            break

print(N - s)

Submission status: Wrong Answer

Solution code:
if __name__ == "__main__":
    # Problem D
    N = int(input())
    A_list = sorted(map(int, input().split(' ')), reverse=True)
    A = set(A_list)
    counter = 0
    continue_flag = False
    if len(A) == 1:
        print(0)
    else:
        while len(A_list) > 0:
            if not continue_flag:
                target = A_list.pop()
            for _a in A:
                continue_flag = False
                if _a%target==0 and _a!=target:
                    A.remove(_a)
                    continue_flag = True
                    break

        print(len(A))

Submission status: Wrong Answer

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
# from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint
# from statistics import mean,median,mode

INF = float("inf")

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    # lsはソート済みであること
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

def I():
    return int(input())

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

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

def CI(n):
    return [ int(input()) for _ in range(n) ]

def LI(n):
    return [ list(map(int,input().split())) for _ in range(n) ]

def S():
    return input()

def MS():
    return input().split()

def RS():
    return list(input().split())

def CS(n):
    return [ input() for _ in range(n) ]

def LS(n):
    return [ list(input().split()) for _ in range(n) ]

n = I()
a = RI()

a.sort()

na = []
for i in a:
    c = mycount(a,i)
    if c==1:
        na.append(i)
    else:
        pass

a = copy(na)

if len(a)==0:
    print(0)
    exit()

M = max(a)

# nまでの自然数が素数かどうかを表すリストを返す
# Sieve of Eratosthenes
def makePrimeChecker(n):
    isPrime = [True] * (n + 1)
    isPrime[0] = False
    isPrime[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if isPrime[i]:
            for j in range(i * i, n + 1, i):
                isPrime[j] = False
    return isPrime

dp = [False]*(M+1)

for i in a:
    dp[i] = True

for i in range(1,M+1):
    if dp[i]:
        for j in range(i+i,M+1,i):
            dp[j] = False

count = 0

# print(dp)

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

ans = count
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    Amax=A[-1]+1
    dp = [True]*Amax
    ans=0
    a_temp=0
    a_tempcheck=False
    if A[0]==1:
        ans=0
    else:
        for a in A:
            if dp[a]:
                ans+=1
                for i in range(a, Amax, a):
                    dp[i] = False
                a_temp=a
            elif a_temp==a:
                if not a_tempcheck:
                    ans-=1
                    a_tempcheck=True
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

A.sort()

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

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

for num in again:
    ban_num = num
    while ban_num <= max_A:
        ban[ban_num] = 1
        ban_num += num
 
for num in A:
    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


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))


n = I()
a = LI()
# 0 ~ 10 ** 6 + 1 までの数のaでの出現回数
cnt = [0] * (10 ** 6 + 1)
for ele in a:
    if ele not in cnt:
        cnt[ele] += 1
# 1個だけあるaの要素のリスト
only_one_a = [i for i in range(1, 10 ** 6 + 1) if cnt[i] == 1]


a = list(set(a))  # 同じ数を排除した a
cnt = [0] * (10 ** 6 + 1)  # 0 ~ 10 ** 6 + 1 までの数の a における出現していないか/したか

# 計算量: O(n * log 10**6)
for ele in a:
    # ele 自身以外の ele の倍数について、印をつける
    for m in range(ele * 2, 10 ** 6 + 1, ele):
        cnt[m] = 1

ans = 0

for ele in only_one_a:
    #
    if cnt[ele] == 0:
        ans += 1

print(ans)

Submission status: Wrong Answer

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

b = sorted(set(a))

maxA = max(b)
dp = [0]*(maxA+1)
count = 0

for e in b:
    for i in range(e,maxA+1,e):
        dp[i] += 1

for e in b:
    if dp[e] == 1:
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline
    n=int(readline())
    arr=list(map(int, readline().rstrip().split()))
    if n==1:
        print(0)
        return
    dic={}
    for a in arr:
        dic[a]=dic.get(a,0)+1
    ans=0
    for i in range(n):
        h=int(arr[i]**(1/2))+1
        flg=0
        for x in range(1,h):
            if arr[i]%x!=0:
                continue
            y = arr[i]//x
            if x==1:
                if dic.get(x,0) > 0 or dic.get(y,0) > 1:
                    flg=1
                    #print(arr[i],x,y)
            elif dic.get(x,0) > 0 or dic.get(y,0) > 0:
                flg=1
                #print(arr[i],x,y)
        if flg==0:
            ans+=1
            #print("ans:", arr[i])
    print(ans)
    return

    #print(arr)
    ans=0
    for i in range(n):
        flg=0
        if i==0:
            if arr[i]!=arr[i+1]:
                ans+=1
            continue

        h=arr[i]//2+1
        for j in range(0,i):
            if arr[i]%arr[j]==0:
                flg=1
                break
            if arr[j] > h:
                break
        if flg==0:
            if (i+1)<n:
                if arr[i]==arr[i+1]:
                    flg=1
        if flg==0:
            ans+=1
    print(ans)
    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int, input().split()))
A.sort()
inf=10**6+1
t=[True for i in range(inf)]

ans=0
for j in range(len(A)):
    if j==len(A)-1 and t[A[j]]:
        ans+=1
    if t[A[j]] and j+1<=N-1 and A[j+1]!=A[j]:
        ans+=1
        for nums in range(A[j],inf,A[j]):
            t[nums]=False
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
a = np.sort(np.array([int(x) for x in input().split()]))
dp = [True]*n

if np.all(a==a[0]):
    print(0)
else:
    for i in a:
        for j in np.where(a%i==0)[0][1:]:
            dp[j] = False
    print(dp.count(True))

Submission status: Wrong Answer

Solution code:
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))


n = I()
a = LI()
# 0 ~ 10 ** 6 + 1 までの数のaでの出現回数
cnt = [0] * (10 ** 6 + 1)
for ele in a:
    if ele not in cnt:
        cnt[ele] += 1
# 1個だけある要素のリスト
only_one_a = [i for i in range(1, 10 ** 6 + 1) if cnt[i] == 1]


a = list(set(a))  # 同じ数を排除した a
cnt = [True] * (10 ** 6 + 1)  # 0 ~ 10 ** 6 + 1 までの数の a における出現していないか/したか

# 計算量: O(n * log 10**6)
for ele in a:
    # ele 自身以外の ele の倍数について、印をつける
    for m in range(ele * 2, 10 ** 6 + 1, ele):
        cnt[m] = False

ans = 0
for ele in only_one_a:
    #
    if cnt[ele]:
        ans += 1

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:
import collections
n = int(input())
lst = list(map(int, input().split()))

c = collections.Counter(lst)

st = set(lst)
st = sorted(st)
stn = len(st)

visited = [0 for _ in range(stn)]
ans = stn

for i in range(stn):
    if c[st[i]] > 1:
        ans -= 1
    elif visited[i] == 0:
        for j in range(i+1,stn):
          if lst[j] % lst[i] == 0 and visited[j] == 0:
            ans -= 1
            visited[j] = 1

print(ans)

Submission status: Wrong Answer

Solution code:
import math

def main():
  N = int(input())
  A = list(map(int, input().split()))
  A.sort()
  MAX = A[-1]
  dp = [True] * MAX
  c = [0] * MAX
  ans = 0

  

  for v in A:
    c[v - 1] += 1

    if(not dp[v - 1] and c[v - 1] > 1):
      continue

    e = v * 2    
    while e < MAX:
      dp[e-1] = False
      e += v
      
  for v in A:
    if dp[v - 1] and c[v - 1] == 1:
      ans += 1

  print(ans)

if __name__ == "__main__":
  main()

Submission status: Wrong Answer

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

flag=[0]*n
l.sort()

if len(set(l))==1:
    print(0)

else:
    for j in range(len(l)):
        for i in range(j+1, len(l)):
            if flag[i]==1:
                continue
            elif l[i]%l[j]==0:
                flag[i]=1
    print(flag.count(0))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
dp = [0]*(1000000+1)
cnt = 0
for i in range(len(a)):
  if dp[a[i]]==1:
    continue
  elif i!=len(a)-1 and a[i+1]==a[i]:
    dp[a[i]] = 1
    continue
  cnt += 1
  dp[a[i]] = 1
  j = 2
  while(a[i]*j<=a[-1]):
    dp[a[i]*j] = 1
    j += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    Amax=A[-1]+1
    dp = [True]*Amax
    ans=0
    a_temp=0
    a_tempcheck=False
    for a in A:
        if dp[a]:
            ans+=1
            for i in range(a, Amax, a):
                dp[i] = False
            a_temp=a
        elif a_temp==a:
            if not a_tempcheck:
                ans-=1
                a_tempcheck=True
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys


sys.setrecursionlimit(10 ** 7)
def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


n = I()
a = LI()
# 0 ~ 10 ** 6 + 1 までの数のaでの出現回数
cnt = [0] * (10 ** 6 + 1)
for ele in a:
    if ele not in cnt:
        cnt[ele] += 1
# 1個だけある要素のリスト
only_one_a = [i for i in range(1, 10 ** 6 + 1) if cnt[i] == 1]


a = list(set(a))  # 同じ数を排除した a
cnt = [True] * (10 ** 6 + 1)  # 0 ~ 10 ** 6 + 1 までの数の a における出現していないか/したか

# 計算量: O(n * log 10**6)
for ele in a:
    # ele 自身以外の ele の倍数について、印をつける
    for m in range(ele * 2, 10 ** 6 + 1, ele):
        cnt[m] = False

ans = 0
for ele in only_one_a:
    #
    if cnt[ele]:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    a = [int(i) for i in ipt().split()]
    yn = [0]*(10**6+1)
    for i in a:
        yn[i] += 1

    a1 = a.count(1)
    if a1 == 1:
        print(1)
        exit()
    elif a1 > 1:
        print(0)
        exit()

    ans = 0
    for i in a:
        f = True
        if yn[i] != 1:
            continue
        for j in range(2,10**3+1):
            if i%j == 0:
                if yn[j]:
                    f = False
                    break
                if yn[i//j]:
                    f = False
                    break
        if f:
            ans += 1

    print(ans)

    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

a = list(set(a))
a.sort()

b=[]

if len(a) <= 1:
    print(0)

else:
    for i in range(len(a)):
        for i2 in range(i+1,len(a)):
            if a[i2]%a[i] == 0:
                b.append(a[i2])
    c = [x for x in a if x not in b]
    print(len(c))

Submission status: Wrong Answer

Solution code:
N = int(input())
#N = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
C = [True]*len(A)
for i in range(len(A)):
    if C[i]==False:
        continue
    a=A[i]
    for j in range(i+1, len(A)):
        if A[j]%a==0:
            C[j] = False
count = len([i for i in C if i==True])
if A[0] in A[1:]:
    count-=1
print(count)

Submission status: Wrong Answer

Solution code:
import copy 
import sys
N=int(input())
A=list(map(int,(input().split())))
new_A=list(set(A))
new_A.sort()
tmp_A = copy.copy(new_A)
count=0
if(1 in new_A):
  print(1)
  sys.exit()
try:
  for i in new_A[:]:
    tmp_A.remove(i)
    for j in tmp_A[:]:

      if(i%j==0):
        new_A.remove(i)
    tmp_A=copy.copy(new_A)

  if(len(new_A)==1):
    print(0)
  else:
    print(len(new_A))
except:
  print(len(new_A))

Submission status: Wrong Answer

Solution code:
import math

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

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
	tt = 0
	for i, v in enumerate(A):
		if i > 0 and A[i] == A[i - 1]:
			if tt == 1:
				t += 1
			continue
		elif is_prime(A[i]):
			tt = 0
			continue
		else:
			for j in range(i + 1, N):
				if A[i] % A[j] == 0:
					t += 1
					tt = 1
					break
				if j == N - 1:
					tt = 0
	print(N - t)

Submission status: Wrong Answer

Solution code:
N = int(input())

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


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

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

print(dp.count(1))

Submission status: Wrong Answer

Solution code:
from collections import Counter
N=int(input())
A=list(map(int,input().split()))
A=sorted(A)[::-1]
if Counter(A)[A[-1]]>1:
    ans=-1
else:
    ans=0
B=[]
while A:
    x=A.pop()
    B.append(x)
    for i in A[::-1]:
        if i%x==0:
            A.remove(i)
print(len(B)+ans)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from collections import Counter
    input=sys.stdin.readline
    n=int(input())
    b=list(map(int,input().split()))
    a=Counter(b)
    ans=0
    for k in b:
        divisors=set()
        for i in range(1,int(k**0.5)+1):
            if k%i==0:
                divisors.add(1)
                if i!=k//i:
                    divisors.add(k//i)
        for j in divisors:
            if (j in a and j!=k)or(j==k and a[j]>1):
                break
        else:
            ans+=1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import collections
n = int(input())
lst = list(map(int, input().split()))

c = collections.Counter(lst)
lst.sort()

st = set(lst)
stn = len(st)
visited = [0 for _ in range(stn)]
ans = stn

for i in range(stn):
    if c[lst[i]] > 1:
        ans -= 1
    elif visited[i] == 0:
        for j in range(i+1,stn):
          if lst[j] % lst[i] == 0 and visited[j] == 0:
            ans -= 1
            visited[j] = 1

print(ans)

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;
        continue
    times = 2
    while a[i] * times < a[-1]:
        r = bisect.bisect_right(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:
import numpy as np

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

a = list(set(a))

count = 0
for i in range(len(a)):
    ans = a[i] % np.array(a)
    if np.count_nonzero(ans == 0) == 1:
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N=int(input())
A=list(map(int,input().split()))
A=sorted(A)[::-1]
if Counter(A)[A[-1]]>0:
    ans=-1
else:
    ans=0
B=[]
while A:
    x=A.pop()
    B.append(x)
    for i in A[::-1]:
        if i%x==0:
            A.remove(i)
print(len(B)+ans)

Submission status: Wrong Answer

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

n = 10**6
prime = {i for i in range(2, n)}
for i in range(2, n):
    if i in prime:
        for j in range(i*2, n, i):
            if j in prime:
                prime.remove(j)
ans = 0
for i in range(N):
    if D[A[i]] == 1:
        if A[i] in prime or A[i] == 1:
            ans += 1
        else:
            flag = True
            for j in range(i):
                if A[i] % A[j] == 0:
                    flag = False 
                    break
                if A[j]*2 > A[i]:
                    break
            if flag:
                ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import math

def main():
  MAX = 10 ** 6
  N = int(input())
  A = list(map(int, input().split()))
  dp = [True] * MAX
  c = [0] * MAX
  ans = 0

  A.sort()

  for v in A:
    c[v - 1] += 1

    if(not dp[v - 1] and c[v - 1] > 1):
      continue

    e = v * 2    
    while e < MAX:
      dp[e-1] = False
      e += v
      
  for v in A:
    if dp[v - 1] and c[v - 1] < 2:
      ans += 1

  print(ans)

if __name__ == "__main__":
  main()

Submission status: Wrong Answer

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

dp = {}
double = {}
A_max = sortedA[-1:][0]
for i in A:
  if dp.get(i):
    double[i] = True
  dp[i] = True
for i in sortedA:
  j = 2
  while i * j <= A_max:
    if dp.get(i * j):
      dp[i * j] = False
    j += 1
count = 0
for key, value in dp.items():
  if double.get(key) is None and value:
    count += 1
if len(A) == 1:
  print(0)
else:
  print(count)

Submission status: Wrong Answer

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

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

from collections import Counter
c = Counter(A)

NMAX = 10 ** 6 + 10
dp = [True] * (NMAX + 1)
for k, v in c.items():
    for i in range(k * 2, NMAX + 1, k):
        dp[i] = False

count = 0
for k, v in c.items():
    if v > 1: continue
    if dp[k]: count += 1

print(count)

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(2,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:
n = int(input())
a = list(map(int , input().split()))
if len(set(a)) == 1:
    print(0)
    exit()

#a = list(sa)
a.sort()

#print(a)
import numpy as np
U=10**6 + 5
is_prime = np.zeros(U,np.bool)
#is_prime[2] = 1
is_prime[1::] = 1
M = int(U**.5)+1
for ai in a:#range(3,M,2):
    if is_prime[ai]:
        is_prime[ai*2::ai] = 0
    #print(is_prime.nonzero()[0])

ans = 0

import collections
cnt = collections.Counter(a)
for ai in a:
    if is_prime[ai] and cnt == 1:
        ans += 1

print(ans)

"""
sa = set()
for ai in a:
    if ai in sa:
        sa.discard(ai)
        continue
    sa.add(ai)
"""

"""
p = list(range(10**6+10))

a = list(sa)
a.sort()

print(a)

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

ans = 1
l = 1
for i in range(n):
    if lcm(a[i], l) < a[i] * l:
        continue
    l = lcm(a[i], l)
    ans += 1
print(ans)

"""

Submission status: Wrong Answer

Solution code:
def main():
    n, *a = map(int, open(0).read().split())

    m = max(a) + 1
    l = [0] * m
    for i in a:
        l[i] -= 2
        for j in range(i, m, i):
            l[j] += 1

    ans = l.count(-1)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(hoge) for hoge in input().split()]
A = list(range(2,1000001))
A.sort()
M = max(A)
dp = [False] * (M+ 1)
ans = 0
prev = -1
for a in A:
    if dp[a] == False:
        for j in range(2,1 + (M// a)):
            dp[a*j] = True
        if a != prev:
            ans += 1
        else:
            dp[a] = True
            ans -= 1
    prev = a
print(ans)