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:
#!/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())

def divisor(n): 
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table

if len(l) == 1 or l[0] == 1:
    print(0)
    exit()

is_sosu = [False for _ in range(l[-1] + 1)]
ans = 0
for i1 in range(len(l)):
    d = divisor(l[i1])
    b = [is_sosu[d_] for d_ in d]
    
    if not True in b:
        ans += c[l[i1]]

    is_sosu[l[i1]] = True

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = sorted(list(map(int,input().split())))
res = []
while len(A)>2:
    if A[0]==A[1]:
        suicFlag = True
    else:
        suicFlag = False
    delInt = A[0]
    A = [c for c in A if c % delInt != 0]
    if not suicFlag:
        res.append(delInt)
print(len(res)+len(A))

Submission status: Wrong Answer

Solution code:
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())))
new_A=list(set(A))
new_A.sort()
kotei_A=copy.copy(new_A)
tmp_A = copy.copy(new_A)
count=0

for i in kotei_A:
  tmp_A.remove(i)
  yaku=list(set(make_divisors(i)) & set(tmp_A))
  if(len(yaku)==0):
    count+=1
  else:
    new_A.remove(i)

  tmp_A = copy.copy(new_A)
  
if(len(new_A)==1):
  print(0)
else:
  print(count)

Submission status: Wrong Answer

Solution code:
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7

def prime_factorize(n: int) -> list:
    return_list = []
    while n % 2 == 0:
        return_list.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            return_list.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        return_list.append(n)
    return return_list

def make_divisors(n: int) -> list:
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if i == 1:
            continue
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    return divisors

def main():
    n = i_input()
    num_list = i_list()

    num_list.sort()
    num_list = set(num_list)

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

    count = 0

    for num in num_list:
        yakusu_list = make_divisors(num)
        if len(yakusu_list) == 0:
            count += 1
            continue
        tmp = 0
        for yakusu in yakusu_list:
            if yakusu in num_list:
                break
            tmp += 1
        if tmp == len(yakusu_list):
            count += 1

    print(count)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
l_list = []
for i in range(n):
    if (i < n-1 and a[i] != a[i+1]) or i == n-1:
        flag = 0
        for l in l_list:
            if a[i] % l == 0:
                flag = 1
        if flag == 0:
            l_list.append(a[i])

print(len(l_list))

Submission status: Wrong Answer

Solution code:
def main():
    from collections import Counter

    n = int(input())
    A = sorted(map(int, input().split()))
    c = Counter(A)
    flag = [False] * n
    for i in range(n):
        if c[A[i]] > 1:
            flag[i] = True
            continue
        if flag[i] == False:
            for j in range(i+1, n):
                if A[j] % A[i] == 0:
                    flag[j] = True
    print(flag.count(False))
main()

Submission status: Wrong Answer

Solution code:
N=input();
N=int(N);
A=input().split();
A=[int(s) for s in A];
ans_list=[];
flag=True;
for i in range(N):
  for j in range(i,N):
    if i==j:
      continue;
    if A[i]%A[j]==0:
      flag=False;
      break;
  if (not A[i] in ans_list) and flag==True:
    ans_list.append(A[i]);
  flag=True;
print(len(ans_list))

Submission status: Wrong Answer

Solution code:
import sys
N = list(map(int, input().split()))
A= list(map(int, input().split()))
A=sorted(list(set(A)),reverse=True)
count=0
if len(A)==1:
    print('0')
    sys.exit()
for n in range(len(A)):
    judge=0
    for j in range(len(A)):
        if n!=j and A[n]%A[j]==0:
            judge=1
            break
    if judge==0:
        count+=1
print(count)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
a = Counter(map(int, input().split()))
ans = n
for num, count in a.items():
    if count > 1:
        ans -= count
        continue
    if 1 in a and num != 1:
        ans -= count
        continue
    if num % 2 == 0:
        if (2 in a or (num // 2) in a) and num != 2:
            ans -= count
            continue
    i = 3
    while i * i <= num:
        if num % i == 0:
            if i in a or (num // i) in a:
                ans -= count
                break
        i += 2
print(ans)

Submission status: Wrong Answer

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

a = sorted(set(a))
w = 0
while True:
    h = 1
    cn = 0
    while True:
        if w + h == len(a):
            '''
            print(a)
            '''
            if cn == 1:
                del a[w]
                w -= 1
            break
        if a[w] == a[w+h]:
            cn =1
        if a[w+h] % a[w] == 0:
            '''
            print(h)
            '''
            del a[w+h]
        else:
            '''
            print(a[w+h], h, w, a)
            '''
            h += 1
    w += 1
    if w == len(a):
        print(len(a))
        exit()

Submission status: Wrong Answer

Solution code:
from collections import deque
import copy
m=int(input())
a=list(map(int, input().split()))
a.sort()

li= []
li.append(a[0])
for i in range(1,len(a)):
    if all(a[i]%j != 0 for j in li):
        li.append(a[i])
    elif not all(a[i] != j for j in li):
        li.remove(a[i])


print(len(li))

Submission status: Wrong Answer

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

a.sort(reverse=True)
cnt = 0
div = False
for i in range(1,len(a)+1):
    div = False
    for j in range(i,len(a)):
        if i-1 == j :
            continue
        if a[i-1] % a[j] == 0:
            div = True
            break
    if div :
        cnt += 1
for i in range(0,len(a)-1):
    if a[n-1] % a[i] == 0:
        cnt += 1
        break

print(n - cnt)

Submission status: Wrong Answer

Solution code:
import math

n=int(input())

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

count=0
isDividable=0

for i in range(n):
  isDividable=0
  l=a[i]/2
  for j in range(n):
    if i != j and a[j] <= l and a[i] % a[j] == 0:
      isDividable=1
      break
  if isDividable==0:
    count=count+1
print(count)

Submission status: Wrong Answer

Solution code:
def make_divisors(n,B):

    if 1 in B:
        return False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            if i in B:
                return False
            if n//i in B:
                return False
    # divisors.sort()
    return True



def resolve():
    N = int(input())
    A = list(map(int,input().split()))
    B= set(A)

    A.sort()

    count = 0
    for idx,i in enumerate(A):
        if i == A[idx -1]:
            continue
        if idx != N-1 and i == A[idx +1]:
            continue
        if make_divisors(i,B):
            count+=1
    print(count)
resolve()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(input().split())
s_1 = [x for x in set(a) if a.count(x)>1]
l = len(s_1)
for i in range(n):
    a[i] = int(a[i])
a.sort()
count = 0
for i in range(n):
    flag = 0
    for j in range(i):
        if a[i]%a[j] == 0 or a[i] == a[j]:
            flag += 1 
    if flag == 0:
        count += 1 

print(count-l)

Submission status: Wrong Answer

Solution code:
def LI(): return list(map(int, input().split()))
def I(): return map(int, input().split())
  
def main():
  m = int(input())
  a = LI()
  ans = 0
  n = max(a)
  num = [True]*(n+1)
  num[0] = num[1] = False
  for i in a:
    if a.count(i) != 1: num[i] = False
    for j in range(i*2, n+1, i):
      num[j] = False
  for aa in a:
    if num[aa]:
      ans += 1
  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(1,i+1):
      if A[i]%A[i-j] == 0:
        count -= 1
        break
print(count)

Submission status: Wrong Answer

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

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:
      _ans += 1
      break
print(int(data_1[0]) - _ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = sorted(map(int,input().split()))
numbers = [0]*(max(A)+1)

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]


answer = 0
for i in range(N):
    yakusu = make_divisors(A[i])
    judge = 1
    for j in range(1,len(yakusu)-1):
        if numbers[yakusu[j]] != 1:
            judge = 0
    if judge == 1:
        answer += 1
    numbers[A[i]]=1
    if A[i]==A[i-1]:
        answer -= 1
    
print(answer)

Submission status: Wrong Answer

Solution code:
import math, copy

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

ans = 0
A.sort()

for i in range(len(A)):
    root = math.sqrt(A[i])
    for x in range(1, int(root)+1):
        if (A[i] / x in A[:i]) or (A[i] / x in A[i+1:]) or ((x in A) and (A[i] % x == 0)):
            break
    else:
        ans += 1

print(ans)

Submission status: Wrong Answer

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

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

aset=set(orga)

def m_div(n,aset):
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            if i!=n and i in aset:
                return False
            if i != n // i:
                if (n//i != n) and (n//i in aset):
                    return False
    return True

ans=0
dups=set()
fins=set()
for num in orga:
    if num in fins:
        dups.add(num)
        continue
    if m_div(num,aset):
        ans+=1
    fins.add(num)

print(ans-len(dups))

Submission status: Wrong Answer

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

count = []
for i in range(N//2 + 1):
    dev = 0
    for j in range(0, i):
        if A[i]%A[j] == 0:
            dev = 1
            count.append(i)
            count.append(j)
            #print(A[i], A[j])
#   if dev == 1:
#       %print(i)
print(N-len(set(count)))

Submission status: Wrong Answer

Solution code:
N = int,input()
p = sorted(list(map(int,input().split())),reverse=True)
#print(p)
count = 0

for i in p:
    sabun = list(set(p) - set([i]))
    if len(sabun) == 0:
        count = len(p)
    for j in sabun:
        if i % j == 0:
            count += 1
            break
    
print(len(p)-count)

Submission status: Wrong Answer

Solution code:
import itertools
#H, W = map(int,input().split())
N = int(input())
al = list(map(int,input().split()))
al.sort(reverse=True)

cnt = 0
for i in range(N):
    flg = 0
    for j in range(i+1,N):
        if (al[i] or al[j]) == 0:
            flg = 1
            break
        elif al[i] == al[j]:
            flg = 1
            break
        elif al[i] % al[j] == 0:
           flg = 1
           break

    if flg == 0:
        cnt += 1
        # elif al[i] != al[j] and al[i] % al[j] != 0:
        #     print(al[i], al[j])
        #     cnt += 1
        #     al[i] = 0

print(cnt)

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
a = sorted(list(map(int,input().split())))
if 1 < len(a):
    c = 1 if a[0] == a[1] else 0
else:
    c = 0
for i in range(1, n):
    x = a[i]
    for j in range(math.ceil(i/2)):
        if j == i:
            continue
        if (x % a[j] == 0) or (x % a[i-j-1] == 0):
            break
    else:
        continue
    c+=1
print(n-c)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
limit = max(A) / 2
def eratos(A, limit):
    prime = []
    while True:
        if len(A) == 0:
            return prime
        p = A[0]
        if limit < p:
            return prime + A
        #print(p)
        #print(A)
        prime.append(p)
        A = [x for x in A if( x % p != 0)]


eratosed_list = eratos(A, limit)
#print(f'eratosed_list:{eratosed_list}')
print(len([x for x in set(eratosed_list) if eratosed_list.count(x) == 1]))

Submission status: Wrong Answer

Solution code:
def divisor(n): 
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table
  
import bisect,collections,copy,heapq,itertools,math,string
import sys
def S(): return sys.stdin.readline().rstrip()
def M(): return map(int,sys.stdin.readline().rstrip().split())
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())
N = I()
A = LI()
d = collections.deque(A)
ans = 0
if d.count(1) >= 2:
    ans = N
else:
    if d.count(1) == 1:
        ans = N-1

    for i in range(N):
        c_d = copy.deepcopy(d)
        c_d.remove(A[i])
        if A[i] in c_d:
            continue
        else:
            yakusu_list = divisor(A[i])
            warikirenai = True
            for j in yakusu_list:
                if j in c_d:
                    warikirenai = False
                    break
            if warikirenai == True:
                ans += 1
                if ans == N:
                    break
print(ans)

Submission status: Wrong Answer

Solution code:
import copy
n=int(input())
a=list(map(int,input().split()))
a2=[x for x in set(a) if a.count(x) > 1]
a=set(a)
b=copy.deepcopy(a)
b2=set()
b3=set()
for i in a:
  if len(b)==0:
    break
  if i not in b :
    continue
  for j in b:
    if j % i!=0:
      b2.add(j)
  b=copy.deepcopy(b2)
  b2.clear()
  b3.add(i)
c=0
for m in b3:
  if m not in a2:
    c+=1
print(c)

Submission status: Wrong Answer

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

import numpy as np

ans = 0
for i in range(N):
    A_re = np.array([j for j in A if not j == A[i]])
    np.array(A[i])
    #print(A[i],A_re)
    if len(A_re) == 0:
        ans = 0
        break
        break
    c = [j for j in A[i]/A_re if j.is_integer() ]
    if len(c) == 0:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import collections
n=int(input())
a=list(map(int,input().split()))
if 1 in a:
  print(1)
  sys.exit()
C=list(collections.Counter(a).items())
t=[] 
for i in range(len(C)):
  if C[i][1]>1:
    t.append(C[i][0])
t=set(t) #カブッタヤツら
b=list(set(a))
m=len(b)
b.sort()
Lst=[]
for i in range(m):
  l=2
  num=b[i]*l
  while num<10**6+1:
    Lst.append(num)
    l+=1
    num=b[i]*l
c=set(Lst)
d=set(b)
e=c&d
f=(d-e)&t
print(m-len(e)-len(f))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = sorted(map(int, input().split()))
sum(sum(A[j] % A[i] == 0 for i in range(j)) == 0 and (j == N - 1 or A[j] < A[j + 1]) for j in range(N))

Submission status: Wrong Answer

Solution code:
from sys import stdin
import sys

MAX_A = 1000000;
N = int(stdin.readline().rstrip())
A = sorted([int(x) for x in stdin.readline().rstrip().split()])
A_one = [x for x in set(A) if A.count(x) == 1]

M = [False]*MAX_A
ans = 0
for a in A_one:
  if M[a] == False:
    ans+=1
    M[::a] = [True]*(len(M[::a]))
    
print(ans)

Submission status: Wrong Answer

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

import numpy as np
from collections import Counter


N = int(input())
A = np.array(readline().split(), dtype=np.int64)
count = Counter(A)
A = np.array([
    a for a, c in count.items() if c == 1
])
if len(A) == 0:
    A = np.sort(A)
i = 0
while True:
    if len(A) == 0:
        break
    pre = A
    a = A[i]
    A = np.delete(A, np.where((A % a == 0) & (A != a)))
    i += 1
    if len(pre) == len(A) or i >= len(A):
        break

print(len(A))

Submission status: Wrong Answer

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


N = int(input())
Alist = list(map(int, input().split()))
setA = list(set(Alist))
setA.sort(reverse=True)
dnum = len([x for x in setA if Alist.count(x) > 1])

cnt = 0
for idx, item in enumerate(setA):
    sub = setA[:idx:-1]
    for s in sub:
        if item % s == 0:
            break

    else:
        cnt += 1

if 1 in setA:
    cnt += 1

print(cnt - dnum)

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])
ns = sorted([i for i in ns if i not in dubbles])
def primes(n):
    i = 1
    p = [2]
    while i+2 <= n:
        flag = True
        i += 2
        for j in range(3, int(i**(1/2))+1, 2):
            if i % j == 0:
                flag = False
                break
        if flag:
            p.append(i)
    return p
if not ns:
    print(0)
    exit()
ps = set(primes(ns[-1]))
a = []
for i in ns:
    if i in ps:
        ans += 1
        dubbles.add(i)
    else:
        a.append(i)
n = len(a)
def make_divisors(n):
    divisors = set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.add(i)
            if i != n // i:
                divisors.add(n//i)
    return divisors

for i in range(n):
    if make_divisors(a[i]) & dubbles:
        dubbles.add(a[i])
        continue
    ans += 1
    dubbles.add(a[i])
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

n = int(input())
a = list(set(map(int, input().split())))
if len(a) == 1:
    print(0)

a.sort()

limit = max(a)
for i, num in enumerate(a):
    for m in (a[i + 1:]):
        if m % num == 0:
            a.pop(a.index(m))

print(len(a))

Submission status: Wrong Answer

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

if n == 1:
    print(1)
    exit()

now = 0
b = [True]*n
for i in range(n):
    if a[i] < now * 2:
        continue
    if i < n-1 and a[i] == a[i+1]:
        b[i] = False
        b[i+1] = False
    now = a[i]
    for j in range(i+1, n):
        if a[j] % a[i] == 0:
            b[j] = False
print(sum(b))

Submission status: Wrong Answer

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

N = int(input())


if N == 1:
    print(int(input()))
    sys.exit()

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

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

count = 1
A = sorted(A)
B = [A[0]]

for i in range(len(A)-1):
    Flag = True
    for j in B:
        if A[i+1] % j == 0:
            Flag = False
    if Flag == True:
        B.append(A[i+1])

print(len(B))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
import math
A.sort()
A_set = set(A)
count = 0
last_num = 0
flag = True
now_num = 0
half_num = 0
count_flag = False

if A.count(1) == 1:
    print(1)
    exit()
for i in range(N):
    count_flag = True
    now_num = A[i]
    sqrt_num = math.sqrt(A[i])
    if now_num == last_num:
        if flag:
            count -= 1
            flag = False
    else:
        for j in range(0, i):
            if A[j] > sqrt_num:
                break
            if now_num % A[j] == 0:
                count_flag = False
                break
        if count_flag:
            if not flag:
                flag = True
            count += 1
        last_num = A[i]
print(count)

Submission status: Wrong Answer

Solution code:
import numpy as np
 
N = int(input())
x_list = np.array(list(map(int, input().split()))).reshape(1,N)
#count = np.sum(x_list%x_list.reshape(N,1)==0, axis=0)==1
#print(np.sum(count))

Submission status: Wrong Answer

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

if n == 1:
    print(0)
else:
    if a_list[0] != a_list[1]:
        ans += 1
    for i in range(1, n):
        if i != n - 1 and a_list[i] == a_list[i + 1]:
            continue
        for j in range(i):
            if a_list[i] % a_list[j] == 0:
                break
            if a_list[j] > a_list[i] / 2:
                ans += 1
                break
            if j == i - 1:
                ans += 1
                break
print(ans)

Submission status: Wrong Answer

Solution code:
import math
n = int(input())

a = [0 for _ in range(n)]
a_s = [[] for _ in range(n)]
a = [int(s) for s in input().split()]
list.sort(a,reverse=False)

a_s = set(a)
ans = n

def sol(n):
    st = []
    temp = n
    mx = int(math.sqrt(n))

    for i in range(2,mx+1):
        if(n%i == 0):
            st.append(n//i)
            st.append(i)
    
    return st


#print(sol(24))
flag = 0
for i in range(n):
    if(i < n-1 and a[i] == a[i+1]):
        flag = 1
        ans -= 1
        continue
    
    s_tmp = sol(a[i])
    for x in s_tmp:
        if(x in a_s):
            ans -= 1
            break
        
if(flag == 1):
    ans -= 1
    
print(ans)

Submission status: Wrong Answer

Solution code:
#import numpy as np
#import random
#import time
from collections import defaultdict

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

def main():
    #N = 20
    #A = [random.randint(1, int(1e6)) for _ in range(int(N))]
    N = int(input())
    A = [int(c) for c in input().split(' ')]
    #t1 = time.time()
    dup = set(x for x in A if A.count(x)>1)
    A = list(set(A))
    N = len(A)
    A.sort()
#    B = [factorization(x) for x in A]
#    B.sort()

    d = defaultdict(list)
    B = []
    for x in A:
        x_fac = factorization(x)
        B.append(x_fac)
        for y in x_fac:
            d[y[0]].append(x)
    assert len(A)==len(B)
    #print(A)
    #print(B)
    #print(d)
    dp = [1] * (N+1)
    for i in range(1,N):
        bi = A[i]
        bi_fac = B[i]
        can_divide = False
        for y in bi_fac:
            for a in d[y[0]]:
                if bi % a == 0 and bi != a:
                    #print(a,bi)
                    can_divide = True
                    break
                elif a > bi:
                    break
            if can_divide:
                break
        if can_divide or bi in dup:
            dp[i] = dp[i-1]
        else:
            dp[i] = dp[i-1] + 1
    print(dp[N-1] - len(dup))
    #print(time.time() - t1)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# D

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

# 降順に並べ替え
B.sort(reverse=True)

A = list(dict.fromkeys(B))

ans = 0
N = len(A)

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

if N == 1:
  ans += 1
elif 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()))
x=0
A=sorted(a)
if(A.count(A[0])==N):
    print(0)
else:
    for i in range(N):
        if A[i] in (A[i+1:]):
            break
        else:
            for j in (range(i)):
                if(A[i]%A[j]==0):
                    break
                else:
                    x +=1
    print(x-1)

Submission status: Wrong Answer

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

A.sort()
checked = []
ans = 0
before = 0
first = True
for i in A:
    if before == i and first:
        if flag:
            ans -= 1
        first = False
        break
    elif before != i:
        first = True
    elif not first:
        break
    flag = True
    for l in checked:
        if l > i // 2:
            break
        if i % l == 0:
            flag = False
            break
    if flag:
        checked.append(i)
        ans += 1
    before = i

print(ans)

Submission status: Wrong Answer

Solution code:
import math
from collections import deque

N = int(input())
A = list(input().split())
A = deque(sorted([int(A[i]) for i in range(N)]))
prime = set([])
count = 0

for i in range(N):
    Frag = True
    tmp = A.popleft()
    for j in range(1, int(math.sqrt(tmp) +1)):
        if tmp % (j+1) == 0:
            if (j+1) in prime or (tmp // (j+1)) in prime:
                Frag = False
                break
    if tmp in prime:
        Frag = False
    if Frag:
        prime.add(tmp)
        if tmp not in A:
            count += 1

print(count)

Submission status: Wrong Answer

Solution code:
import sys 
n = int(input())

if n == 1:
    print(0)
    sys.exit()

nums = sorted(map(int,input().split()))

ans = []
ans.append(nums[0])
for i in range(1,n):
    for j in ans:
        if nums[i] % j == 0:break 
    else:ans.append(nums[i])
    
print(len(ans))

Submission status: Wrong Answer

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

if A.count(1) >= 1:
    print(A.count(1))
    exit()

i = 0
now = A[0]
D = []
cnt = 1
while i < n:
    if i+1 < n:
        if A[i+1] == now:
            cnt += 1
            i += 1
            continue

        if cnt == 1:
            D.append(now)

        now = A[i+1]
        cnt = 1
    i += 1

if cnt == 1:
    D.append(now)


b = [False]*1000005
seen = [False]*1000005
cnt = 0
for a in D:
    if seen[a]:
        continue

    seen[a] = True
    if b[a] == False:
        cnt += 1

    for i in range(a, 1000005, a):
        b[i] = True
print(cnt)

Submission status: Wrong Answer

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

A.sort()


def div_by_min(a: list, start: int):
    del_list = {}
    for i in range(start+1, len(a)):
        if A[i] % A[start] == 0:
            del_list[A[i]] = 0
    ans_list = []
    for num in a:
        if num not in del_list:
            ans_list.append(num)
    return ans_list


Start = 0
prev_len = 1000000
tmp = A

while True:
    if Start >= len(tmp):
        break
    else:
        tmp = div_by_min(tmp, Start)
        if prev_len == len(tmp):
            Start += 1
        else:
            prev_len = len(tmp)
            Start = 0

print(len(tmp))

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 i in range(len(A)):
    if cnt[A[i]] > 1:
        continue
    idx = bisect.bisect_right(A, pow(A[i],0.5))
    J = min(idx+1,i)
    #J = i
    ok = True
    for j in range(J):
        #print(i,j)
        if A[i] % A[j] == 0:
            ok = False
            break
    if ok:
        ans += 1
print (ans)

Submission status: Wrong Answer

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

A_sort = sorted(A, reverse=True)

cnt = 0

for i in range(N):
    L = A_sort[i]
    for j in range(N-1, i, -1):
        R = A_sort[j]
        if L % R == 0:
            break
            
        if R > L/2 or j == i+1:
            cnt += 1
            break
            
if N==1 or (A_sort[-1] != A_sort[-2]):
    cnt += 1

print(cnt)