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.sort()
cnt = n

if n != 1:
    if a[0] == a[1]:
        cnt -= 1

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

Submission status: Wrong Answer

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

ans = 0
a = sorted([x for x in set(a) if a.count(x) == 1])

for i , Ai in enumerate(a):
    cnt = 0
    for j in range(i):
        if Ai % a[j] == 0:
            cnt += 1
    if cnt == 0:
        ans += 1
        

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

A.sort()
A2 = copy.copy(A)

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
def solution():
    n = int(input())
    inputList = list(map(int, input().split()))
    numpyArray = np.array(inputList)
    numpyArray = np.unique(numpyArray)
    resultCount = 0
    for i in range(numpyArray.size):
        newArray = numpyArray[numpyArray != inputList[i]]
        test = lambda x: inputList[i] % x
        newArray = test(newArray)
        if newArray.size>0 and 0 not in newArray:
            resultCount += 1

    print(resultCount)

solution()

Submission status: Wrong Answer

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

count=0
for i in l:
  for num in range(n):
    if i%l[num]==0:
      if i!=l[num]:
        count+=1
    break
      
print(n-count)

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=0
    while len(P)>1:
        sum1+=1
        P1=[x for x in P if x%P[0]==0]
        for x in P1:
            P.remove(x)
    sum1+=1
    print(sum1)

Submission status: Wrong Answer

Solution code:
#! env/bin/local python3


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


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


counter = 0
for ac in a:
    if len(make_divisors(ac) & set(a)) > 1:
        counter += 1

print(n - counter)

Submission status: Wrong Answer

Solution code:
input()
nums = [int(s) for s in input().split(" ")]
nums.sort(reverse=True)
count = 0
for i in range(len(nums) - 1):
    flag = 0
    for j in range(1, len(nums) - i):
        print("{0} % {1} = {2}".format(nums[i], nums[i + j], nums[i]%nums[i + j]))
        if nums[i]%nums[i + j] == 0:
            flag = 1
    if flag == 0:
        count = count + 1
print(count + 1)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
a.reverse()
number=0
judge=0
for i in range(n):
  for j in range(i+1,n):
    1

Submission status: Wrong Answer

Solution code:
import sys
import collections

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
    c = collections.Counter(As)

    if N == 1:
        print(1)
    elif len(set(A)) == 1:
        print(0)
    elif c[1] != 0:
        if c[1] == 1:
            print(1)
        else:
            print(0)
    else:
        for i in range(N-1):
            print("i", i)
            k = N-1
            if c[As[i]] >= 2:
                ans -= 1
                if i == N-2:
                    ans -= 1
            else:
                for j in range(N):
                    if k == i:
                        break
                    elif As[i] % As[k] == 0:
                        ans -= 1
                        break

                    k -= 1

        print(ans)


if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline


def main():
    N = int(input())
    arr = list(map(int, input().split(" ")))

    my2dict = dict()

    def calc(i, j):
        if i != j and arr[i] >= arr[j] and arr[i] % arr[j] == 0:
            my2dict[i][j] = True
            if j not in my2dict:
                my2dict[j]=dict()
            my2dict[j][i] = False
        else:
            my2dict[i][j] = False

    def query(i, j):
        if i in my2dict:
            if j in my2dict[i]:
                return my2dict[i][j]
            else:
                calc(i, j)
                return my2dict[i][j]
        else:
            my2dict[i] = dict()
            calc(i, j)
            return my2dict[i][j]

    cnt = 0
    for i in range(N):
        for j in range(N):
            if query(i,j):
                cnt += 1
                break

    print(N-cnt)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
a=sorted(A)
total=0
c=True
t=0
for i in range(N):
    if c==True:
        t=0
        for j in range(1,len(a)):
            if len(a)==0:
                c=False
                break
            try:
                if a[j-t]%a[0]==0:
                    if a[0]==a[1]:
                        del a[0]
                        del a[1]
                        c=False
                        break
                    else:
                        del a[j-t]
                        t+=1
            except:
                break
        try:
            del a[0]
        except:
            break
        if c==True:
            total+=1
    else:
        break
print(total)

Submission status: Wrong Answer

Solution code:
import copy

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
  
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 = list(map(int, input().split()))
  
ans = 0
for a in A:
  if is_prime(a):
    ans += 1
  else:
    d_list = divisor(a)
    tmp = copy.copy(A)
    tmp.remove(a)
    if len(set(d_list) & set(tmp)) == 0:
      ans += 1
    
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

for i in range(n):
    if a[i] == t:
        if arr and arr[-1] == t:
            arr.pop()
        continue
    t = a[i]
    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])

print(len(arr))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
divisible = int()
dup = len([x for x in set(A) if A.count(x) > 1])
# print(dup)
B = A[:]
for i, a in enumerate(A):
  r_range = i - divisible
  for ri, r in enumerate(B[:r_range]):
#    print(a,r)
    if a % r == 0:
      divisible += 1
#      print(B[:r_range], B.pop(r_range), B)
      break
print(N - divisible - dup)

Submission status: Wrong Answer

Solution code:
def calc():
    n, *a = map(int, open(0).read().split())
    appear = {}
    for x in a:
        if x in appear:
            appear[x] = False
        else:
            appear[x] = True

    r = set(a)
    count = 0
    for x in r:
        s = r & divs(x)
        if not s and appear[x]:
            count += 1
    return count

def divs(n):
    ds = set()
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            ds.add(i)
            if i != n // i:
                ds.add(n//i)
    return ds

print(calc())

Submission status: Wrong Answer

Solution code:
n = int(input())

a=list(map(int,input().split()))
a.sort(reverse = True)
from collections import deque
from collections import Counter as cnt
from math import sqrt
aaa = dict(cnt(a))

maa = round(sqrt(a[0]))
ma = maa+1

ans = []
a = deque(a)
while True:
    if len(a) < 1 :
        break
    i = a.pop()
    ans.append(i)

    b = deque()
    while len(a)>0:
        j = a.pop()
        if j%i !=0:
            b.appendleft(j)
    a = b.copy()

    if i >= ma:
        ans += a
        break


mans = 0
for i,v in aaa.items():
    if (i in ans) & (v == 1) :
        mans+=1

print(mans)

Submission status: Wrong Answer

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

n=int(input())
a=list(map(int,input().split()))
a.sort()
flag=0
cnt=0
for i in range(n):
    for j in range(n-i):
        if i==j:
            pass
        elif a[i]%a[j]==0:
            flag=1
            break
    if flag==0:
        cnt+=1
    else:
        flag=0
print(cnt)

Submission status: Wrong Answer

Solution code:
A1 = [int(x) for x in input().split()]
p = [int(x) for x in input().split()]
N = A1[0]
i_list=[]
for i in range(N):
  for j in range(N):
    if i!=j and p[i] % p[j]==0:
      i_list.append(p[i])
      break
check = set(p) & set(i_list)
print(N-int(len(list(check))))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce, lru_cache  # @lru_cache(None)
from fractions import gcd
import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**6)
# ----------------------------------------------------------- #

n = int(input())
A = list(int(x) for x in input().split())
A.sort()
ans = 0
ANS = []
while A:
    p = A[0]
    if p > 10**3:
        break
    else:
        if len(A) <= 1 or p not in A[1:]:
            ANS.append(p)
        A = [a for a in A[1:] if a % p != 0]

ans = len(ANS) + len(A)

Submission status: Wrong Answer

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

A.sort()

se = set(A)
if len(se) == 1 and N > 1:
    print(0)
    exit()

for i in range(N):
    tmp = set()
    for s in se:
        if s == A[i] or s % A[i] != 0:
            tmp.add(s)
    se = tmp

print(len(se))

Submission status: Wrong Answer

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

table = [0 for i in range(10**6)]
ans = 0
a.sort()
a.append(10**7)
for i in range(n):
    el = a[i]
    if table[el-1] != 0:
        continue
    else:
        if el != a[i+1]:
            ans += 1
    idx = el
    while idx-1 < 10**6-1:
        table[idx-1] += 1
        idx += el

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=0
b=a.copy()
a=set(a)
for i in range(1,b[-1]+1):
    bi=b.count(i)
    if bi>=2:
        for j in range(bi):
            b.remove(i)
a=list(a)
n=len(a)
m=len(b)
for i in range(m):
    for j in range(n):
        if a[j]>b[i]:
            break
        elif a[j]!=b[i] and b[i]%a[j]==0:
            b[i]=0
            break
print(m-b.count(0))

Submission status: Wrong Answer

Solution code:
import sys

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

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

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

a.sort()
ans = 0
for i in range(n):
    cnt = 0
    for j in reversed(range(n)):
        if i != j:
            if a[j] % a[i] != 0:
                cnt += 1
                if cnt == n-1:
                    ans += 1
            else:
                break
print(ans)

Submission status: Wrong Answer

Solution code:
def multi_diff(es):
    return es == [es[0]] * len(es) if es else False

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

if multi_diff(a):
    print(0)
else:
    a = list(set(a))
    a.sort()
    dele = []
    i = 0
    while i < len(a)-1:
        for j in range(i+1, len(a)):
            if a[j] % a[i] == 0:
                dele.append(j)
        for k in reversed(dele):
            a.pop(k)
        i += 1
        dele.clear()
    print(len(a))

Submission status: Wrong Answer

Solution code:
from math import sqrt
N = int(input())
A = list(map(int, input().split()))
curr_set = set(A)
ans = 0
for i, val in enumerate(A):
    curr_set.remove(val)
    if not curr_set:
        curr_set.add(val)
        continue
    for j in range(1, int(sqrt(val)) + 1):
        if (val % j == 0 and j in curr_set) or val / j in curr_set:
            break
    else:
        ans += 1
    curr_set.add(val)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

N = int(input())
#print(N)

A = input().split()
L = [int(b.strip()) for b in A]  

#print(L)

count = 0
for i in range(N):
  for j in range(N):
    if L[i] > L[j] and L[i] % L[j] == 0:
      count += 1
      break

print(count)

Submission status: Wrong Answer

Solution code:
def iput(): return int(input())
def mput(): return map(int, input().split())
def lput(): return list(map(int, input().split()))

def solve():
    n = iput()
    a = lput()
    a.sort()
    ans = 0
    for i in range(1, n):
        if a[0] % a[i] == 0:
            ans += 1
            break
    for i in range(n):
        for j in range(0, i):
            if a[i] % a[j] == 0:
                ans += 1
                break
    print(n - ans)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
results = []

while(A):
  a = A.pop(0)
  if a in A:
    A = [i for i in A if i!=a]
  else:
    results.append(a)
  A = [i for i in A if i%a!=0]
  #print(a, a*2, ([0]+A)[-1])
  if a*2 > ([0]+A)[-1]:
    results.extend(A)
    break
print(len(results))

Submission status: Wrong Answer

Solution code:
n = int(input())
arr = list(map(int, input().split()))
arr.sort()
c = 0
ans = 0
while c < n:
  flag = True
  for a in arr[:c]:
    if arr[c] % a == 0:
      flag = False
  if flag:
    ans += 1
  c += 1
print(ans)

Submission status: Wrong Answer

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

import collections

A_count = collections.Counter(A)
A_list = sorted(list(A_count.keys()), reverse=True)

count = 0

for i in range(len(A_list)):
    for j in range(i+1, len(A_list)):
        if A_list[i] % A_list[j] == 0:
            count += A_count[A_list[i]]
            break
if len(A_list) == 1:
    print(0)
else:
    print(N-count)

Submission status: Wrong Answer

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

setA = set(A)
result = 0

if N == 1:
    print(0)
else:
    for i in range(N):
        tmp = A[i]
        A[i] = 0
        setA = set(A)
        A[i] = tmp
        if 1 in setA:
            continue

        for a in setA:
            if a == 0:
                continue
            if A[i] % a == 0 or A[i] <= a:
                break
        else:
            result += 1

    print(result)

Submission status: Wrong Answer

Solution code:
n = input()
A = list(map(int, input().split()))
count = 0
count2 = 0

for a in A:
  for b in A:
    if a % b  == 0:
      count += 1
  if count == 1:
    count2 += 1
    
print(count2)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int,input().split()))
i = 0
ans = 0 
A.sort()
A.reverse()
if A[n-1] == 1:
    if A[n-2] != 1:
        print(1)
        exit()
    else:
        print(0)
        exit()
while i <= n-1:
    for j in range(i+1,n):
        if A[i] % A[j] == 0:
            break
        elif A[i] % A[j] != 0 and j == n - 1:
            ans = ans + 1
    i = i + 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の呼び出し制限

N = int(input())
An = [int(_) for _ in input().split()]
An.sort()

old_val = 0
ans = 0
same_flag = False
# 割り切れるものの数を数える
def dfs(An):
    global ans, old_val, same_flag
    if(len(An) == 0):
        return
    val = An.pop(-1)
    # 同じ数に対してのループの場合
    if(val == old_val):
        same_flag = True
    if((same_flag == True) and (val != old_val or len(An) == 1)):
        ans += 1
        same_flag = False
    for i in An:
        # 割り切れる場合はansに数を足して今のループを抜ける
        if(val % i == 0):
            ans += 1
            break
    old_val = val
    # どの数でも割り切れなかった場合は一度抜ける
    dfs(An)

dfs(An)
print(N - ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=sorted(map(int,input().split()))
prime=[]
count=0
for a in A:
    if all([a%i for i in range(2,int(a**.5)+1)]):
        count+=1
        prime.append(a)
for i in A:
    if i not in prime:
        for j in A:
            if i!=j and i%j==0:
                break
        else:
            count+=1
twice=0
if len(A)!=len(set(A)):
    twice=len(A)-len(set(A))+1
print(count-twice)
#print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
al = [int(i) for i in input().split()]  
al.sort()
ma = al[-1]
from collections import Counter
c = Counter(al)

if n == 1:
  print(0)
else:
  sn = set()
  total = 0
  l = len(al)
  for num in al:
    if num in sn:
      continue
    if c[num] == 1:
      total += 1
    tmp = num
    while tmp <= ma:
      sn.add(tmp)
      tmp += num
  print(total)

Submission status: Wrong Answer

Solution code:
import math

def isPrime(n):
  if n == 1:
    return False
  for k in range(2, int(math.sqrt(n)) + 1):
    if n % k == 0:
      return False
  return True

def isDiv(x, y):
  if x % y == 0:
    return True
  else:
    return False

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

if A[0] == 1:
  print(N - A.count(1))
  exit()

for i in range(N):
  x = A[i]
  if isPrime(x):
    if i - 1 >= 0:
      y = A[i - 1]
      if isDiv(x, y):
        cnt -= 1
        continue
    if i + 1 < N:
      y = A[i + 1]
      if isDiv(x, y):
        cnt -= 1
        continue
    continue
  for j in range(N):
    if i == j:
      continue

    y = A[j]
    if x < y:
      break
    if isDiv(x, y):
      cnt -= 1
      break
print(cnt)

Submission status: Wrong Answer

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

c_set = set()
for i in A:
  if i > 1000:
    break
  else:
    #room of improvement
    c_set.add(i)

ans = 0
d = 0
for i in range(N):
  f = True
  for j in c_set:
    if A[i] != j and A[i] % j == 0:
      f = False
      break
  if f:
    ans += 1
    if i < N - 1 and A[i] == A[i+1] or i > 0 and A[i] == A[i-1]:
      d += 1
print(ans - d)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
from collections import Counter

input = sys.stdin.readline


def S():
    return input().rstrip()


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


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


n = I()
al = list(MI())

al.sort()

f = set()
count = Counter(al)
for k, v in count.items():
    if v > 1:
        f.add(k)

half = al[n - 1] / 2

ans = np.array(al)
c = 0
while len(ans) != 0:
    d = ans[0]
    if d in f:
        ans = ans[ans % d != 0]
        continue
    ans = ans[ans % d != 0]
    c += 1
    if d > half:
        break

print(c + len(ans))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(i) for i in input().split(' ')]

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

divisors_list = {}
for i in range(1,1000001):
  divisors_list[i] = []

for k,i in enumerate(A):
  for j in make_divisors(i):
    divisors_list[j].append(k)

pass_li = {}
for i in range(N):
  pass_li[i] = 1

for i in range(N):
  tmp = pass_li[i]
  for j in divisors_list[A[i]]:
    pass_li[j] = 0
  pass_li[i] = tmp 
  
  
print(sum(pass_li.values()))

Submission status: Wrong Answer

Solution code:
from sys import stdin, setrecursionlimit
from collections import deque


def main():
    input = stdin.buffer.readline
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()

    q = deque(a)
    ans = 0

    while q:
        a = q.popleft()
        for _ in range(len(q)):
            b = q.popleft()
            if b % a != 0:
                q.append(b)
            elif a == b:
                break
        else:
            ans += 1
    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

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(i):
    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:
n = int(input())
li = list(map(int,input().split()))
li.sort()
dp = [1]*n
done = [0]*n

for i in range(n):
    if done[i]!=1:
        continue
    for j in range(i+1,n):
        if done[j]!=0:
            continue
        elif li[j]%li[i]==0:
            done[j]=1
            dp[j]=0
            if li[j]==li[i]:
                done[i]=1
                dp[i]=0

            
print(sum(dp))

Submission status: Wrong Answer

Solution code:
import collections

n = int(input())
p = list(map(int,input().split()))
p.sort(reverse=True)
count=0
a = collections.Counter(p)
if len(a) >1:
    count +=1
for i in range(len(p)):
    if a[p[i]]>1:
        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:
def resolve():
    n = int(input())
    A = list(map(int, input().split()))
    if len(set(A)) == 1:
        print(0)
        return

    ans = 0
    while len(A) > 0:
        a = A.pop()
        ans += 1
        B = list(map(lambda x: x % a, A))
        A = [i for i in range(len(A)) if B[i] != 0]
    print(ans - 1)

resolve()

Submission status: Wrong Answer

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

A = list(set(A))

A.sort()

#print(A)

flag = 0

for i in range(1, len(A)):
  list=[]
  for p in range(1, len(A)):
    if A[p] % A[0] == 0:
      list.append(A[p])
  for p in range(len(list)):
    A.remove(list[p])
  flag += 1
  del A[0]
  if len(A) == 1:
    flag += 1
    break
  if len(A) == 0:
    break
  #print(A)
    
print(flag)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
b = [False]*n
a.sort()
z = 0
for i,v in enumerate(a):
    if b[i]:
        continue
    for j in range(i+1,n):
        if a[j] == v:
            if b[i] == False:
                z += 1
            b[i] = True
            b[j] = True
            z += 1
        elif a[j] > a[-1]//v * v:
            break
        elif a[j] % v == 0:
            b[j] = True
            z += 1
print(n-z)

Submission status: Wrong Answer

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

A.sort()
ans = 0

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)

  if temp != 1:
    arr.append(temp)

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

  return set(arr)
  
yakusu = []

for i in range(N):
  yakusu.append(factorization(A[i]))
  
subset_yakusu = yakusu[0]

for i in range(1, N, 1):
  if A[i-1] == A[i]:
  	pass
  else:
  	#print(len(subset_yakusu & yakusu[i]), len(yakusu[i]))
  	#print(subset_yakusu, yakusu[i])
  	if (len(subset_yakusu & yakusu[i]) < len(yakusu[i])) and (subset_yakusu & yakusu[i] > yakusu[i]):
  	  ans += 1
  	  subset_yakusu = subset_yakusu | yakusu[i]
  	else:
  	  subset_yakusu = subset_yakusu | yakusu[i]
  	  for j in range(i):
  	  	if A[i] % A[j] == 0:
  	  	  break
  	  else:
  	  	ans += 1
else:
  if N != 1:
    if A[0] != A[1]:
      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]

from collections import deque

N = int(input())
A = list(map(int,input().split()))
if len(set(A)) == 1:
    print(0)
else:
    counter = 0
    A.sort()
    d = deque(A)
    for i in range(len(d)):
        p = d.popleft()
        divs = make_divisors(p)
        if set(divs) & set(d) == set():
            counter += 1
        d.append(p)
    print(counter)

Submission status: Wrong Answer

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

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

A = sorted(A)

def yakusu(x):
  if x==1:
    return []
  result = [1]
  y = 2
  while y**2<=x:
    if x%y==0:
      result.append(y)
      result.append(x//y)
    y += 1
  return result

count = N
setA = set()

for i in range(N):
  a = A[i]
  if i>0 and a==A[i-1]:
    count -= 1
    continue
  if i<N-1 and a==A[i+1]:
    count -= 1
    continue
  setA.add(a)
  y = 1
  while y**2<=a:
    if a%y==0:
      if y!=a and y in setA:
        count -= 1
        break
      if a//y!=a and a//y in setA:
        count -= 1
        break
    y += 1

print(count)

Submission status: Wrong Answer

Solution code:
def main():
  n=int(input())
  a=sorted(map(int,input().split()))
  tf=[1]*n
  n=n-1
#r=[]
#print(n)
#print(a)
  #notdiv=True
  #firstyn=0
  for i in range(n,-1,-1):
  #print(i)
  #notdiv=True
    if tf[i] ==0:
      continue
    for j in range(i):
    #print(a[j])
      if a[i]%a[j] == 0:
        tf[i]=0
        if a[i]==a[j]:
          tf[j]=0
        break
  if n==0:
    print(1)
    exit()
  if a[0] % a[1]==0:
    print(sum(tf)-1)
  else:
    print(sum(tf))
main()

Submission status: Wrong Answer

Solution code:
import math
from collections import Counter

upper_bound = 200001

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

dup = [key for key, value in Counter(nums).items() if value >= 2]

out = set()
for d in dup:
	if d not in out:
		out = out | set([d * i for i in range(1, 2 + upper_bound // d)if i not in out])

nums = sorted([x for x in nums if x not in dup])

cnt = 0
for x in nums:
	if x not in out:
		cnt += 1
		out = out | set([x * i for i in range(1, 2 + upper_bound // x) if i not in out])

print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())

A_list = [int(n) for n in input().split()]

import numpy as np

A_array = np.array(A_list)
sort_A = np.sort(A_array)

r_list = list()

for n in range(len(sort_A) - 1):
    for m in range(n+1):
        r_list.append(sort_A[n + 1] % sort_A[m] == 0)

r_array = np.array(r_list)        
        
print(r_array.sum())

Submission status: Wrong Answer

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

setA = set(A)
result = 0

if N == 1:
    print(0)
else:
    for i in range(N):
        tmp = A[i]
        A[i] = 0
        setA = set(A)
        A[i] = tmp
        if 1 in setA:
            continue

        print(setA)
        for a in setA:
            if a == 0:
                continue
            if A[i] % a == 0 or A[i] <= a:
                break
        else:
            result += 1

    print(result)

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import defaultdict

input()
A = np.fromstring(input(), int, sep=' ')

counter = defaultdict(int)
for x in A:
    counter[x] += 1

A = np.array(list(set(A)))
A.sort()

count = 0
waru = set()
for i, x in enumerate(A):
    flag = True
    if counter[x] > 1:
        waru.add(x)
        continue
    for v in waru: 
        if x % v == 0:
            flag = False
            break

    if x <= 10**3:
        waru.add(x)
    if flag:
        count += 1

print(count)

Submission status: Wrong Answer

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

#################################################
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
##################################################
def is_prime(n):
    if n == 1:
        return False
    elif n == 2:
        return True
    else:
        if n % 2 != 0:
            for i in range(3,int(math.sqrt(n))+1,2):
                if n % i == 0:
                    return False
                else:
                    pass
            return True
        else:
            return False
#################################################

cnt = 0
for j in range(n):
    x = a[j]
    if is_prime(x) and a.count(x)==1:
        cnt += 1
        continue

    f = 1
    div = make_divisors(x)
    for k in range(len(div)):
        if k != len(div)-1:
            if div[k] not in a:
                pass
            else:
                f = 0
                break
        else:
            if a.count(div[k]) == 1:
                pass
            else:
                f = 0
    if f:
        cnt += 1

print(cnt)

Submission status: Wrong Answer

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