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:
from collections import Counter

N = int(input())
A = list(map(int,input().split()))
counter = Counter(A)
s = sorted(set(A))
A.sort()
if len(A) == 1:
    print(1)
else:
    lst = []
    ans = 0
    for a in s:
        lst.append(a)
        if counter[a] == 1:
            ans = 1
            break

    for i in range(1,len(s)):
        m = s[i]**0.5 + 1
        flg = True
        for p in lst:
            if A[i]%p == 0:
                flg = False
                break
            else:
                if m < p:
                    break
        if flg:
            lst.append(A[i])
            if counter[s[i]] == 1:
                ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

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

AListsort = sorted(AList)

ResultList = []

tmp = 0
for p in range(0, N - 1):
    tmp = 0
    if AListsort[p] == AListsort[p + 1]:
        continue
    else:
        for q in ResultList:
            if AListsort[p] % q == 0:
                tmp = 1
                break
        if tmp == 0:
            ResultList.append(AListsort[p])

tmp = 0
if AListsort[N - 2] != AListsort[N - 1]:
    for q in ResultList:
        if AListsort[N - 1] % q == 0:
            tmp = 1
            break
    if tmp == 0:
        ResultList.append(AListsort[N - 1])

print(len(ResultList))

Submission status: Wrong Answer

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

    A.sort()

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

    print(ans)


if __name__ == "__main__":
    main()

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
ans=0
for i in range(n):
  x=a[i]
  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
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

N=int(input())
lis=list(map(int, input().split()))
lis.sort(reverse=True)
arr=np.array(lis)
ans=0

for i in range(N):
    #print(arr[i] % arr[i+1:])
    if np.count_nonzero(arr[i] % arr[i+1:] == 0) == 0:
        ans+=1

if N>2 and lis[-1]==lis[-2]:
    ans -=1
    
print(ans)

Submission status: Wrong Answer

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

A.sort()

ls = []

for i in range(N):
    a = A[i]

    if (i + 1 < N and a == A[i + 1]) or (i - 1 >= 0 and a == A[i - 1]):
        continue
    else:
        flag = False

        for b in ls:
            if b * 2 > a:
                break

            if a % b == 0:
                flag = True
                break
            

        if not flag:
            ls.append(a)

print(len(ls))

Submission status: Wrong Answer

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

ans = 0
for i in range(n):
    while len(A) > 1:
        ans += 1
        A = [i for i in A if i%A[0]!=0]
if not A:print(0)
else: print(ans+1)

Submission status: Wrong Answer

Solution code:
if __name__ == '__main__':
    n = int(input())
    a = [int(i) for i in input().split()]
    a.sort()
    b = list(set(a))
    count = 0

    for i in range(len(b)):
        if i == 0 and a[0] not in a[1:]:
            count += 1

        for j in range(i):
            if b[i] % b[j] == 0:
                break
            if j == i - 1:
                count += 1
    print(count)

Submission status: Wrong Answer

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

A.sort()
divisors=[]
ans=0
for i in range(N):
    if i!=N-1:
        if A[i]==A[i-1]:
            divisors.append(A[i])
            continue
    
    cnt=0
    for j in divisors:
        if A[i]%j==0:
            break
        cnt+=1
    if cnt==len(divisors):
        ans+=1
    divisors.append(A[i])
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=set(map(int,input().split()))
A=list(A)
N=len(A)
ans=0
for i in range(N):
  for j in range(N):
    if i==j:
      continue
    if A[i]%A[j]==0:
      break
    else:
      continue
  else:
    ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int, input().split()))
ans = []
A.sort()
if A[0] == A[-1]:
  print(0)
else:
  for a in A:
    for b in ans:
      if a%b == 0:
        break
    else:
      ans.append(a)
      continue

  print(len(ans))

Submission status: Wrong Answer

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

AS.sort()

ok = []
for i in range(N):
    for j in range(N):
        if AS[i] == AS[j]:
            break
        if i <= j:
            break
        if AS[i] % AS[j] == 0:
            break
    else:
        ok.append(i)

print(len(ok))

Submission status: Wrong Answer

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

A.sort()
if A[0]==1:
    print(0)
    exit()

def make_divisors(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

dic={}
ans=0
for i in range(N):
    if A[i] in dic:
        if dic[A[i]]==1:
            ans-=1
            dic[A[i]]+=1
        continue
    f=False
    div=make_divisors(A[i])
    for d in div:
        if d in dic:
            f=True
    dic[A[i]]=1
    if f:
        continue
    ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
import collections

if __name__ == "__main__":
    N = int(input())
    A = [int(x) for x in input().split(" ")]
    counter = collections.Counter(A)
    A = []
    for key, val in counter.items():
        if val == 1:
            A.append(key)
    A.sort()
    count = 0
    for i, a in enumerate(A):
        flag = True
        for j in range(i):
            if a % A[j] == 0:
                flag = False
        if flag:
            count += 1
    print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = [int(x) for x in input().split()]
A.sort()
ans = 0
for i, a in enumerate(A):
    if i != n - 1 and A[i + 1] == a:
        continue
    do_count = True
    for j in range(i):
        b = A[j]
        if a % b == 0:
            do_count = False
            break
        if b * 2 > a:
            break
    if do_count:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

count = 0
for i in range(N):
  for j in range(N):
    if i == j:
      continue
    if x_list[i]%x_list[j] == 0:
      break
    if j == N-1:
      count += 1
print(count)

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

#素因数分解
def prime_factorize(n):
    a = set([])
    while n % 2 == 0:
        a.add(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.add(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.add(n)
    return a

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(2, 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:
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int,input().split()))
for i in range(1,n):
    if a[i] != a[0]:
        break
else:
    print(0)
    exit()
a.sort()
ans = 0
for i in range(n):
    for j in range(i):
        if a[i]%a[j] == 0:
            break
    else:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

    A.sort()

    ans = 1
    modlist = [A[0]]
    for i in range(1, N):
        flag = True
        for j, m in enumerate(modlist):
            if A[i] % m == 0:
                flag = False
                break
        if flag:
            ans += 1
            print(A[i])

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

A.sort()

ls = []

for i in range(N):
    a = A[i]

    if (i + 1 < N and a == A[i + 1]) or (i - 1 >= 0 and a == A[i - 1]):
        continue
    else:
        flag = False

        for b in ls:
            if b * 2 > a:
                break
                
            if a % b == 0:
                flag = True
                break
            

        if flag:
            ls.append(a)

print(len(ls))

Submission status: Wrong Answer

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

print(ans-len(ng))

Submission status: Wrong Answer

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

exist = set([])

for i in range(n):
    temp = a[i]
    loop = False
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            if not i in exist:
                while temp%i==0:
                    temp //= i
                exist.add(i)
            else:
                loop=True
                break
    
    if loop:
        continue
    else:
        if temp!=1:
            exist.add(temp)

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

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+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:
from collections import defaultdict, Counter
def factors(N,E): #約数を全て求める。ただし、順不同
    from collections import deque
    ret = deque()
    middle = int( N**(1/2))
    for e in E:
        if e >= middle:
            break
        if N%e == 0:
            ret.append(e)
            ret.append(N//e)
            
    if N%middle == 0:
        ret.append(middle)
        if middle != N//middle:
            ret.append(N//middle)
    return ret

def eratosthenes(N):
    from collections import deque
    work = [True] * (N+1)
    work[0] = False
    work[1] = False
    ret = []
    for i in range(N+1):
        if work[i]:
            ret.append(i)
            for j in range(2* i, N+1, i):
                work[j] = False
    return ret


def main():
    N = int( input())
    A = list( map( int, input().split()))
    CA = Counter(A)
    d = defaultdict( lambda : False)
    for a in A:
        d[a] = True
    ans = 0
    E = eratosthenes(10**6)
    for a in A:
        if CA[a] > 1:
            continue
        for p in factors(a, E):
            if p == a:
                continue
            if d[p]:
                break
        else:
            ans += 1
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

count = 1

if A[0] in A[1:]:
    count -= 1

for i in range(1, N):
    flag = True
    for j in range(0, i):
        if A[i] % A[j] == 0:
            flag = False
            break
        if A[j] * 2 > A[i]:
            break
    if flag:
        count += 1


print(count)

Submission status: Wrong Answer

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

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf
# @pysnooper.snoop()
#import pysnooper # debug

import math
#from sortedcontainers import SortedList, SortedDict, SortedSet # no in atcoder
import bisect


def save_get(l, index):
    try:
        return l[index]
    except IndexError:
        return None

def has_same(l, index, value):
    bef = save_get(l, index - 1)
    aft = save_get(l, index + 1)
    if bef == value:
        return True
    if aft == value:
        return True
    return False

if __name__ == '__main__':
    n = int(input())
    data = list(map(int, input().split()))
    data.sort()
    #print('data') # debug
    #print(data) # debug
    max_ = data[-1]
    times = [False] * (max_ + 3)
    for d in data:
        if times[d]:
            continue
        v = d * 2
        while v < len(times):
            times[v] = True
            v += d
    #print('times') # debug
    #print(times) # debug
    ans = 0
    for i, d in enumerate(data):
        if has_same(data, i, d):
            continue
        if times[d] == False:
            ans += 1
    print(ans)

    #print('\33[32m' + 'end' + '\033[0m') # debug

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

S = set(A)
C = Counter(A)
ans = 0
for Ai in A:
    if C[Ai] > 1:
        continue
    i = 1
    j = True
    while i * i <= Ai:
        if Ai % i != 0:
            i += 1
            continue
        if i in S or i != 1 and Ai // i in S:
            j = False
            break
        i += 1
    if j:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
P=list(map(int, input().split()))
P.sort()
if P[0]==P[N-1]:
    print(0)
else:
    sum1=1
    i=1
    for i in range(1,N):
        j=0
        for j in range(0,i):
            if P[i]%P[j]==0:
                j+=1
                break
            j+=1
        if P[i]%P[j-1]>0:
            sum1+=1
        i+=1
    print(sum1)

Submission status: Wrong Answer

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

d = {}
for a in A:
    d.setdefault(a, 0)
    d[a] += 1

b = sorted(d)
result = 0
for i in range(len(b)):
    if d[b[i]] > 1:
        continue
    for j in range(i):
        if A[i] % A[j] == 0:
            break
    else:
        result += 1
print(result)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
# n =5
# a=[24, 11, 8, 3, 16]

a.sort()


def prime_factorization(n):
    pmax = int(n ** 0.5 // 1) + 1

    factors = {}
    for p in range(2, pmax + 1):
        while n % p == 0:
            factors[p] = factors.get(p, 0) + 1
            n //= p
    if n != 1:
        factors[n] = factors.get(n, 0) + 1

    return factors


divisors = set()
answer = 0
apast = None
for i, ai in enumerate(a):
    if ai == apast:
        is_good = False
    elif i < n - 1 and ai == a[i + 1]:
        is_good = False
    else:
        is_good = True
        factors = prime_factorization(ai)
        for p, m in factors.items():
            for i in range(m):
                if p ** (i + 1) in divisors:
                    is_good = False

    if is_good:
        # print(ai, factors, divisors)
        answer += 1

    divisors.add(ai)
    apast = ai


print(answer)

Submission status: Wrong Answer

Solution code:
import sys

def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
def TI(): return tuple(map(int,input().split()))
def RN(N): return [input().strip() for i in range(N)]


def main():
    N = II()
    A = LI()
    As = sorted(A, reverse=True)
    ans = N

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

    
    print()

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
from sys import setrecursionlimit
from collections import Counter, deque, defaultdict
from math import floor, ceil
from bisect import bisect_left
from itertools import combinations
setrecursionlimit(100000)

INF = int(1e10)
MOD = int(1e9 + 7)

def main():
    from builtins import int, map
    # _, primes = sieve(100001)
    N = int(input())
    A = list(map(int, input().split()))
    # dividable = {i:set ({}) for i in range(N)}
    # divcount = {i: 0 for i in range(N)}
    divcount = [0] * N
    A.sort()
    cA = Counter(A)

    ans = 0
    for i in range(N):
        if i == 0:
            if cA[A[i]] == 1:
                ans += 1
            for j in range(1, N):
                if A[j] % A[i] == 0:
                    divcount[j] += 1
        else:
            flag = True
            for j in range(i + 1, N):
                if A[j] % A[i] == 0:
                    flag = False
                    divcount[i] += 1
            if divcount[i] == 0:
                ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

A.sort()
ans=N
i=0
while i<N:
    if i<N-1 and A[i]==A[i+1]:
        ans-=1
        i+=1
        continue
    for a in A[:i]:
        if A[i]%a==0:
            ans-=1
            break
        if a>A[i]//2:
            break
    i+=1

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
  n, = list(map(int, input().split()))
  aa = sorted(map(int, input().split()))
  
  res = []
  while aa:
    x = aa[0]
    if len(aa) > 1 and x == aa[1]:
      aa = [a for a in aa[1:] if a != x]
      continue
    res.append(x)
    aa = [a for a in aa[1:] if a % x]
    
  print(len(res))
  
  
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

ans = 0
while len(que) > 0:
    n = que.popleft()
    que = deque([i for i in que if i % n != 0])
    ans += 1
    
print(ans)

Submission status: Wrong Answer

Solution code:
def is_prime(n):
    if n==1:
        return False
    for k in range(2,int(n**0.5)+1):
        if n%k==0:
            return False
    return True

N=int(input())
A=sorted(list(map(int,input().split())))
ans=0
for i in range(N):
    if i+1<N:
        if A[i]==A[i+1]:
            continue
    else:
        if A[i-1]==A[i]:
            continue
    if is_prime(A[i]):
        ans+=1
        continue
    for j in range(N):
        if i==j:
            continue
        if A[i]<A[j]:
            ans+=1
            break
        if A[i]%A[j]==0:
            break
    else:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
input = lambda: sys.stdin.readline().rstrip()

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

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

   upper_divisors.reverse()
   return lower_divisors + upper_divisors

cnt = 0
is_ok = defaultdict(lambda: True)
divs = defaultdict(lambda: None)

for v in a:
   if divs[v] == None:
      divs[v] = make_divisors(v)
   f = True
   for w in divs[v]:
      # check
      if not is_ok[w]:
         f = False
         break
   if f:
      cnt += 1
   is_ok[v] = False

if cnt == 1:
   cnt = 0
print(cnt)

Submission status: Wrong Answer

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

alist.sort()

count = 0

for i in range(0, N):
  
  a = alist[i]
  flag = 0
  
  if i != N - 1:
    if alist[i + 1] == a:
      continue
      
  if i != 0:
    if alist[i - 1] == a:
      continue

  for j in range(i):
    b = alist[j]
    if b * b <= a:
      if a % b == 0:
        flag = 1
        break
        
  if flag == 0:
    count += 1
      
print(count)

Submission status: Wrong Answer

Solution code:
from collections import deque
#from numba import njit
N = int(input())
A = sorted(list(set(list(map(int, input().split())))))

#D = deque(A)

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

else:
  ans = 0
  while True:
    d = A.pop(0)
  
    for a in A[::-1]:
      if a % d == 0:
        A.remove(a)
    ans += 1
    if A:
      True
    else:
      break
  
  print(ans)

Submission status: Wrong Answer

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

# print(li)
li.sort()
# print(li)

one = [1 for _ in range(n)]

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

Submission status: Wrong Answer

Solution code:
n = int(input())
dat = list(map(int, input().split()))
res = 0
import collections
buf = collections.Counter(dat)
dat = []
for k in buf:
    if buf[k] == 1:
        dat.append(k)
dat.sort()
#print(dat)
res = 0
used = [False] * (1000100)

for i in range(len(dat)):
    ok = True

    if used[dat[i]]:
        ok = False
    c = 0
    v = -1
    while True:
        c += 1
        v = dat[i] * c
        if v > 1000010:
            break
        used[v] = True


    used[dat[i]] = True
    if ok:
        res += 1
print(res)

Submission status: Wrong Answer

Solution code:
import copy
import sys
input = sys.stdin.readline

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

cnt = 0
new_a = copy.copy(a)
for i in a:
    new_a.remove(i)
    tmp = True
    if new_a == []:
        tmp = False
    for j in new_a:
        if i%j == 0:
            tmp = False
            break
    if tmp:
        new_a.append(i)
        cnt += 1

print(cnt)

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(N):
        if i==j:
            continue
        if A[i]%A[j]==0:
            ans+=1

print(ans)

Submission status: Wrong Answer

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

cnt=0

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

        if a[i]%a[j]==0:
            break
        else:
            continue
        
print(cnt)

Submission status: Wrong Answer

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

A = sorted(A)
di = {}
count = 0

for i, a in enumerate(A):
    judge = True
    if a > 3:
        for j in di.keys():
            if a % j == 0:
                judge = False
                if a == j:
                    count -= di[j]
                    di[a] = 0

        if judge:
            count += 1
            di[a] = 1
    else:
        di[a] = 1
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
from collections import Counter


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]


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

c = Counter(a)
new = []
for key, val in c.most_common():
    if val == 1:
        new.append(key)

ans = 0
for i in a:
    div = make_divisors(i)
    if len(set(new) & set(div)) == 1:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
# 素数判定 O(√N)
def is_prime(n):
    if n <= 1:
        return False
    if n == 2:
        return True
    i = 2
    while i*i <= n:
        if n % i == 0:
            return False
        i += 1
    return True

# エラトステネスの篩 およそO(NloglogN)
# Nまでの自然数iが素数であるかをtable[i]に保持
# is_primeに依存
def Eratosthenes_sieve(n):
    table = [True]*(n+1)
    for i in range(n+1):
        if is_prime(i):
            for j in range(2*i,n+1,i): # 素数の倍数は非素数
                table[j] = False
        else:
            table[i] = False
    return table

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

ma = A[-1]
first = [0]*(ma+1)
seen = [False]*(ma+1)

for i in range(N):
    a = A[i]
    if first[a] == 0:
        first[a] += 1
    elif first[a] == 1:
        ans -= 1
        first[a] += 1
    else:
        pass
    #if pt[a] == 0:
    if not seen[a]:
        ans += 1
    for j in range(a,ma+1,a):
        seen[j] = True
print(ans)

Submission status: Wrong Answer

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

A.sort()
from collections import Counter
L = dict(Counter(A))

Xs = list(L.keys())
NX = len(Xs)

B = [0]*(10**6+1)

if NX!=1:
    cnt = 0
    for X in Xs:
        if B[X]>0:
            continue
        else:
            if L[X]==1:
                cnt += L[X]
            check = X
            t = 2
            while check*t<10**6+1:
                B[check*t]=1
                t+=1
    print(cnt)
else:
    print(0)

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(1)
    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
    else:
        continue

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
    sys.setrecursionlimit(10 ** 7)

    n = int(readline())
    a = list(map(int, readline().split()))
    a.sort()
    memo = [True] * (2 * 10 ** 6 + 1)
    check = a[0]
    for aa in a[1:]:
        if check % aa == 0:
            ans = -1
            break
    else:
        ans = 0
    for aa in a:
        if memo[aa]:
            ans += 1
            for i in range(1, 10 ** 6 + 1):
                if 10 ** 6 + 1 < i * aa:
                    break
                memo[i * aa] = False
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log,gcd
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
'''
#Pythonを用いる場合
#numpy 1.18.0, scipy 1.4.1, scikit-learn 0.22, numba 0.47.0, networkx 2.4
 
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
'''
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n=ii()
arr=sorted(limii(),reverse=True)

ans=0

for i,k in enumerate(arr[:-1]):
    for j in range(i+1,n):
        if k%arr[j]==0:
            ans+=1
            #print(k,arr[j])
            break
print(n-ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import Counter
def main():
    #入力
    readline=stdin.readline
    n=int(readline())
    a=list(map(int,readline().split()))
    a.sort()

    hosei=0
    c=Counter(a)
    for v in c.values():
        if v>=2:
            hosei+=1

    a_max=10**6+1
    table=[False]*a_max
    cnt=0
    s=set()
    for i in range(n):
        a_i=a[i]
        if a_i in s:
            pass
        else:
            s.add(a_i)
            if table[a_i]==False:
                cnt+=1
            for x in range(a_i,a_max,a_i):
                table[x]=True

    print(cnt-hosei)

if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
def make_divisors(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)

    # divisors.sort()
    return divisors

n = int(input())
list_A = list(map(int, input().split()))
set_A = set(list_A)
ans = 0

for num in list_A:
    set_B = set(make_divisors(num))
    set_A.remove(num)
    d = set_A & set_B
    if len(d) == 0 and len(set_A) != 0:
        ans += 1
    set_A.add(num)

print(ans)