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
from collections import Counter
N = int(input())
A=list(map(int,input().split()))

#O(nlogn)
A.sort()

cnt= 1 if Counter(A)[min(A)]==1 else 0

for i,a in  enumerate(A):
  if i==0:continue
  max_soinsu=math.floor(a**(0.5))
  cntFlag=1
  for divider in A[:i]:
    if a % divider == 0:
      cntFlag=0
      break
    if divider >= max_soinsu:
      break
  cnt+=cntFlag

print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def read_a_int(): return int(read())


def read_ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right

# 一番小さい数はかならず条件を満たす(同じ数があるときはだめ)
# i!=j の任意のjで割り切れない → N-i!=jで一つでも割り切れるものがある数

'''
エラトステネスの篩の数列版じゃない？
1  2  3  4  5  6  7  8  9  10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30

小さい方から倍数を取ってけば良いかな
'''


N = read_a_int()
A = read_ints()
cnt = Counter(A)
A = []
# print(cnt)
for k, v in cnt.items():
    if v == 1:
        A.append(k)

A.sort()
# print(A)
AMAX = 10**6 + 10
cnt = 0  # なにでも割り切れないときのcnt
is_first = [True] * (AMAX + 1)
for a in A:
    if is_first[a]:
        cnt += 1
        for j in range(a, AMAX + 1, a):
            is_first[j] = False
print(cnt)

Submission status: Wrong Answer

Solution code:
MAXA = 10**6+1
N = int(input())
A = list(map(int,input().split()))
A.append(MAXA)
A.sort()
hurui = [0]*(MAXA+1)
ans = 0
for j in range(N):
    a = A[j]
    if hurui[a] == 0 and A[j+1] != a:
        ans += 1
    for i in range(a,MAXA+1,a):
        if hurui[i] != 0:
            break
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import collections

def main():

    input = sys.stdin.readline

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

    ans = 0
    sort_A = sorted(A)

    c = collections.Counter(sort_A)

    keisan_set = set()

    for a in set(sort_A):
        for k in keisan_set:
            if (a % k == 0):
                break
        else:
            if c[a] == 1:
                ans += 1

            keisan_set.add(a)

    print(ans)





if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    answer = n
    chk = [0 for _ in range(a[-1] + 1)]
    for aa in a:
        chk[aa] += 1
    for i in range(a[-1] + 1):
        if chk[i] == 1:
            for j in range(2 * i, a[-1] + 1, i):
                answer -= chk[j]
                chk[j] = 0
        else:
            answer -= chk[i]
            chk[i] = 0
    if n == 1:
        answer = 0
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

import math

n=ni()
a=sorted(nl())

# def is_prime(n):



ans=0

for i in range(n):
  for j in range(n):
    if i==j:
      continue
    if a[i]%a[j]==0:
      break
    if a[i]<a[j]:
      ans+=1
      break
  if j==n-1:
    ans+=1

print(ans)

Submission status: Wrong Answer

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

a.sort()
a_wk = set()
a_wk.add(a[0])

ans = 0
if n == 1 or a[0] < a[1]:
  ans = 1

for i in range(1, n):
  if a[i] == a[i - 1]:
    continue
  flag = True
  for _a in a_wk:
    if a[i] % _a == 0:
      flag = False
      break
  if flag:
    ans += 1
    a_wk.add(a[i])

print(ans)

Submission status: Wrong Answer

Solution code:
import collections
n=int(input())
data=list(map(int,input().split()))
data=list(collections.Counter(data).keys())
count=0
def is_mul(i,data):
    if len(data)==1:
        return True
    for j in data:
        if i!=j and i%j==0:
            return True
    return False
for i in data:
    if is_mul(i,data)==False:
        count+=1
print(count)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
if len(set(a))==1:
  print(0)
  exit()
l=[0 for i in range(10**6+1)]
for i in range(n):
  l[a[i]]+=1
ans2=[-1 for i in range(10**6+1)]
ans=0
for i in range(n):
  x=a[i]
  if ans2[x]==-1:
    if l[a[i]]==1:
      flag=1
      for j in range(1,int(x**0.5)+2):
        if x%j==0:
          if x!=j and l[j]>0:
            flag=0
            break
          if x!=x//j and x%(x//j)==0 and l[x//j]>0:
            flag=0
            break
      if flag==1:
        ans+=1
        ans2[x]=1
      else:
        ans2[x]=0
  else:
    ans+=ans2[x]
print(ans)

Submission status: Wrong Answer

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

a.sort()
c = Counter(a)
#print(c)
already = []
count = 0
for i in a:
    if c[i] != 1:
        continue
    if len(already) == 0:
        count += 1
        already.append(i)
    else:
        for j in already:
            if i % j == 0:
                break
        else:
            count += 1
            already.append(i)

print(count)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import deque
from collections import defaultdict

def main():
    n = int(sys.stdin.readline())
    A = list(map(int,sys.stdin.readline().split()))
    ans = 0
    A_dup = [x for x in set(A) if A.count(x) > 1]
    A = list(set(A) - set(A_dup))
    A.sort()
    while(A != []):
        ans += 1
        x = A.pop(0)
        A_x = [i for i in A if i % x == 0]
        A = list(set(A) - set(A_x))
        #print(A)
    print(ans)
    return 0

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

import sys
sys.setrecursionlimit(300000)


def solve(N: int, A: "List[int]"):
    def is_p(v):
        i = 2
        while i * i <= v:
            if v % i == 0:
                return False
            i += 1
        return True
    primes = []
    for i in range(2, 1001):
        if is_p(i):
            primes.append(i)
    #print(primes)

    A.sort()
    ret = 0
    tmp = set()
    for idx, v in enumerate(A):
        ok = (idx > 0 and v == A[idx - 1]) or (idx < N - 1 and v == A[idx + 1])
        for p in primes:
            if p * p > v:
                break
            if v % p == 0 and (p in tmp or v // p in tmp):
                ok = True
        if ok:
            pass
        else:
            #print(v)
            tmp.add(v)
            ret += 1
    print(ret)
    #tmp = []
    #for idx, v in enumerate(A):
    #    l = len(tmp)
    #    i = 0
    #    ok = (idx > 0 and v == A[idx - 1]) or (idx < N - 1 and v == A[idx + 1])
    #    while not ok and i < l and tmp[i] * tmp[i] <= v:
    #        if v % tmp[i] == 0:
    #            ok = True
    #            break
    #        i += 1
    #    if ok:
    #        pass
    #    else:
    #        print(v)
    #        ret += 1
    #        tmp.append(v)
    #print(ret)
    #return

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 = sorted(map(int,input().split()))

ans = 0

for i in range(n):
    judge = 0
    a0 = a[i]
    for j in range(i):
        if a0%a[j] == 0:
            judge = 1
            break
    if i < n-2 and a[i] == a[i+1]:
        judge = 1
    if judge == 0:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
def prime(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    a = list(set(a))
    return a

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

X = [0]*(10**6+10)
for i in A:
    X[i] += 1
ans = 0
for i in A:
    found = False
    for j in prime(i):
        if found:
            break
        for k in range(j, 10**6+1, j):
            if X[k] == 0 or k > i or k == i and X[k] == 1:
                continue
            if i % k == 0:
                found = True
                break
    if not found:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
if N==1:
  print(1)
else:
  A.sort()
  import numpy as np

  l = np.array([0] * (10**6 + 10))
  for i in range(1,N):
    if A[i-1]!=A[i]:
      l[A[i]] += 1

  if A[0]!=A[1]:
    l[A[0]] += 1

  ans = 0
  length = len(l)
  for i in range(length):
    if l[i]>=1:
      ans += 1
      l[i::i] = 0

  print(ans)

Submission status: Wrong Answer

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

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

"""
10
33 18 45 28 8 19 89 86 2 4
5
"""

Submission status: Wrong Answer

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

iter = 0

for j in a:
  c = a.count(j)
  lst = [i%j for i in a]
  iter = iter + lst.count(0) - c
print(iter)

Submission status: Wrong Answer

Solution code:
N = int(input())
*A, = map(int, input().split())
A.sort()
ans = 0
for i in reversed(range(N)):
    b = True
    for j in reversed(range(i)):
        if A[i] % A[j] == 0:
            b = False
    if b:
        ans += 1
if ans == 1:
    print(ans-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a_list = list(map(int, input().split()))
a_list.sort()
binary_list = [1 for i in range(n)]
#print(a_list)

for i in range(n):
    if binary_list[i]==1:
        for k in range(i+1, n):
            if a_list[k]%a_list[i]==0:
                binary_list[k] = 0

if a_list[0] in a_list[1:]:
    binary_list[0] = 0

print(sum(binary_list))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys

N,*A = map(int, sys.stdin.buffer.read().split())

A = sorted(A)

count = N
yakusu = []
for i in range(N):
  a = A[i]
  if i>0 and a==A[i-1]:
    count -= 1
    continue
  if i<N-1 and a==A[i+1]:
    count -= 1
    continue
  flg = 0
  for b in yakusu:
    if a%b == 0:
      flg = 1
      count -= 1
      break
    if b*2>a:
      break
  if flg==0:
    yakusu.append(a)

print(count)

Submission status: Wrong Answer

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

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

ans = 0
num = []

for i in range(N):
  num = make_divisors(A[i])
  num.remove(A[i])
  if len(set(A) & set(num)) >= 1:
    ans += 1

print(N - ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = sorted(map(int, input().split()))[::-1]
cnt = 0
for i in range(n):
    if all(a[i]%j!=0 for j in a[i+1:]):
        cnt += 1
if n!=1 and a[-1]==a[-2]:
    cnt -= 1
print(cnt)

Submission status: Wrong Answer

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

check = True
for i in range(0,N):
    if A[0] != A[i]:
        check = False

for j in range(0,N):
    for i in range(0,N):
        if A[j] != 0:
            if A[i] % A[j] == 0 and i != j:
                A[i] = 0
count = 0
for i in range(0,N):
    if A[i] != 0:
        count = count + 1

if check == True:
    count = 0
print(count)

Submission status: Wrong Answer

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

B = [x for x in set(A) if A.count(x) > 1]

A = [i for i in A if i not in B]

A = sorted(A)
cnt = 0
devide_list = []

for a in A:
  flag = 1
  for d in devide_list:
    if a % d == 0:
      flag = 0
      break
  if flag == 1:
    cnt += 1
  else:
    pass
  devide_list.append(a)
  
print(cnt)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
cnt=0
e=[]
a.sort()
prime=[2,3]
ans=[]
from collections import Counter
d=Counter(a)
for i in a:
    if d[i]>1:
        continue
    for j in e:
        if i%j==0:
            break
    else:
        cnt+=1
    e.append(i)
print(cnt)

Submission status: Wrong Answer

Solution code:
def main1():
    N=int(input())
    A=list(map(int,input().split()))
    A.sort()
    t=[]
    while A:
        cp=[]
        tmp=A[0]
        t.append([tmp])
        A.pop(0)
        for a in A:
            if a%tmp==0:
                t[-1].append(a)
            else:
                cp.append(a)
        A=cp
    if len(t)==1:
        print(0)
    else:
        print(len(t))

main1()

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
#from fractions import gcd
from decimal import *
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

n = INT()
a = LIST()
b = set(a)

NN = 10 ** 6 + 100
primes = set([])
isprime = [False for _ in range(NN + 1)]
cnt = [0 for _ in range(NN + 1)]
for i in a:
    if cnt[i] == 0:
        isprime[i] = True
        cnt[i] += 1
    else:
        isprime[i] = False
#エラトステネスの篩
for i in range(1, NN + 1):
    if not isprime[i]:
        continue
    primes.add(i)
    for j in range(i * 2, NN + 1, i):
        isprime[j] = False
ans = 0
for i in a:
    if isprime[i]:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:

def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    A = list(map(int, input().split()))

    d = dict()
    for x in A:
        if x in d:
            d[x] += 1
        else:
            d[x] = 1
    A = [x for x in d if d[x] == 1]

    A.sort(reverse=True)
    ans = 0

    while(A):
        ans += 1
        x = A.pop()
        next = []
        for y in A:
            if y % x != 0:
                next.append(y)
        A = list(next)

    print(ans)


main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# D

import sys
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

n = int(input())
a = list(map(int, input().split()))
a.sort()
max_a = a[-1]
counter_a = Counter(a)

if len(set(a)) == 1:
    print(0)
    sys.exit()

lis_prime = [False] * (max_a+1)
for a_ in a:
    lis_prime[a_] = True

primes = []
for i in range(len(lis_prime)):
    if lis_prime[i]:
        if counter_a[i]==1:
            primes.append(i)

        j = 2 * i
        while True:
            if j > max_a:
                break
            lis_prime[j] = False
            j += i

print(len(primes))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import collections
import itertools as it
import math
#import numpy as np
 
#  = input()
n  = int(input())
#  = map(int, input().split())
l  = list(map(int, input().split()))
#  = [int(input()) for i in range(N)]
#
c = collections.Counter(l)

l = sorted(c.keys())
sosu = []

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

for i1 in range(len(l)):
    #print(sosu)
    for s in sosu:
        if l[i1] % s == 0:
            break
    else:
        sosu.append(l[i1])

print(len(sosu))

Submission status: Wrong Answer

Solution code:
import sys
import math as mt
input=sys.stdin.buffer.readline  
#t=int(input())
mod=10**9+7
t=1
for __ in range(t):
    
    #x,n=map(int,input().split())
    l=[0]*(10**6+1)
    n=int(input())
    #a=[[0 for j in range(m)] for i in range(n)]
    a=list(map(int,input().split()))
    a.sort()
    ans=0
    for i in range(n):
        cnt=0
        for j in range(i):
            if a[i]%a[j]!=0:
                cnt+=1
        if cnt==i:
            ans+=1
    print(ans)

Submission status: Wrong Answer

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

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

print(ans)

Submission status: Wrong Answer

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

count = 0
for i in range(N):
  for j in range(i+1, N):
    if x_list[i]%x_list[j] == 0:
      break
    if j == N-1:
      count += 1
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)

res = []
for k, v in c.items():
    bl = True
    if v > 1:
        continue
    for w in res:
        if k % w == 0:
            bl = False
            break
    if bl:
        res.append(k)

print(len(res))

Submission status: Wrong Answer

Solution code:
import collections

n = int(input())
d = list(map(int, input().strip().split()))

# 重複しているやつは削除
counts = collections.Counter(d)
d = []
for a, c in counts.items():
    if c == 0:
        d.append(a)

d = sorted(d)
count = 0

while True:
    if len(d) == 0:
        break

    divisor = d[0]
    d = d[1:]
    count += 1
    d1 = []
    for a in d:
        if a % divisor != 0:
            d1.append(a)

    d = d1

print(count)

Submission status: Wrong Answer

Solution code:
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

N = INT()
A = LIST()

A.sort()
flag = [True] * N

ans = 0
for i in range(N):
    if not(flag[i]):
        continue
    if i != N-1 and A[i] != A[i+1]:
        ans += 1
    for j in range(i+1, N):
        if flag[j] and A[j] % A[i] == 0:
            flag[j] = False
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
INF = 1000000000000

n = I()
a = LI()

a.sort()
f = [False]*n

if(n > 1):
    if(a[0] == a[1]):
        f[0] = True
    for i in range(1,n):
        for j in range(0,i):
            if(a[i] % a[j] == 0):
                f[i] = True
                break

count = 0
for i in range(n):
    if(not f[i]):
        count += 1

print(count)

Submission status: Wrong Answer

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

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

"""
10
33 18 45 28 8 19 89 86 2 4
5
"""

Submission status: Wrong Answer

Solution code:
import numpy as np

if __name__ == '__main__':
    n = int(input().strip())
    a = list(map(int, input().strip().split()))
    ans = 0
    aa = np.argsort(a)

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

    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
"""
すべてのjで割れない場合、カウントする。
逆に言えば、一つでもiをjで割れるようなjが存在するならば、それはカウントしない。
一番小さい数が2つあればそれはカウントしないが、基本的に一番小さい数はほかのどの数字でも割れない
Aiの制約が10**6であることから、小さい数から数えていって、10**6までの倍数の場所にマークを付ける。
初めて出てくるような数字に関して、カウントを1足してやる。
一番小さい数のコーナーケースに注意
"""
n = int(readline())
lst1 = list(map(int,readline().split()))

lst1.sort()

memo = [0]*(10**6+1)
if n == 1:
    print(0)
    exit()
if lst1[0] == lst1[1]:
    ans = -1
else:
    ans = 0
for i in lst1:
    if memo[i] == 0:
        ans += 1
        j = 1
        while i*j <= 10**6:
            memo[i*j] = 1
            j += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n = int(input())
orga = list(map(int, input().split()))

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

import collections
c = collections.Counter(orga)

a=[]
for itm in c.items():
    num,cnt=itm
    if cnt==1:
        a.append(num)

aset=set(a)

def m_div(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

ans=0
for num in a:
    found=False
    for div in m_div(num):
        if div==num:
            continue
        if div in aset:
            found=True
            break
    if not found:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import bisect
N = int(input())
A = list(map(int,input().split()))
cnt = Counter(A)
A.sort()
ans = 0
for j in range(len(A)):
    a = A[j]
    if cnt[a] > 1:
        continue
    i = bisect.bisect_left(A, pow(a,0.5))
    if i==j:
        i-=1
    ok = True

    while(i>=0):
        if a % A[i]==0:
            #print (a,A[i])
            ok = False
            break
        i-=1
    if ok:
        #print(a)
        ans+=1
print (ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
m=max(a)
x=[1 for i in range(m+1)]
for i in range(n):
    p=a[i]
    if 2*p<=m:
        for k in range(2,m//p+1):
            x[p*k]=-1

ans=0
for p in a:
    if x[p]==1: ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
N=int(input())
aset=set(map(int,input().split()))

num_True=0
tlist=[False]*(max(aset)+1)
for a in aset:
  tlist[a]=True
  num_True+=1
#print(tlist)

if num_True==1:
  print(0)
elif tlist[1]:
  print(1)
else:
  for i in range(2,len(tlist)//2+1):
    if not tlist[i]:
      continue
    else:
      for j in range(2*i,len(tlist),i):
        tlist[j]=False
        
  #print(tlist)
  answer=0
  for t in tlist:
    if t:
      answer+=1
    
  print(answer)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
r = [0 for _ in range(max(a)+1)]
l = [1 for _ in range(max(a)+1)]
ans = 0
for i in a:
    r[i] += 1
for i in range(len(r)):
    if r[i]:
        for j in range(2*i,len(r),i):
            if 1 < r[j]:
                break
            elif (r[j] == 1 and l[j]):
                ans += 1
                l[j] = 0
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

def divisor(n): #nの約数を全て求める
  i = 1
  table = []
  while i * i <= n:
    if n%i == 0:
      if i != 1:
        table.append(i)
      if n//i != 1:
        table.append(n//i)
    i += 1
  table = list(set(table))
  return table

A = list(map(int, input().split()))
A.sort()
B = []
for a in A:
  B += [divisor(a)]

s = set()
ans = 0
for i in range(N):
  if i == 0:
    s |= set(B[i])
  else:
    if len(set(B[i]) & s) == 0:
      ans += 1
    s.add(A[i])

c = set()
for i in range(1, N):
  c.add(A[i])

if len(c & set(B[0])) == 0:
  ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
#import numpy as np
#from decimal import *

N = INT()
A = LIST()
A.sort()

A_max = max(A)

a = [0]*(A_max+1)

ans = 0
for x in A:
	a[x] += 1

for i in range(A_max+1):
	if a[i] == 1:
		ans += 1
		for j in range(A_max//i + 1):
			a[i*j] = 0

print(ans)

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

    ax = set()
    ans = 0
    for i in range(1, N):
        a0 = A[i-1]
        if A[i-1] == A[i]:
            ax.add(a0)
            continue

        for x in ax:
            if a0 % x == 0:
                break
        else:
            ax.add(a0)
            ans += 1
    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
n=int(input())
a=sorted(list(map(int,input().split())))
l=[]
l.append(a[0])
ans=n
if(len(a)!=len(set(a))):ans-=1
for i in range(1,n):
    x=a[i]
    for j in l:
        if(x%j==0):
            ans-=1
            break
    l.append(x)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

MAX = 10 ** 6
is_divisible = [True] * (MAX + 1)
is_divisible[0] = False
is_divisible[1] = False
for i in A:
    if not is_divisible[i]:
        continue
    for j in range(i * 2, MAX + 1, i):
        is_divisible[j] = False


for k, v in Counter(A).items():
    if v > 1:
        is_divisible[k] = False

st = {i for i in range(MAX + 1) if is_divisible[i]}
print(len(st & set(A)))

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)
d={}
for a in A:
    if a in d:
        d[a]+=1
    else:
        d[a]=1

ans=0
for i in range(N):
    a=A[i]
    p=1
    if d[a]>1:
        continue
    for j in range(2,int(a**0.5)+1):
        if a%j==0:
            if j in d or a//j in d:
                p=0
                break
    ans+=p

if A[-1]==1:
    if A[-1]>1:
        ans=1
    else:
        ans=0
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
div = set()
for i in range(n):
    for j in range(1,int(pow(a[i], 0.5)) + 1):
        if a[i] % j == 0:
            if j in div or a[i] // j in div:
                break
    div.add(a[i])
    if i != n-1 and a[i] != a[i+1]:
        ans += 1
    if i == n-1:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
alst = list(map(int, input().split()))
alst.sort()
ans = 0
for i, num in enumerate(alst[::-1], start = 1):
    for num2 in alst[:-i]:
        if num % num2 == 0:
            break
        if num <= num2 * 2:
            try:
                if alst[n - i + 1] != num:
                    ans += 1
            except IndexError:
                ans += 1
            break
    else:
        try:
            if alst[n - i + 1] != num:
                ans += 1
        except IndexError:
            ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
ns = list(map(int, input().split()))
ans = 0
from collections import Counter
c = Counter(ns)
dubbles = set([key for key, value in c.items() if value >= 2])
ignore = set()
ns = sorted(ns)
for i in range(n):
    if ns[i] in dubbles | ignore:
        continue
    ans += 1
    for j in range(i + 1, n):
        if ns[j] % ns[i] == 0:
            ignore.add(ns[j])
print(ans)

Submission status: Wrong Answer

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

def main():
    N = int(input())
    A = sorted(map(int, input().split()))
    MAX_A = max(A)
    A_COUNT = Counter(A)

    ans = 0
    prime = [False] * 2 + [True] * (MAX_A - 1)
    for a in A:
        if prime[a]:
            if A_COUNT[a] == 1:
                ans += 1
            for j in range(a, MAX_A + 1, a):
                prime[j] = False
    print(ans)

if __name__ == '__main__':
    main()

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,m,k=map(int, readline().rstrip().split())
    n=int(readline())
    arr=list(map(int, readline().rstrip().split()))
    
    if n==1:
        print(0)
        return

    arr.sort(reverse=True)
    ans=0
    for i in range(n):
        flg=0
        for j in range(i+1,n):
            if arr[i]%arr[j]==0:
                flg=1
                break
        if i==(n-1) and arr[i]==arr[i-1]:
            flg=1
        if flg==0:
            ans+=1
    print(ans)
    return

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

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