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

A_list = sorted(A_list)
count = 0

for i, A in enumerate(A_list):
    
    is_di = False
    for j in range(0, i):

        if A % A_list[j] != 0:
            continue

        is_di = True

    if (not is_di) and (i != 0):
        count += 1


print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
arr = list(map(int, input().split())) # A1, A2 ... An

count = 0
arr2 = []

for i in range(1, n):
    for j in range(1, i):
        if i != j:
            if (arr[i] % arr[j]) != 0:
                if not i in arr2:
                    arr2.append(i)

print(len(arr2))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3

n = int(input())
A = [int(s) for s in input().split(" ")]

from itertools import product
lst = []
for x, y in product(A, A):
    lst.append(x%y)

counter = 0
for i in range(n):
    if lst[i*n:i*n+n].count(0) == 1:
        counter=counter+1
print(lst)

Submission status: Wrong Answer

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

import math
import bisect

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

A_cnt = {}
for i, Ai in enumerate(A):
    A_cnt.setdefault(str(Ai), 0)
    A_cnt[str(Ai)] += 1

for i, Ai in enumerate(A):
    if A_cnt[str(Ai)] > 1: ans[i] = False

inA = [False] * (10 ** 6 + 1)
for i, Ai in enumerate(A):
    inA[Ai] = True

for i, Ai in enumerate(A):
    for p in range(1, int(math.sqrt(Ai)) + 1):
        if Ai % p == 0:
            if inA[p]:
                ans[i] = False
                break
            if p == 1: continue
            elif inA[Ai // p]:
                ans[i] = False
                break

ans = ans.count(True)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())))
arr = []
du = set()
t = 0

for i in range(n):
    if a[i] == t:
        du.add(a[i])
        continue
    q = a[i] ** 0.5
    for tmp in arr:
        if a[i] % tmp == 0:
            break
        if tmp > q:
            arr.append(a[i])
            break
    else:
        arr.append(a[i])
    t = a[i]

print(len(arr) - len(du))

Submission status: Wrong Answer

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

b = sorted(a)

ans =0
for i in range(len(b)):
    c =[k%b[i] for k in a]
    count = c.count(0)
    if count == 1:
        ans += 1
        
print(ans)

Submission status: Wrong Answer

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

A.sort()
count = 0
for i in range(n - 1):
    if A[i] % A[i + 1] == 0:
        count += 1
        continue
    place = bisect.bisect(A, A[i]//2)
    for j in range(place):
        if A[i] % A[j] == 0:
            count += 1
            break
i = n - 1
for j in range(i):
    if A[i] % A[j] == 0:
        count += 1
        break
print(n - count)

Submission status: Wrong Answer

Solution code:
N=int(input())
a=list(map(int,input().split()))
count=0
a.sort(reverse=True)
while len(a)>1:
    x=a.pop(0)
    if x==a[0]:
        xeq=0
        for i in range(len(a)):
            if x==a[i]:
                xeq+=1
            else:
                break
        del a[:xeq]
        if len(a)==0:
            xeq+=1
        count+=xeq

    for i in a[::-1]:
        if x%i==0:
            count+=1
            break
print(N-count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
cnt = 0
flag = True
A.sort()
tmp = []
i = 0
isDelete = False
while True:
    tmp.append(A[i])
    for j in range(i+1, len(A)):
        if A[j]%A[i] != 0:
            tmp.append(A[j])
    A = tmp.copy()
    tmp = tmp[:i+1]
    if i >= len(A) - 2:
        break
    i += 1

print(len(A))

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
a = list(map(int,input().split()))
a = sorted(a)
flag_list = [False]*n
count = 0
for i in range(n):
    flag = True
    root = math.sqrt(a[i])
    for j in range(i):
        if a[j] > root:
            break
        elif flag_list[j]:
            continue
        elif  (a[i]%a[j]) == 0:
            flag = False
            flag_list[i] = True
            break
    if flag and i <= n-2 and a[i] == a[i+1]:
        flag = False
    if flag:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
# D - Not Divisible
import numpy as np
from collections import Counter

N = int(input())
A = list(int(a) for a in input().split())
c = Counter(A)
dbl = len([i[0] for i in c.items() if i[1] >= 2])

A.sort()
A = np.array(A)
ans = 0
for i in range(N):
    if A[i] == 0:
        continue
    else:
        ans += 1
        B = A % A[i]
        B = B.astype(np.bool)
        A = A * B

print(ans-dbl)

Submission status: Wrong Answer

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

A.sort()
C=[]

while A[0] != max(A):
    B =[]
    for n in range(1,len(A)):
        if A[n] % A[0] !=0:
            B.append(A[n])
    if A[0] != A[1]:
        
        C.append(A[0])
    #print(A,B,C)
    A = B
    if len(A)==0:
        break
    Al = max(A)
    if A[0] == Al:
        C.append(B)
        break
#print(C)
if len(C)>0:
    print(len(C))
else:
    print(0)

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
p = list(map(int,input().split()))
p.sort(reverse=True)
count=0
if np.unique(p).size >1:
    count +=1
for i in range(len(p)):
    if p.count(p[i])>=2:
        continue
    for j in reversed(range(i+1,len(p))):
        if p[i]< p[j]*2 and not p[i]==p[j]:
            count +=1
            break
        if p[i]%p[j] ==0:
            break
        if j == i+1:
            count +=1
if count >=1:
    print(count)
else:
    print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
li = list(map(int,input().split()))
li.sort(reverse=True)
ans = 0

if len(set(li)) == 1:
    ans = 0
else:
    for i,num in enumerate(li,1):
        temp = 0
        for j in range(i,n):
            if num % li[j] == 0:
                break
            else:
                temp += 1
        if temp == n - i:
            ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from math import gcd
from collections import defaultdict
import copy
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()))
ans = 0
if len(set(a)) == 1:
    print(0)
    exit()
for j in a:
    tmp = set(a)
    tmp.remove(j)
    table_ = make_divisors(j)
    for i in table_:
        if i in tmp:
            break
    else:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import collections

n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=0
mis=0
for i in range(len(a)):
  if a[i]==a[i-1]:
    continue
  for j in range(len(a)):
    if a[i]%a[j]==0:
      if i!=j:
        mis=1
        break
  if mis==0:
    ans+=1
  mis=0
print(ans)

Submission status: Wrong Answer

Solution code:
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()))
setA = set(A)
dup = set([x for x in setA if A.count(x) > 1])

count = 0
for i in range(len(A)):
    flag = False
    if A[i] in dup:
        continue
    for div in make_divisors(A[i]):
        if div <= 1 or div == A[i]:
            continue
        elif div in setA:
            flag = True
            break
    if not flag:
        count += 1

print(count)

Submission status: Wrong Answer

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

    for i, div_num in enumerate(A):
        max_num = A[-1]
        counter = 1
        divdiv = div_num

        while max_num >= divdiv:
            if divdiv in A[i + 1:]:
                A = [item for item in A if item is not divdiv]
                
            counter += 1
            divdiv = div_num * counter
        
        if len(A) < 1:
            break

    print(len(A))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

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

if 1 in A:
    print(1)
    exit()

D = collections.Counter(A)


A = list(set(A))

ret = 0
for a in A:
    if is_prime(a) == True:
        if D[a] == 1:
            ret += 1
        continue
    f = make_divisors(a)
    flag = True
    for f2 in f[2:]:
        if D[f2] == 0: continue
        else: flag = False
    if flag: ret += 1


print(ret)

Submission status: Wrong Answer

Solution code:
import sys
import copy

data = sys.stdin
data_list = data.readlines()
data_1 = data_list[0].strip("\n").split(" ")
data_2 = data_list[1].strip("\n").split(" ")

_data = [int(s) for s in data_2]
_data.sort()
_data.reverse()

ans = 0

for i in range(int(data_1[0])):
  flag = 0
  moto = _data[0]
  del _data[0]
  for x in _data:
    if moto % int(x) == 0:
      flag = 1
      break
  if flag == 0:
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
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())
p = list(map(int, input().split()))

cnt = [0] * 1000001

for i in range(n):
    cnt[p[i]] += 1

ans = n

for i in range(n):
    c = make_divisors(p[i])
    for j in range(len(c)-1,0,-1):
        if (not (c[j] == p[i]) or cnt[c[j]] > 1) and cnt[c[j]]:
            ans -= 1
            break
print(ans)

Submission status: Wrong Answer

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

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

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

print(ans+1)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
A=sorted(A)
numCount=0
for i in range(len(A)-1):
    count=0
    for j in range(len(A)-i-1):
        if A[len(A)-i-1]%A[j]==0:
            break
        if j==len(A)-i-2:
            numCount+=1
if N>1:
    if A[0]%A[1]!=0:
        numCount+=1
print(numCount)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
len = len(A)
for i in A:
  for j in A:
    if i != j and i%j == 0:
      len =len - 1
      break
print(len)

Submission status: Wrong Answer

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

b = []
for i in range(1,N):
#    print("i is "+ str(i))
    if i == 1:
        j = 2
    else:
        j = 1
    while A[i-1]%A[j-1]!=0 and j <= N:
        j+=1
#        print("j is "+ str(j))
        if j == i:
            j += 1
        if j == N+1:
            b.append(i)
            break
        
print(len(b))

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int,input().split()))
A = sorted(a, reverse=True)
count = 0
print(A)
if A[N-1] % A[N-2] != 0:
  count += 1
for i in range(N-1):
  flag = False
  for j in range(i+1,N):
    if i != j:
      if A[i] % A[j] == 0:
        flag = True
        break
  if flag == False:
    count += 1
print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(N):
    count = 0
    for j in range(N):
        if A[i] == A[j]:
            continue
        if A[i]%A[j] != 0:
            count += 1
            if count == N-1:
                ans += 1

             

print(ans)

Submission status: Wrong Answer

Solution code:
num = int(input())
a = list(map(int, input().split()))
b = sorted(a)
c = 0
for i in b:
    for f in b[:b.index(i)]:
        if i % f == 0:
            c += 1
            break
print(num - c)

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
A = deque(sorted(list(map(int, input().split())), reverse = True))

B = deque([])
C = deque([])
for i in range(len(A)):
    if A[i] % 2 == 0:
        B.append(A[i])
    else:
        C.append(A[i])

def f(L:list):
    tans = 0
    while len(L) > 0:    
        f = 0
        tans += 1
        s = L.pop()
        N = deque([])
        if len(L) == 0:
            break
        else:
            for i in range(len(L)):
                t = L.popleft()
                if t == s:
                    f = 1
                elif t % s == 0:
                    f = 0
                else:
                    N.append(t)

            L = N
            #print(A)

            if f == 1:
                tans -= 1
            else:
                pass
    
    return tans

ans = f(B) + f(C)       
print(ans)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
def resolve():
    nn = int(input())
    a = {}
    exists = set()
    for i,aa in enumerate(map(int, input().split())):
        if aa not in a:
            a[aa] = i
        else:
            exists.add(aa)
    tt = 0
    for n in a.keys():
        for div in range(1, int(n**0.5)+1):
            if n % div == 0:
                dd = n // div
                if dd != 1 and div in a:
                    break
                if dd != n and dd in a:
                    break
        else:
            tt += 1

    print(tt - len(exists))

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
from collections import Counter

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            i2 = n // i
            if i != i2 and n != i2: # choufuku
                divisors.append(i2)
    # divisors.sort()
    return divisors


exists = [False] * (10 ** 6 + 1)

input = raw_input
input()
As_0 = map(int, input().split(" "))

out = 0

counter = Counter(As_0)
As = counter.keys()


for A in As:
    exists[A] = True

for A1, num in counter.items():
    if num >= 2:
        continue
    
    exist = False

    ds = make_divisors(A1)
    for d in ds:
        if exists[d]:
            exist = True

    if not exist:
        out += 1

print(out)

Submission status: Wrong Answer

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

if a.count(1) == 1 or n == 1:
    print("1")
elif a.count(1) >= 2:
    print("0")
elif len(set(a)) == 1:
    print("0")
else:
    a.sort()
    c = 0
    l = []
    for i in range(n-1):
        if i in l:
            continue
        for j in range(i+1, n):
            if a[j]%a[i] == 0:
                l.append(j)
            if j == n-1:
                c += 1
    print(c+1)

Submission status: Wrong Answer

Solution code:
import collections
N = int(input())
A = list(map(int, input().split()))
A.sort()
collect = collections.Counter(A)
count = 0
if N == 1:
    print(0)
    exit()
for i in range(N):
    judge = True
    if i == 0:
        if collect[A[i]] == 1:
            count += 1
        continue
    if  collect[A[i]] > 1:
        continue
    for j in range(i):
        if A[i] % A[j] == 0:
            judge = False
            break
    if judge:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
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]

from collections import defaultdict,Counter
N = int(input())
A = list(map(int,input().split()))
A.sort()
c = Counter(A)
seen = []
res = 0

for a in A:
  if c[a] > 1: continue
  flg = False
  for s in seen:
    if a % s == 0:
      flg = True
      break

  if flg:
    continue
  else:
    res += 1
    seen.append(a)

print(res)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int, input().split()))
A=sorted(A)
DI={}
for i in A:
  if i not in DI:
    DI[i]=1
  else:
    DI[i]+=1
  
d=0
B=sorted(list(set(A)))
n=len(B)
for i in range(n):
  if DI[B[i]]!=1:
    continue
  d+=1
  for j in range(0,i):
    if A[i]%A[j]==0:
      d-=1
      break
    if A[i]<A[j]*2:
      break
print(d)

Submission status: Wrong Answer

Solution code:
N = int(input())
Mylist = input().split()
Mylist = [int(s) for s in Mylist]
ANS = 0

Mylist.sort()

for i in range(1,N):
    cheack = 0
    for j in range(i):
        if Mylist[i] % Mylist[j] != 0:
            cheack += 1
    if cheack == (i):
        ANS += 1

if Mylist[0] != Mylist[-1]:
    ANS = ANS + 1
print(ANS)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
b = [i for i in list(set(a)) if c[i] == 1]
b.sort()
if len(b) == 0:
    print(0)
elif len(b) == 1:
    print(1)
else:
    ans = 1
    for i in range(1,len(b)):
        for j in range(0,i):
            if b[i] % b[j] == 0:
                break
            if j == i-1:
                ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
M = int(input())
A=list(map(int,input().split()))
A.sort()
ma=A[-1]

k=0
judge=0
ans=0
while True:
    if k>=len(A)-1 or A[k]*2>ma:
        break
    for i in range(len(A)-1,k,-1):
        judge=0
        if A[i]%A[k]==0:
            if A[i]==A[k]:
                judge=1
            A.pop(i)
    k+=1
    ans=ans+judge

print(len(A)-ans)

Submission status: Wrong Answer

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

INF = float("inf")

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

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

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

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

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

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

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

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

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

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

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

def S():
    return input()

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

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

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

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

n = I()
a = RI()

b = list(set(a))
if len(b)==1:
    print(0)
    exit()

# M = int( max(b)**0.5 ) + 1
M = max(b)//2
# print(M)

a.sort()

count = 0

while a:
    flag = False
    m = a[0]
    if m<=M:
        c = a[1:]
        a = []
        for i in c:
            if i==m:
                if flag:
                    count += 1
                else:
                    count += 2
                    flag = True
            elif i%m==0:
                count += 1
            else:
                a.append(i)
    else:
        break

# print(count)
# print(a)

ans = n - count
print(ans)

Submission status: Wrong Answer

Solution code:
def main(N, a):
    a.sort()
    if a[0] == 1:
        return 1
    i = 0
    while True:
        num = a[0]
        if 2 > len(a):
            return len(a)+i
        while True:
            if num == a[1]:
                a = [i for i in a if i != num]
                if 2 > len(a):
                    return len(a)+i
                num = a[0]
            else:
                break
        if num*2 > a[len(a)-1]:
            a = [i for i in a if i % num != 0]
            return len(a)+i+1
        a = [i for i in a if i % num != 0]
        i = i+1


N = int(input())
a = list(map(int, input().split()))
print(main(N, a))

Submission status: Wrong Answer

Solution code:
import math
 
def is_prime(n):
    if n == 1: return False
 
    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
 
    return True
  
n = int(input())
an = list(map(int, input().split()))
an = sorted(an)
 
count = 0
for i, ai in enumerate(an):
    if is_prime(ai) and an.count(ai) == 1:
        count+=1
    elif an.count(ai) == 1:
        ai_2 = (ai + 1) // 2
        for aj in an[:i]:
            if ai % aj == 0:
                break
            if aj > ai_2:
                count+=1
                break
        else:
            count+=1
print(count)

Submission status: Wrong Answer

Solution code:
import math

input()
a = [int(i) for i in input().split()]
a.sort()

L = 0
for n,i in enumerate(a):
    SO = 0
    for k in range(2,int(math.sqrt(i))+1):
        if i % k == 0:
            SO = 1
            break
    H = 0
    if SO == 0:
        if a.count(i) > 1:
            H = 1
    else:
        for m,j in enumerate(a[:n+2]):
            if i % j == 0 and n != m:
                H = 1
                break
    if H == 0:
        L+=1
print(L)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

N = I()
A = LI()
A = sorted(A)
if A[0] == 1:
    if N >= 2 and A[1] == 1:
        print(0)
    else:
        print(1)
    exit()

from collections import Counter

c = Counter(A)

a = 0
D = []
for i in c.keys():
    D.append(i)
    if c[i] >= 2:
        a += 1

D = sorted(D)

ans = 0
B = [0]*(10**6+1)
for i in range(len(D)):
    if B[D[i]] == 0:
        ans += 1
    B[i] = 1
    if D[i]*2 <= 10**6:
        for j in range(D[i]*2,10**6+1,D[i]):
            B[j] = 1

print(ans-a)

Submission status: Wrong Answer

Solution code:
import collections
def is_prime(n):
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return n != 1

n = int(input())
a = sorted(list(map(int, input().split())))
c = collections.Counter(a)
l = []
pena = 0
for idx in c.keys():
    if c[idx] > 1:
        pena += 1
    l.append(idx)
        
ans = []
if l[0] == 1:
    print(1)
else:
    ans.append(l[0])
    for i in range(1, len(l)):
        if is_prime(l[i]):
            ans.append(l[i])
        else:
            flag = True
            for j in range(len(ans)):
                if l[i]%ans[j] == 0:
                    flag = False
                    break
            if flag:
                ans.append(l[i])
    print(len(ans)-pena)

Submission status: Wrong Answer

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

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

print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
def map_all(es):
    return all([e == es[0] for e in es[1:]]) if es else False
if map_all(A):
    print(0)
else:
    B = list(set(A))
    l = len(B)
    k = len(A)-len(B)
    ct = 1-k
    for i in range(1,l):
        for j in range(i):
            if B[i]%B[j] == 0:
                break
            elif j == i-1:
                ct = ct +1
    print(ct)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A = sorted(A, reverse=True)
cnt = 0
for i in range(len(A)-1):
    divide_flag = 0
    for j in range(i+1, len(A)):
        if A[i] % A[j] == 0:
            divide_flag = 1
            break
    if divide_flag == 0:
        cnt += 1
if A[0] == A[-1]:
    print(cnt)
else:
    print(cnt+1)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(s) for s in input().split()]
k = 0
l = []
for i in A: #ｎ個の数について調べる 今調べてるのはi
    for j in A:  #要素で割っていって余りがないか調べる　自分自身で割るときは余らないことに注意
        if (i%j == 0):
            k += 1
    if (k == 1):
        l = l + [i]
    k = 0
print(l)
print (len(l))

Submission status: Wrong Answer

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

if a_l[0] == 1:
    cnt = 0
    for val in a_l:
        if val == 1:
            cnt += 1
        else:
            break
    print(cnt)
    exit()

flag = 0
cnt = 1
challengers = [a_l[0],]
for i in range(1,n):
    if a_l[i] in challengers:
        if flag == 0:
            cnt -= 1
        flag = 1
        continue
    else:
        flag = 0
    for num in challengers:
        if a_l[i]%num == 0:
            break
    else:
        cnt += 1
        challengers.append(a_l[i])

print(cnt)

Submission status: Wrong Answer

Solution code:
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()))
b = list(set(sorted(a)))
c = [1]*len(b)
if len(b)==1:
    print(0)
else:
    for j in range(1,len(b)):
        f = set(b)-set([b[j]])
        g = set(make_divisors(b[j]))
        if len(list(f&g)) !=0:
            c[j] =0
    print(c.count(1))

Submission status: Wrong Answer

Solution code:
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()))
b = set()
if len(set(a)) == 1:
    print(0)
    exit()
a.sort()
cnt = 0

for i in a:
    flg = True
    l = set(make_divisors(i))
    if len(l & b) == 0:
        cnt += 1
    b.add(i)
print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())))
if(len(list(set(a)))==1 and len(a)!=1):print(0);exit()
if(1 in a):print(1);exit()
prime_q = []
for i in range(10**6+2):
    prime_q.append(True)

ans = 0
for i in a:
    if(prime_q[i] == True):
        ans+=1
        c = 1
        while(True):
            try:prime_q[i*c] = False
            except:break
            c+=1

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))
k = {}
count = 0
for a in A:
    if a not in k:
        ret = np.mod(a, A[A < a])
        if np.all(ret > 0):
            count += 1
    k[a] = 1
print(count)

Submission status: Wrong Answer

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

a.sort(reverse=True)
ans = 0

for i in range(n - 1):
    for j in reversed(range(i + 1, n)):
        if a[i - 1] == a[i] or a[i] == a[i + 1]:
            break
        elif a[i] % a[j] == 0:
            break
        elif a[i] < a[j] ** 2 or j == i + 1:
            ans += 1
            break

if a[n - 2] != a[n - 1]:
    ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = set()
cnt = 0
for i in range(N-1):
  for j in range(N-1):
    if A[j] % A[i] == 0 and i != j:
      B.add(A[j])
for i in range(N-1):
  if A[j] == A[i] and i != j:
    cnt += 1
    
print(N-cnt-len(B)-1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

print(cnt)

Submission status: Wrong Answer

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

l = []
l.append(a[0])
cou =[]

def isPrime(n):
  if n < 2:
    # 2未満は素数でない
    return False
  if n == 2:
    # 2は素数
    return True
  for p in range(2, n):
      if n % p == 0:
        # nまでの数で割り切れたら素数ではない
        return False
  # nまでの数で割り切れなかったら素数
  return True

for i in range(1,n):
    b = a[i]
    if not isPrime(b):
      for j in range(len(l)):
        if b==l[j]:
          cou.append(b)
          break
        if b%l[j]==0:
            break
      else:
          l.append(b)
    else:
      l.append(b)
print(len(l)-len(set(cou)))