Problem:


Score : 400 points

Problem Statement

Given is a number sequence A of length N.

Find the number of integers i \left(1 \leq i \leq N\right) with the following property:

For every integer j \left(1 \leq j \leq N\right) such that i \neq j , A_j does not divide A_i.

Constraints

All values in input are integers.

1 \leq N \leq 2 \times 10^5

1 \leq A_i \leq 10^6

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answer.

Sample Input 1

5
24 11 8 3 16

Sample Output 1

3

The integers with the property are 2, 3, and 4.

Sample Input 2

4
5 5 5 5

Sample Output 2

0

Note that there can be multiple equal numbers.

Sample Input 3

10
33 18 45 28 8 19 89 86 2 4

Sample Output 3

5



Sample input:
5
24 11 8 3 16


Sample output:
3

Submission status: Wrong Answer

Solution code:
import numpy as np

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

A_sorted=np.sort(A)
result=[]
a=A_sorted[0]
while A_sorted.size>0:
    a=A_sorted[0]
    if A_sorted.size==1:
        result.append(a)
        break
    A_sorted=A_sorted[1:]
    if a in A_sorted:
        A_sorted=A_sorted[A_sorted!=a]
        continue
    result.append(a)
    A_sorted=A_sorted[A_sorted%a!=0]
print(len(result))

Submission status: Wrong Answer

Solution code:
import numpy as np

n=int(input())
a = np.array(list(map(int, input().split())))
a=np.append(0,a)
ans=0
b=np.cumsum(a)
for i in range(n):
    for j in range(n):
      if a[i]%(b[j+1]-b[j])==0 and i!=j:
          break
      if j==n-1:
          ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import math
from collections import deque
from collections import defaultdict
import itertools as it

#自作関数群
def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	if len(res)==0:
		res = [n]
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):#階乗
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):#コンビネーション
	if n<r:
		return 0
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
def combmod(n,r,mod):
	return (fact(n)/fact(n-r)*pow(fact(r),mod-2,mod))%mod
def printQueue(q):
	r=copyQueue(q)
	ans=[0]*r.qsize()
	for i in range(r.qsize()-1,-1,-1):
		ans[i] = r.get()
	print(ans)
class UnionFind():
	def __init__(self, n):
		self.n = n
		self.parents = [-1]*n

	def find(self, x): # root
		if self.parents[x]<0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self,x,y):
		x = self.find(x)
		y = self.find(y)

		if x==y:
			return

		if self.parents[x]>self.parents[y]:
			x,y = y,x

		self.parents[x]+=self.parents[y]
		self.parents[y]=x

	def size(self,x):
		return -1*self.parents[self.find(x)]

	def same(self,x,y):
		return self.find(x)==self.find(y)

	def members(self,x): # much time
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i)==root]

	def roots(self):
		return [i for i,x in enumerate(self.parents) if x<0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()} # 1~n
def bitArr(n):#ビット全探索
	x = 1
	zero = "0"*n
	ans = []
	ans.append([0]*n)
	for i in range(2**n-1):
		ans.append(list(map(lambda x:int(x),list((zero+bin(x)[2:])[-1*n:]))))
		x+=1
	return ans;
def arrsSum(a1,a2):
	for i in range(len(a1)):
		a1[i]+=a2[i]
	return a1
def maxValue(a,b,v):
	v2 = v
	for i in range(v2,-1,-1):
		for j in range(v2//a+1): #j:aの個数
			k = i-a*j
			if k%b==0:
				return i
	return -1
def copyQueue(q):
	nq = queue.Queue()
	n = q.qsize()
	for i in range(n):
		x = q.get()
		q.put(x)
		nq.put(x)
	return nq
def get_sieve_of_eratosthenes(n):
	data = [2]
	#data = [0,0,0]
	for i in range(3,n+1,2):
		data.append(i)
		data.append(0)
	for i in range(len(data)):
		interval = data[i]
		if interval!=0:
			for j in range(i+interval,n-1,interval):
				data[j] = 0
	ans = [x for x in data if x!=0]
	#ans = data[:]
	return ans

n = readInt()
a = readInts()

a.sort()

if a.count(a[0])==n:
	print(0)
	exit()

if 1 in a:
	print(1)

maxa = max(a)+1

ans = [0]*maxa
for i in a:
	ans[i] = 1



for j in a:
	if ans[j]==0:
		pass
	for i in range(j*2,10**6+1,j):
		if i>maxa-1:
			break
		ans[i] = 0

print(ans.count(1))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
 
a.sort()
b = set()
c = 0
for i, v in enumerate(a):
    flag = True
    for j in b:          
        if v % j == 0:
            flag = False
            break
        elif v / 2 <= j:
            if a[i-1] == v:
                flag = False
            break
    if flag == True:
        b.add(v)
        if i+1 >= len(a):
            c += 1
        elif a[i+1] != v:
            c += 1
     
print(c)

Submission status: Wrong Answer

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

N = int(input())
A = list(map(int, input().split()))
A = A[:N] # 一応


def calc(b, A):
    new = []
    count = 1
    for a in A:
        if a % b > 0: # bで割れなければ続投
            new.append(a)
        if b % a == 0: # bがaで割り切れてしまったら強い方に交代
            b = a
            count = 0
    # count と 新しいAを返す
    return count, new

count = 0
while len(A) > 0:
    a = A.pop(0)
    
    c, A = calc(a,A)  
    count += c

print(count)

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-2:
    for j in range(i+1,n):
        if A[i] % A[j] == 0:
            break
        elif j == n - 1:
            ans = ans + 1
    i = j + 1
if A[n-1] == A[n-2]:
    print(ans)
else:
    print(ans+1)

Submission status: Wrong Answer

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

flgs = [True] * N
for i in range(N):
    if flgs[i]:
        if As[i] < 10000:
            for j in range(i+1, N):
                if As[j] == As[i]:
                    flgs[i] = False
                    flgs[j] = False
                elif As[j] % As[i] == 0:
                    flgs[j] = False

print(flgs.count(True))

Submission status: Wrong Answer

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

an.sort()
an = deque(an)
ls = deque()
same = -1
while an:
    a = an.popleft()
    t = True
    if same == a:
      continue
    for i in ls:
        if a == i:
            ls.pop()
            same = a
            t = False
            break
        if a % i == 0:
            t = False
            break
    if t:
        ls.append(a)

print(len(ls))

Submission status: Wrong Answer

Solution code:
def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10

    N = II()
    A = LMIIS()
    A.sort()
    ans = 0
    count = defaultdict(int)
    for a in A:
        count[a] += 1
    next_A = deque()
    for a in A:
        if count[a] == 1:
            next_A.append(a)
    A = list(next_A)
    if len(A) == 0:
        print(0)
        return
    if A[0] == 1:
        print(1)
        return


    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]




    F = deque()
    for a in A:
        F.append(make_divisors(a))
    ans = 0
    Not_Divisible = defaultdict(bool)
    for f in F:
        for d in f:
            if Not_Divisible[d]:
                break
        else:
            Not_Divisible[f[-1]] = True
            ans += 1
    print(ans)

                



    
main()

Submission status: Wrong Answer

Solution code:
import copy

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

a = sorted(a)
b = copy.deepcopy(a)

max_a = a[n-1]
min_a = a[0]

cnt = 0

for i in a:
  tmp = 0
  
  for j in b:
    if i == j and tmp == 1:
      cnt += 1
      break
    elif i == j and tmp == 0:
      tmp += 1
      continue
    elif i / 2 < j:
      break
    elif i % j == 0:
      cnt += 1
      b.remove(i)
      break

print(n - cnt)

Submission status: Wrong Answer

Solution code:
import copy

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

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

ans = 0
count = 0
while count < len(a):
    x = a[count]
    comb = factorization(x)
    a2 = copy.deepcopy(a)
    a2.remove(x)
    count += 1
    lst = []
    for i in comb:
        for j in range(i[1]):
            lst.append(i[0]**(j+1))
    count2 = 0
    for i in lst:
        if i not in a2:
            count2 += 1
    if count2 == len(lst):
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(_) for _ in input().split(' ')]

if n > 1:

    c = {}
    for i in a:
        if i in c:
            c[i] += 1
        else:
            c[i] = 1

    a = []
    for i in c.keys():
        if c[i] == 1:
            a.append(i)
    a.sort()

    b = set()

    answer = 0
    for i in a:
        d = set()
        for j in range(1, i):
            if i % j == 0:
                d.add(j)
                d.add(i // j)
            if j * j >= i:
                break

        f = True
        for j in d:
            if j in b:
                f = False
        if f:
            answer += 1
        b.add(i)

    print(answer)
else:
    print(0)

Submission status: Wrong Answer

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

arr2 = []

for i in range(2, n):
    for j in range(2, n):
        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:
N = int(input())
A = [int(x) for x in input().split()]

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

A = list(set(A))

A.sort()

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])
  if A[0] not in B:
    flag += 1
  del A[0]
  if len(A) == 1:
    flag += 1
    break
  if len(A) == 0:
    break
    
print(flag)

Submission status: Wrong Answer

Solution code:
N=int(input())
a=map(int,input().split())
A=sorted(a)
answers=[A[0]]
if N==1:
    print(1)
else:
     del A[0]
     for a in A:
         number=0
         if a  in set(answers):
             answers.remove(a)
         else:
             for b in answers:
                 if a%b==0:
                     number=1
                     break
             if number==0:
                 answers.append(a)
     print(len(answers))

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

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

# エラトステネスの篩っぽく処理
ans_list = []
ans = 0

# ダブリを省くために先に数える
c = Counter(search_list)
doubly = [x for x in c.values() if c[x] == 1]

tmp = min(search_list)

while tmp <= max(search_list)/2:
    if tmp in doubly:
        ans_list.append(tmp)
    search_list = [i for i in search_list if i % tmp != 0]
    if len(search_list) == 0:
        break
    else:
        tmp = min(search_list)

ans = len(ans_list) + len(search_list)
print(ans)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
from collections import Counter
a = list(map(int, input().split()))
c = Counter(a)
s = set()
for k,v in c.items():
    if v>=2:
        s.add(k)
        
a.sort()
# tmp = set()
# from bisect import bisect_left
# while True:
#     v = a[0]
#     if v*2>a[-1]:
#         for item in a:
#             tmp.add(item)
#         break
#     tmp.add(v)
# #     na = []
# #     ii = bisect_left(a, v*2)
# #     for 
#     a = [item for item in a if item%v!=0]
#     if not a:
#         break

tmp = [a[0]]
ss = 0
for i in range(1, n):
    num = a[i]
#     for i in range(len(tmp)-1, -1, -1):
    for i in range(ss+1):
        item = tmp[i]
        if num%item==0:
            break
        if item*2>num:
            ss = i
#             print(item, num, ss)
            tmp.append(num)
            break
    else:
        tmp.append(num)

tmp = set(tmp) - s
print(len(tmp))

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int,input().split()))
A.sort(reverse = True)
cnt = 0
for i in range(n):
    for j in range(n):
        if i >= j:
            continue
        tmp = A[i]%A[j]
        if tmp == 0:
            cnt += 1
            break

if A[n-1] == A[n-2]:
    cnt += 1
print(n-cnt)

Submission status: Wrong Answer

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

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

ans = [True] * N
for i in range(N):
    for j in range(i+1, N):
        if not A[j]:
            continue
        if A[j] % A[i] == 0:
            ans[j] = False

if A[0] == A[1]:
    ans[0] = False

c = 0
for a in ans:
    if a:
        c += 1
print(c)

Submission status: Wrong Answer

Solution code:
import sys

N = int(input())
A = list(map(int, sys.stdin.readline()[:-1].split()))

A.sort()
if len(A) == 1:
    print(1)
    sys.exit(0)
elif A[0] == A[-1]:
    print(0)
    sys.exit(0)
elif A[0] == 1:
    print(1)
    sys.exit(0)


d =[]

for i in range(len(A)):
    flag = True
    for j in d:
        if A[i] % j == 0:
            flag = False
            break
    if flag:
        d.append(A[i])

print(len(d))

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
A = list(set(map(int,input().split())))
A.sort()
ans = 0
a = len(A)
if a == 1:
    print(0)
else:
    ans = 1
    while True:
        x = A[0]
        for i in range(len(A)):
            if A[i] % x == 0:
                A[i] = x
        #print(A)
        A = sorted(list(set(A)))[1:]
        #print(A,ans)
        if len(A) < 2:
            #print("lrn1")
            ans += 1
            print(ans)
            sys.exit()
            break
        elif len(A) < 3:
            if A[1] % A[0] == 0:
                print(ans)
                sys.exit()
            else:
                ans += 2
                print(ans)
                sys.exit()
        ans += 1
        #print("last",A)
    #print(A,ans-1,99999)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort()
ans=N
for i in range(N-1):
  if A[i]==A[i+1]:
    ans-=1
  else:  
    for k in range(0,i):
      if i!=1 and A[i]==A[i-1]:
        ans-=1
        break
      if A[i]%A[k]==0:
        ans-=1
        break
      if A[k]>(A[i])**(1/2)+2:
        break
for i in range(N-1):
  if A[N-1]%A[i]==0:
    ans-=1
    break
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
B = set(A)
for i in B:
    if A.count(i) > 1: B = B - {i}
multiplier = 2
for i in B:
    while i*multiplier <= max(B):
        B = B - {i*multiplier}
        multiplier += 1
    multiplier = 2
print(len(B))

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import Counter
n=int(input())
a=sorted(list(map(int,input().split())))
ac=Counter(a)
ans=0
for i,j in enumerate(a):
    if i==0:
        ans+=1
        continue
    if ac[j]>=2:
        continue
    A=np.array(a[:i])
    if np.count_nonzero(j%A==0)==0:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import math
import numpy as np
#import torch
#import torch.nn as nn
#import matplotlib.pyplot as plt
#from decimal import Decimal
#import itertools


N=int(input())
#N,K = map(int,input().split())
#B,W = map(int,input().split())
#T=int(input())
A = list(map(int,input().split()))
#S=str(input())
#A=[p for p in range(2*10**5)]
n=len(A)
A=sorted(A,reverse=True)
A=np.asarray(A)

#print(A)
c=0
for i in range(n-1):
    if A[i]==A[i+1]:
        continue
    #print(i)
    p=np.where(A<int(A[i]/2))
    p=np.append(p,n)
    I=p[0]
    #print(I)


#    print(A[i],I)
    for j in range(I,n):
        #print(' ',j)

        #print(A[i],A[j])
        if A[i]%A[j]==0:
            c-=1
            break
    c+=1

print(c)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = input().split()
A = [int(i) for i in A]
A.sort()
count=0
pak = []
for b, a in enumerate(A):
    for i in range(N):
        if A[i] % a ==0 and A[i] != a:
            count+=1
            A[i] = a
if count == 0:
    print(0)
else:
    print(N-count)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

m=max(A)
ans_list=A


for i in range(1,m+1):
    if i in A:
        ans_list=list(filter(lambda x:x%i!=0 or x==i,ans_list))
        ans_list=set(ans_list)
        # print(ans_list)

print(len(ans_list))

Submission status: Wrong Answer

Solution code:
num = int(input())
A = [int(i) for i in input().split(" ")]
A = sorted(A)

diff = 0
i = 0
while i < num:
  if i == 0 or A[i] != A[i-1]:
    if i+1 < num and A[i]==A[i+1]:
      diff += 1
  for j in range(i):
    if A[i] % A[j] == 0:
      A.pop(i)
      num -= 1
      i -= 1
      break
  i += 1

print(num-diff)

Submission status: Wrong Answer

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

def q(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
count = 0
if apple.count(1) >= 2:
    count = 0
elif apple.count(1) == 1:
    count = 1
elif len(set(apple)) == 1:
    count = 0
else:
    for i in apple:
        if len(q(i)) == 1:
            if apple.count(i) >= 2:
                pass
            else:
                count += 1
        else:
            num = i
            result = [i for i in range(1, num+1) if num % i ==0]
            result = result[:-1]
            if len(set(result) & set(apple)) == 0:
                count += 1
            else:
                pass

print(count)

Submission status: Wrong Answer

Solution code:
import numpy as np

length = int(input())
As = list(map(int, input().split()))

# 1が1つでもいた場合　または
# 長さが1　または　すべて同じ数字のみの場合
# ⇒0確定
if 1 in As or len(set(As)) == 1:
    print(0)
    exit()

As.sort(reverse=True)
As = np.array(As)

out = 0
while len(As) > 0:
    # 末尾(最小値)を取得してリストから削除
    e = As[-1]
    As = np.delete(As, -1)
    
    # 重複がある場合
    if e in As:
        # 割り切れたもののインデックス抽出
        tmp = np.where(As % e == 0)
        tmp_ones = np.ones(len(As), dtype=bool)
        tmp_ones[tmp] = False
        As = As[tmp_ones]
    # 重複がない場合
    else:
        out = out + 1
        # 割り切れたもののインデックス抽出
        tmp = np.where(As % e == 0)
        tmp_ones = np.ones(len(As), dtype=bool)
        tmp_ones[tmp] = False
        As = As[tmp_ones]

print(out)

Submission status: Wrong Answer

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

A_list.sort()

cnt = 0

while len(A_list)>1:
    num = A_list.pop(0)
    if num != A_list[0]:
        cnt+=1
    A_small = [x for x in A_list if x < 2*num]
    len_small = len(A_small)
#    c = collections.Counter(A_small)
    while len(A_small)>1:
        num_s = A_small.pop(0)
        if num_s != A_small[0]:
            cnt+=1
        else:
            A_small = [x for x in A_small if x!=num_s]
    if len(A_small)==1:
        cnt+=1
    A_list = A_list[len_small:]
    A_list = [x for x in A_list if x%num!=0]

if len(A_list) == 1:
    cnt+=1

print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
list_A = input().split()
int_list_A = [int(x) for x in list_A]
answer = 0

for i in range(N):
    temp1 = int_list_A[i] 
    for j in range(N):
        if i == j:
            continue
        else:
            temp2 = int_list_A[j]
            if temp1 % temp2 == 0:
                break
            else:
                if j == (len(int_list_A) - 1):
                    answer += 1

print(answer)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left as bl
from bisect import bisect_right as br
n = int(input())
a = list(map(int, input().split()))
a.sort()
c = set(a)
b = c.copy()
for x in c:
    if (br(a,x) - bl(a,x)) >= 2:
        b.remove(x)
b = sorted(list(b))
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:
from sys import stdin
import sys

MAX_A = 1000001;
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]
A = list(set(A))
M = [False]*MAX_A
ans = 0
for a in A:
  if M[a] == False:
    if a in A_one:
    	ans+=1
    M[a::a] = [True]*(len(M[a::a]))
    
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            for i in range(1, e+1):
                fct.append(b**i)
        b, e = b + 1, 0
    if n > 1:
        fct.append(n)
    return fct


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

A = deque(sorted(A, reverse=True))

count = 0
if N >1:
    if A[-1] == A[-2]:
        count -= 1

jud = True

for i in range(len(A)):
    C = factorize(A.popleft())
    for c in C:
        if c in A:
            jud = False
            break

    if jud:
        count += 1

    jud = True

print(count)

Submission status: Wrong Answer

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

A_sort = sorted(A, reverse=True)

cnt = 0

if N == 1:
    cnt +=1

elif A_sort[-1] != 1:
        
    if A_sort[-1] != A_sort[-2]:
        cnt += 1

    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

            
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))
    C = [x for x in set(A) if A.count(x) > 1]
    l = len(B)
    k = len(C)
    ct = 1-k
    if len(B) == len(A):
        ct = 1
    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:
from functools import reduce
from math import gcd

def lcm(A, B):
    return A * B // gcd(A, B)

#S=[33,18,45,28,8,19,89,86,2,4]
n=int(input())
S=list(map(int,input().split()))
# リストを引数にとる
val=reduce(lcm, S)
cnt=0
for i in S:
    if val%i==0:
        cnt+=1
        val//=i
print(cnt)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

def main():
    n = I()
    mylist = list(MI())
    mylist.sort(reverse = True)
    mylist = tuple(mylist)

    if mylist[n-1] in mylist[:n-1]:
        result = 0
    else:
        result = 1


    for i in range(n-1):
        temp = mylist[i]
        divide = True
        for j in range(i+1,n):
            if temp % mylist[j] == 0:
                divide = False
                break
        if divide:
            result += 1
    print(result)

main()

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

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()

half = (al[n - 1] / al[0]) + 1
ans = np.array(al)
c = 0
while len(ans) != 0:
    d = ans[0]
    if len(ans) >= 2 and d == ans[1]:
        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:
def resolve():
    import sys
    input = sys.stdin.readline
    # 整数 1 つ
    n = int(input())
    # 整数複数個
    # a, b = map(int, input().split())
    # 整数 N 個 (改行区切り)
    # N = [int(input()) for i in range(N)]
    # 整数 N 個 (スペース区切り)
    A = list(map(int, input().split()))
    # 整数 (縦 H 横 W の行列)
    # A = [list(map(int, input().split())) for i in range(H)]

    if n == 1:
        print(1)
    else:
        A.sort()
        if A[0] == 1:
            if A[1] == 1:
                print(0)
            else:
                print(1)
        elif len(list(set(A))) == 1:
            print(0)
        else:
            B = []
            for i in range(n):
                flag = True
                for x in B:
                    if A[i] % x == 0:
                        flag = False
                        break
                if flag == True:
                    B.append(A[i])
            print(len(B))

            # cnt = 0
            # for i in range(n):
            #     flag = False
            #     for j in range(n-i-1):
            #         if A[n-1-i] % A[j] == 0:
            #             flag = True
            #             break
            #     if flag == False:
            #         cnt += 1
            # print(cnt)

            # for i in range(n):
            #     lentemp = len(A)
            #     for j in range(lentemp-1-i):
            #         if A[lentemp-1-j] % A[i] == 0:
            #             del A[lentemp-1-j]
            #
            #     if i+2 >= len(A):
            #         break
            # print(len(A))

resolve()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
# print (A)
ans = 0
for i in range(N - 1, -1, -1):
    a = A[i]
    flag = True
    for j in range(i):
        if a % A[j] == 0:
            flag = False
            break
        if A[j] * 2 > a:
            break
    if i + 1 < N and A[i] == A[i + 1]:
        flag = False

    if flag:
        ans += 1

print (ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = 5
ARR = [24, 11, 8, 3, 16]
#
N = 4
ARR = [5, 5, 5, 5]

N = 10
ARR = [33, 18, 45, 28, 8, 19, 89, 86, 2, 4]

N = int(input())

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

import numpy as np


def filterNotTheSame(n, arr):
    dict = {}
    for i in range(n):
        if dict.get(arr[i]) == None:
            dict.__setitem__(arr[i], 1)
        else:
            dict.__delitem__(arr[i])

    return dict.keys()

def calculate(arr):
    arr = sorted(arr)
    arr = np.array(arr)

    result = []
    while np.sum(arr) > 0:
        start = np.argmax(arr > 0)
        startValue = arr[start]
        arr = np.where((arr % startValue) == 0, 0, arr)
        result.append(startValue)
    return result

ARR = filterNotTheSame(N,ARR)
result = calculate(ARR)

print(len(result))

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 A:
  divisors_list[i] = []

for k,i in enumerate(A):
  for j in make_divisors(i):
    if j in divisors_list.keys():
      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:
def make_divisors(n):
    lower_divisors = []
    upper_divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)

    upper_divisors.reverse()
    return lower_divisors + upper_divisors


n = int(input())
a = list(map(int,input().split()))
b = set()
add = b.add
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
    add(i)
print(cnt)

Submission status: Wrong Answer

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

b = list(c for c in a)

ans = 0

for i in a:
    for j in b:
        if i == j: continue
        elif i % j == 0:
            b.remove(i)
            break
    else: ans += 1

if len(set(a)) == 1: ans = 0
print(ans)