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 i!=0:
            if nums[a-1]==1 and A[i-1]==a:
                ans+=1
        if a>MAX//2:
            continue

    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:
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] == 1:
      ans += 1

  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]:
    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:
N = int(input())
As = list(map(int, input().split()))
st = set(As)
 
As.sort()
if N == 1:
  print(1)
  exit()

st = set(As)
m = As[-1]
rlt = 0
gb = set([])

for i in range(N):
  if i > 1 and As[i] == As[i-1]:
    gb.add(As[i])
    continue
  j = 2
  while As[i]*j <= m:
    if As[i]*j in st:
      gb.add(As[i]*j)
    j += 1

for a in As:
  if a not in gb:
    rlt += 1
    
print(rlt)

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
print(c)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
a.sort()
ans = 0
con = False
for i in range(1, n):
    if a[i] == a[i-1]:
        con = True
        a[i-1] = 0
    elif con:
        con = False
        ans -= 1
if con:
    ans -= 1

ng = [0] * 1050000
for i in range(n):
    if not a[i]:
        continue
    if not ng[a[i]]:
        ans += 1
        for j in range(2, 1050000//a[i]):
            ng[a[i]*j] = 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter
def input():
    return sys.stdin.readline()[:-1]
def main():
    N = int(input())
    A = sorted(list(map(int,input().split())))
    for k in range(max(A)):
        pass
    print(max(A))
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

import sys


def input():
    return sys.stdin.readline()

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]

def resolve():
    n = int(input().rstrip())
    a_list = list(map(int, input().split()))

    a_list.sort()

    cnt = 0

    for i in range(len(a_list)):
        num = a_list[i]
        # 最小の値は割れない
        if i == 0:
            if i < len(a_list)-1 and num == a_list[i+1]:
                continue
            elif num == a_list[i-1]:
                continue
            cnt += 1
            continue

        if i < len(a_list) - 1 and num == a_list[i + 1]:
            continue
        elif num == a_list[i-1]:
            continue
        prime_list = make_divisors(num)
        prime_list.pop()
        del prime_list[0]

        # 素数の場合割れないので次へ
        if len(prime_list) == 0:
            cnt += 1
            continue

        div_flag = False
        for pr in prime_list:
            if pr in a_list:
                div_flag = True
                break

        if not div_flag:
            cnt += 1

        """
        div_flag = False
        for j, num2 in enumerate(a_list):
            #print(num, num2)
            if i == j:
                break
            if num % num2 == 0:
                div_flag = True
                break

        if not div_flag:
            cnt += 1
        """
    print(cnt)


if __name__ == "__main__":
    resolve()

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())
mapping = [True] * (10**6 + 10)
a = sorted(map(int, input().split()))

last = None
for i in a:
    if i == 1:
        print(0)
        exit()
    if i == last:
        mapping[i] = False
        continue
    if not mapping[i]:
        last = i
        continue
    else:
        j = 2
        while i * j < len(mapping):
            mapping[i*j] = False
            j += 1
        last = i

print(sum([1 for i in a if mapping[i]]))

Submission status: Wrong Answer

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


#print(A)

MAX = 10**6+1000
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:
import sys
def input():
    return sys.stdin.readline()[:-1]
def main():
    N = int(input())
    A = sorted(list(map(int,input().split())))
    print(max(A))
if __name__ == '__main__':
    main()

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(1, a_max // a[0]+1):
    dp[a[0] * k] = 0

for i in range(1, n):
    if dp[a[i]] == 1:
        count += 1
        for k in range(1, 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()))

A.sort()

maxnum = A[-1]
checklist = [True]*(maxnum+1)
before = 0

for a in A:
    if before == a:
        checklist[a] = False
        continue
    num = 1
    while num * a <= maxnum:
        checklist[a * num] = False
        num += 1
    before = a

ans = 0
for i in A:
    ans += checklist[i]
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter



N = input()
A=list(map(int,input().split()))
B=list(set(A))
C= sorted(B)
l = len(C)

flg = [0] * 10**6

if l == 1:
    print(0)
    exit()

if 1 in C:
    print(0)
    exit()

ans = 0
max = C[l-1]
counter = Counter(C)
for i in range(2,10**6):
    if counter[i] == 0:
        continue
    if flg[i] == 0 and counter[i] > 0:
        ans = ans + 1
    for j in range(10**6//i):
        flg[i*j] = 1

print(ans)

Submission status: Wrong Answer

Solution code:
# MAX = int(1e6)+2


n = int(input())
lis = list(map(int,input().split()))
lis.sort()
MAX = lis[-1]
lis2 = [0]*(MAX+1)
# lis.sort()
# m = max(lis)
ans = 0

for num in lis:
    for i in range(num, MAX, num):
            lis2[i] += 1

for j in set(lis):
    if lis2[j] == 1:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

A.sort()

maxnum = A[-1]
checklist = [True]*(maxnum+1)
before = 0

for a in A:
    if before == a:
        continue
    num = 1
    while num * a <= maxnum:
        checklist[a * num] = False
        num += 1
    before = a

ans = 0
for i in A:
    ans += checklist[i]
print(ans)

Submission status: Wrong Answer

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

l = sorted(a)
dp = [True] * (max(l) + 1)
ans = 0

if l[0] == max(l):
    print(0)
    exit()

for i in range(n):
    if dp[l[i]] == True:
        ans = ans + 1
        for j in range(n):
            tmp = l[j]
            if tmp % l[i] == 0:
                dp[tmp] = False

#print(dp)
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]):
      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:
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)

if len(prime) == 1:
    print(0)
else:
    print(len(prime))

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
print(count)

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] and A[i] % A[j] == 0:
            s += 1
            break
        if A[i] < (A[j])**2:
            break

print(N - s)

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()))
    A.sort()

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

    for a in c.keys():
        tmp = a * 2
        if tmp <= 10**6:
            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:
import numpy as np
 
n = int(input())
a = list(map(int, input().split()))
a.sort()
dp = [True for _ in range(a[-1])]

for x in a:
    if dp[x - 1] == False: continue
    else:
        multiply = x * 2
        while multiply <= a[-1]:
            dp[multiply - 1] = False
            multiply += x
ans = 0
for x in set(a):
    if dp[x - 1] is True:
        ans += 1
print(ans)

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(2, m_a//i+1):
            dp[j*i] -=100

print(dp.count(1))

Submission status: Wrong Answer

Solution code:
def main():
    from sys import stdin
    n = int(input())
    a = list(map(int, stdin.readline().split()))
    a.sort()
    amax = max(a)+1
    e = [True]*amax
    Alice = set()
    Bob = set()
    ans = 0

    for i in range(n):
        if e[a[i]] == True:
            Alice.add(a[i])
            for j in range(a[i], amax, a[i]):
                e[j] = False
        else:
            if e[a[i]] in Alice:
                Bob.add(a[i])

    print(len(Alice - Bob))

if __name__ == "__main__":
    main()

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
    # print(A)

    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:
#!/usr/bin/env python3

import sys
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import Fraction               # Fraction(a, b) => a / b ∈ Q. note: Fraction(0.1) do not returns Fraciton(1, 10). Fraction('0.1') returns Fraction(1, 10)
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79e+308
    # inf = 2 ** 63 - 1             # (for fast JIT compile in PyPy) 9.22e+18
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def isp():   return input().split()
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())


    def remove_duplicate_all(L):
        cnt = Counter(L)
        buf = []
        for num in L:
            if cnt[num] == 1:
                buf.append(num)
        return buf

    def fill_mul_false(num, table):
        for ind in range(num*2, 10**6+1, num):
            table[ind] = False
    
    
    n = ii()
    command = lmi()
    command = remove_duplicate_all(command)
    table = [False] * (10 ** 6 + 1)
    for num in command:
        table[num] = True
    
    for num in command:
        if table[num]:
            fill_mul_false(num, table)
    
    print(table.count(True))



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7


N = ri()
A = rl()

import collections
cnt = collections.Counter(A)
A = []
for k, v in cnt.items():
	if v == 1:
		A.append(k)
N = len(A)

A.sort()
h = {}
for a in A:
	h[a] = 1
ans = 0
for i in range(N):
	if A[i] in h:
		ans += 1
	b = A[i]
	while b <= 10**6:
		if b in h:
			del h[b]
		b += A[i]
print(ans)

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

maxA = max(a)
dp = [1]*(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*2,maxA+1,e):
                dp[i] = 0

    print(count)

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
  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:
import copy

def main():
  N = int(input())
  A = list(map(int, input().split()))
  A.sort()
  devide = sorted(set(A), key=A.index)
  target = copy.copy(devide)
  
  i = 0
  length_devide = len(devide)
  
  if length_devide == 1:
    print(0)
    exit()
    
  while i < length_devide:
    j = 0
    length_target = len(target)
    while j < length_target:
      if devide[i] == target[j]:
        j += 1
      elif target[j] % devide[i] == 0:
        del(target[j])
        length_target -= 1
      else:
        j += 1
    i += 1
  print(len(target))
    
if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
import collections

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

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 x:
        if c["i"] > 1:
            continue
        if is_prime[i] == True:
            cnt += 1
    print(cnt)

Eratosthenes(a)

Submission status: Wrong Answer

Solution code:
import copy 

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
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 collections

n=int(input())
a=sorted([int(i) for i in input().split()])
b=[0 for i in range(max(a)+1)]
d = collections.Counter(a)
ans=0
for i in a:
    if d[i]==1:
        if b[i]==0:
            c=i
            ans+=1
            while i<max(a)+1:
                b[i]=c
                i+=c
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort()
size=N
i=0
while i<size:
  j=i+1
  if not (i!=0 and A[i]!=A[i-1]):
    while size>j:
      if A[j]%A[i]==0:
        A.remove(A[j])
        size-=1      
      else:j+=1
  i+=1
print(size)

Submission status: Wrong Answer

Solution code:
N = int(input())
L = list(map(int, input().split()))
#N=10
#L=[33,18,45,28,8,19,89,86,2,4]
#N=5
#L=[3,8,11,16,24]

List=list(set(L))
#print(List)
List.sort()
#print(List)
#N=2
#List=[3,3,11,16,24]
#List=[5,5,5,5]
#List=[2,5]
a=0
#ns=List[N-1]/2
#print(ns)
for i in range(len(List)):
    #if i>ns:
     #   break
    
    for u in range(i):
 #       print(i,u,List[i],List[u])
        if List[i]%List[u]==0:
            a+=1
            #print('#',i,u)
            break
#print(a)
if len(List)==1:
    print(0)
else:
    print(N-a)

Submission status: Wrong Answer

Solution code:
def main():
    n=int(input())
    a=list(map(int,input().split()))
    a.sort()
    max=a[-1]
    check=[0 for i in range(max+10)]
    sum=0
    if len(a)==1:
        print(1)
        exit()
    tmp=a[1]
    for i in range(n):
        if tmp==a[i]:
            continue
        tmp=a[i]
        if check[a[i]]==0:
            sum+=1
            j=1
            x=a[i]*j
            while x<max+1:
                check[x]=1
                j+=1
                x=a[i]*j
        else:
            continue
    print(sum)
        
    
    
if __name__=="__main__":
    main()

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 and (x % i or i not in s and x // i not in s):
      i += 1
    if i * i > x:
      r += 1
print(r)

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

    count=1
    num=a
    while num<=MAX:
        nums[num-1]+=1
        count+=1
        num=a*count
    

print(ans)

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]==1 :
        for j in range(2, max(A)//i+1):
            dp[j*i] -=100

print(dp.count(1))

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[i-1]:
            NG += 1
            break
        else:
            if A[i] % A[j] == 0:
                NG += 1
                break

res = N - NG
print(res)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
ans = 0
prime = []
limit = max(A)
if A[0] == 1:
    print(1)
else:
    while True:
        if len(A) == 0:
            break
        p = A[0]
        if len(A) >1:
            if A[0] != A[1]:
                prime.append(p)
        else:
            prime.append(p)
        A = [e for e in A if e % p != 0]

    print(len(prime))

Submission status: Wrong Answer

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

for x in a:
    if dp[x - 1] == False: continue
    else:
        multiply = x + x
        while multiply <= a[-1]:
            dp[multiply - 1] = False
            multiply += x
ans = 0
for x in a:
    if dp[x - 1] is True:
        ans += 1
        dp[x - 1] = False
        #print(x)
print(ans)

Submission status: Wrong Answer

Solution code:
def D():
    n = int(input())
    a = list(map(int, input().split()))
    a = [x for x in set(a) if a.count(x) < 2]
    if len(a) == 0:
        print(0)
        return
    import copy
    res = copy.copy(a)
    for d in a:
        if d not in res:
            continue
        mult = list(range(d*2,max(res)+1,d))
        res = list(set(res)-set(mult))
    print(len(res))
D()

Submission status: Wrong Answer

Solution code:
N=int(input())
list=list(map(int,input().split()))
flag=0
for i in list:
  a=0
  for j in list:
    if i%j==0:
      a+=1
      if a>=2:
        flag+=1
        break
print(flag)

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 = sorted(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]
  for j in range(old_idx+1, p):
    prime_bool[j] = False
    old_idx = p
  if prime_bool[p]:
    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:
n = int(input())
l = list(map(int,input().split()))

l.sort()
j = [0]*(10**6+1)

for i in l:
    j[i] += 1
    if j[i] == 1:
        for k in range(2*i,10**6,i):
            j[k] += 100

print(j.count(1))

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

print(N - s)

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 a[i] % a[N-1-j] == 0:
      d = 1
      break
  if d == 0:
    c =c+1
print(c)

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]==1 :
        for j in range(2, max(A)//i+1):
            dp[j*i] =-1

print(dp.count(1))

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:
n=int(input())
a=list(map(int,input().split()))
tmp = {}
for a2 in a:
  tmp[a2]=tmp.get(a2,0)+1
a = [i for i in tmp if tmp[i]==1]
if len(a) == 0:
  print(0)
  exit()
a.sort()
b = [True]*(a[-1]+1)
for a2 in a:
  if b[a2] == False: continue
  c = 2
  while c*a2<=a[-1]:
    b[c*a2]=False
    c+=1
#print(b)
t = [a2 for a2 in a if b[a2]==True]
print(len(t))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
p = [True for i in range(a[-1])]
ans = 0
for k in range(0,n):
    if p[a[k]-1]:
        if a[k-1] != a[k]:
            for i in range(1,a[-1]+1):
                if a[k]*i <= a[-1]:
                    p[a[k]*i-1] = False
                else:
                    break
        else:
            ans -= 1
            for i in range(1,a[-1]+1):
                if a[k]*i <= a[-1]:
                    p[a[k]*i-1] = False
                else:
                    break          
    else:
        ans -= 1        

    

print(n+ans)