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()))
"""
ans = 0
m = []
for i in range(n):
    cnt = 0
    for j in range(n):
        if a[i]%a[j] != 0:
            if i != j:
                cnt += 1

            else:
                break
    if cnt == n-1:
        ans += 1
        m.append(i)
print(ans, m)
"""
ans = []

for i in range(n):
    #print(ans)
    flag = True
    for j in range(len(ans)):
        try:
            if ans[j] == a[i]:
                ans.pop(j)
                flag = False
            elif ans[j]%a[i] == 0:
                ans.pop(j)
                if not a[i] in ans:
                    ans.append(a[i])
                flag = False
            elif a[i]%ans[j] == 0:
                flag = False
        except :
            pass
    if flag:
        ans.append(a[i])

print(len(ans))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
multi = [x for x in set(a) if a.count(x) > 1]
a = list(set(a))
ans = 0
dec = 0
i = 0
while i < len(a):
    if a[i] in multi:
        dec += 1
    after = list(map(lambda x:x%a[i],a))
    after[i] += 1
    for j in range(after.count(0)):
        k = after.index(0)
        a.pop(k)
    i += 1
ans = len(a) - dec
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

n = int(input())
l = list(map(int, input().split()))
c = Counter(l)
s_b = set(range(n))
res = 0
for i in range(n):
    if i in s_b:
        v = l[i]
        if c[v] > 1:
            res += 0
        else:
            res += 1
        s_b.remove(i)
        l_r = []
        for j in s_b:
            if l[j]%v==0:
                l_r.append(j)
        for j in l_r:
            s_b.remove(j)
print(res)

Submission status: Wrong Answer

Solution code:
from collections import deque
n=int(input())
aaa=list(map(int,input().split()))
aaa.sort()
ko=0
if [aaa[0]==aaa[i] for i in range(n)]==[True]*n:
  ko=1
  
aa=deque(aaa)
count=0

while aa:
    a=aa.popleft()
    if len(aa)!=0:
        b=aa.popleft()
    else:
      b=float("inf")
    if a!=b:
        count+=1
    if b!=float("inf"):
      aa.appendleft(b)
    k=len(aa)
    co=0
    while co!=k:
      t=aa.popleft()
      co+=1
      if t%a!=0:
        aa.append(t)
        
if ko==0:
  print(count)
else:
  print(0)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = sorted(a,reverse = True)
judge = [True] * n

for i in range(n):
    for j in range(i+1,n):
        if (b[i]%b[j] == 0):
            judge[i] = False
            break

print(judge.count(True))

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:
    while True:
        x = A[0]
        ans += 1
        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()

        #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()
for i in range(len(A)-1):
    cnt = 0
    if A[i] != 0:
        for j in range(i+1,len(A)):
            if A[j] == A[i]:
                A[j] = 0
                cnt +=1
            elif A[j] % A[i] == 0:
                A[j] = 0
    if cnt != 0:
        A[i] = 0
print(len(set(A))-1)

Submission status: Wrong Answer

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

no_list = [False] * N

for i in range(N):
  if no_list[i]:
    continue
  for j in range(i+1, N):
    if As[i] == As[j]:
      no_list[i] = True
      no_list[j] = True
      break
    elif As[i] % As[j] == 0:
      no_list[i] = True
      break
    elif As[j] % As[i] == 0:
      no_list[j] = True

print(N-sum(no_list))

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
A = sorted([int(x) for x in input().split()])
if A[0] == 1:
    if N == 1:
        print(1)
        exit()
    elif A[1] == 1:
        print(0)
        exit()
    print(1)
    exit()
cA = Counter(A)

cand_odd = set()
cand_even = set()
ans = 0
for a, val in cA.items():
    if (len(cand_odd) != 0 or len(cand_even) != 0) and val == 1:
        if a % 2 == 0:
            for t in cand_even:
                if a % t == 0:
                    break
            else:
                #print(a)
                if a % 2 != 0:
                    cand_odd.add(a)
                    ans += 1
                else:
                    cand_even.add(a)
                    ans += 1
        else:
            for t in cand_odd:
                if a % t == 0:
                    break
            else:
                #print(a)
                if a % 2 != 0:
                    cand_odd.add(a)
                    ans += 1
                else:
                    cand_even.add(a)
                    ans += 1
    elif val == 1:
        if a % 2 != 0:
            cand_odd.add(a)
            ans += 1
        else:
            cand_even.add(a)
            ans += 1
    else:
        continue
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int, input().split()))
A=sorted(A)
x=N
if A[0]==1:
    print(0)
    exit(0)

for i in range(1,N):
    if A.count(A[i])>1:
        x-=1
        continue
    for j in range(max(i-1,0)):
        if A[i]%A[j]==0:
            x-=1
            break
        if A[i]//A[j]+1<=A[j]:
            break
print(x)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
ans = set()
for i in range(1, n+1):
    check = 0

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

    if check != 0:
        ans.add(i)
                
print(len(ans))

Submission status: Wrong Answer

Solution code:
from collections import Counter
from numba import jit

n = int(input().strip())
L = list(map(int, input().strip().split()))
seen = Counter()
ans=0

for x in L:
    seen[x]+=1
@jit
def loop():
    ans=0
    for x in L:
        if seen[x]>1 or x!=1 and 1 in seen:
            continue
    
        tmp=2
        while tmp**2<=x:
            if x%tmp and (tmp in seen or x/tmp in seen):
                break
            tmp+=1
        else:
            ans+=1
    return ans
print(loop())

Submission status: Wrong Answer

Solution code:
# 幅優先探索（行きがけ）
import collections
import sys
import math
import copy
import collections


def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())


def main():
    N = I()
    AArry = LI()
    c = 0
    count_dict = collections.Counter(AArry)
    for k, v in count_dict.items():
        if v > 1:
            c += 1
    AArry = list(set(AArry))
    AArry.sort()
    a = len(AArry)

    b = len(AArry)
    count = a-b+c

    while AArry:
        l1 = len(AArry)
        a = AArry.pop(0)
        if len(AArry) == 0:
            break
        flag = 0
        AArry = [e for e in AArry if e % a == 0]
        l2 = len(AArry)
        count += (l1-l2)

    print(N-count)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())))
ans = 0
chk = 0
while len(a) > 0:
    if len(a) == 1:
        ans += 1
        break
    a0 = a[0]
    if a0 in a[1:-1]:
        ans -= 1
    l = [i for i in a if i%a0 != 0]
    ans += 1
    a = l

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率

def input(): return sys.stdin.readline()[:-1]
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    A = list(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    #A=[i+1 for i in range(1,200000)]
    A.sort()
    ma=A[-1]
    l=[0]*(ma+10)
    
    count=0
    pa=0
    f=0
    for a in A:
        if pa==a:
            if f==1:
                count-=1
            f=0
        elif l[a]==0:
            count+=1
            f=1
            i=a
            while i<ma+10:
                l[i]=1
                i+=a
        pa=a
    print(count)

    #print(l)
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

from math import sqrt
from collections import Counter

n = int(input())
a = list(map(int,input().split()))
s = Counter(a)
a = sorted(s)
if s[1]==2:
    ans = 0
elif s[1]==1:
    ans = 1
else:
    ans = 0
    for i in range(len(a)):
        if s[a[i]]>1:
            continue
        j = 2
        sq = sqrt(a[i])
        while j<=sq+1:    
            if a[i]%j==0 and (j in s or a[i]//j in s):
                break
            j+=1
        else:
            ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from math import sqrt, gcd, ceil, log
from bisect import bisect
from collections import defaultdict, Counter
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))

# sys.setrecursionlimit(10**6)



def solve():
	n = int(input()); arr= Counter(read())
	if n == 1:
		print(0)
		exit()
	lis = sorted(arr.keys())
	# print(lis)
	ans = 0
	for i in range(len(lis)):
		
		if arr[lis[i]] == 0:
			pass
		elif arr[lis[i]] > 1:
			arr[lis[i]] = 0
		else:
			ans += 1
			for j in range(i+1, len(lis)):
				if lis[j]%lis[i] == 0:
					arr[lis[j]] = 0
	print(ans)



	# arr.sort()
	# k = 0
	# if arr[0] == arr[1]:
	# 	k = 1
	# 	while k < n and arr[k] == arr[0]:
	# 		arr[k] = 0
	# 		k += 1
	# 	arr[0] = 0
	# ans = 0
	# # print(arr)
	# for i in range(k, n):
	# 	if arr[i]:
	# 		ans += 1
	# 		for j in range(i+1, n):
	# 			if arr[j]%arr[i] == 0:
	# 				arr[j] = 0
	# print(ans)








if __name__ == "__main__":
	solve()

Submission status: Wrong Answer

Solution code:
from decimal import Decimal
from collections import Counter

N = int(input())
A = [int(_) for _ in input().split()]
max_a = max(A)
min_a = min(A)
counter_A = Counter(A)
set_A = set([k for k, c in counter_A.items() if c == 1])

for a in A:
  if a not in set_A:
    continue
  i = 2
  while True:
    num = a * i
    if num > max_a:
      break
    if num in set_A:
      set_A.remove(num)
    i += 1

print(len(set_A))

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
    A.sort()

    ans = 0
    while len(A) > 0:
        a = A.pop(0)
        ans += 1
        A = [i for i in A if i % a != 0]

    print(ans)

resolve()

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort()
B=[]
for i in range(N-1):
    if A[i]==A[i+1]:
        B.append(A[i])
L=len(A)
C=[1 for i in range(L)]
for i in range(L):
    if i<len(A):
        j=i+1
        while j<=len(A)-1:
            if A[j]%A[i]==0:
                C[j]=0
            j+=1
print(sum(C)-len(set(B)))

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]
new_list=[]
for i in range(N):
  for j in range(N):
    if i!=j and p[i]>p[j] and p[i] % p[j]==0:
      new_list.append(p[i])
      break
check = set(p) ^ set(new_list)
print(int(len(check)))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
count = 0
unhit = 0
xcount = 0
s = a[0]
for i in range(n):

    for j in range(n):
        if a[i]%a[j]==0:
            if a[i]!=a[j]:
                unhit = 1

    if unhit==0:
        count = count + 1
    unhit = 0

    if a[i] == s:
        xcount = xcount +1

if xcount == n:
    count = 0
print(count)

Submission status: Wrong Answer

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

cnt = 0

for ai in a_s:
    not_same = [ aj for aj in a_s if aj != ai ]
    if len(not_same) == 0:
        continue

    cnt2 = 0
    for aj in not_same:
        if ai % aj != 0:
            cnt2 += 1
    if cnt2 == len(not_same):
        cnt += 1

print(cnt)

Submission status: Wrong Answer

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

A.sort()

count = 0

for i in range(N):
    tmp = 1
    for j in range(i + 1):
        if i != j:
            if A[i] % A[j] == 0:
                tmp = 0
                break
            elif A[i] == A[j]:
                if len(A) <= i + 2:
                    if A[i] % A[j + 1] == 0:
                        tmp = 0
                        break


    if tmp == 1:
        count += 1


print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
ans = [0]*(10**6+1)
mul = set()
for i in range(N):
	if ans[A[i]] == 0:
		ans[A[i]] = 1
		p = A[i]*2
		while p <= 10**6:
			ans[p] = -1
			p += A[i]
	elif ans[A[i]] == 1:
		mul.add(A[i])

q = 0	
for i in range(10**6+1):
	if ans[i] == 1:
		q += 1
print(q-len(mul))

Submission status: Wrong Answer

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

A.sort()

ans_list=[]
for i in range(N):
  for j in range(i+1,N):
    if A[i]<math.sqrt(A[j]):
      temp=math.gcd(A[i],A[j])
      if A[i]==temp:
        ans_list.append(j)  
    elif A[i]==A[j]:
      ans_list.append(i)
      ans_list.append(j)
    else:
      break

Submission status: Wrong Answer

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

import bisect

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]



cnt=0
for i in range(n):
    arr=make_divisors(a[i])

    flg=0
    for j in range(len(arr)):
        if bisect.bisect_left(a,arr[j]) > i:
            if arr[j]==a[i]:
                flg+=1

    if flg==0:
        cnt+=1

print(cnt)

Submission status: Wrong Answer

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

res = 0
for i in range(n):
    for j in range(i):
        if a[j] * 2 > a[i]:
            break
        if a[i] % a[j] == 0:
            res += 1
            break

print(n - res)

Submission status: Wrong Answer

Solution code:
##from collections import Counter
N = int(input())
A = [int(v) for v in input().split()]

from math import sqrt,ceil
from collections import defaultdict

def eratosthenes(n):
    l = [1 for i in range(n+1)]
    l[0] = l[1] = 0
    for i in range(2, ceil(sqrt(n))):
        if l[i] == 0: continue
        for j in range(i*2, n+1, i):
            l[j] = 0
    return l

def factorization(n):
    l = set()
    for i in range(2, int(sqrt(n))+1):
        if not n % i:
            l.add(i)
            l.add(n//i)
    return l


h = defaultdict(int)

for v in A:
    h[v] += 1

if h[1] > 0:
    print(0)
    exit()

ans = 0

p = [i for i, v in enumerate(eratosthenes(10**6)) if v]

for i, v in enumerate(A):
    if h[v] > 1:
        continue
    if v in p:
        ans += 1
        continue
    y = factorization(v)
    f2 = True
    for f in y:
        if h[f] > 0:
            f2 = False
            break
    if f2:
        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 j in range(ss+1):
        item = tmp[j]
        if num%item==0:
            break
        if item*2>num:
            ss = j
#             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())
array = list(map(int, input().split()))

array = list(set(array) - set([x for x in set(array) if array.count(x) > 1]))
array.sort()

dup = []

i = 0;
for j in array:
    if(not(j in dup)):
        dup = dup + [k * j for k in range(2, int(array[-1] / j + 1))]
        i += 1
    
print(i)

Submission status: Wrong Answer

Solution code:
n = int(input())

from collections import defaultdict

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

d = defaultdict(int)

for el in a:
    d[el] += 1

count = 0

d = sorted(d.items(), reverse=True)
# wm = d[0][0]

while len(d):
    a, c = d.pop()
    if c == 1:
#         print(f'count {a=}, {c=}, {count=}, {d=}')
        count += 1
    if a == 1:
        break
#     if len(d):
#         m = d[0][0]
#     else:
#         m = a - 1
    if a * a <= 10 ** 6:
        d = [elm for elm in d if elm[0] % a]
    else:
        d = [elm for elm in d if elm[1] == 1]
        count += len(d)
        break

print(count)

Submission status: Wrong Answer

Solution code:
import numpy as np
import collections
input()

def no_Divisible(num,num_set):
    for row in num_set-{num}:
        if num%row==0:
            return 0
    return 1

count = 0
input_list = map(lambda x:int(x),input().split(" "))
koho = {key for key,value in collections.Counter(input_list).items() if value==1}
visi = set(input_list)

for num in koho:
    if no_Divisible(num,visi):
        count+=1

print(count)

Submission status: Wrong Answer

Solution code:
import random
def is_prime(q, k=5):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q & 1 == 0: return False
    d = (q - 1) >> 1
    while d & 1 == 0:
        d >>= 1
    for i in range(k):
        a = random.randint(1, q-1)
        t = d
        y = pow(a, t, q)
        while t != q-1 and y != 1 and y != q-1:
            y = pow(y, 2, q)
            t <<= 1
        if y != q-1 and t & 1 == 0:
            return False
    return True

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

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

a.sort()
#print(a)

ans = 0
div = []
if a[0] == a[1]:
    pass
else:
    ans += 1

div.append(a[0])

for i in range(1, n-1):
    if a[i] == a[i-1]:
        pass
    elif a[i] == a[i+1]:
        div.append(a[i])
    else:
        if is_prime(a[i]):
            ans += 1
            div.append(a[i])
        else:
            flg = True
            for j in div:
                if j*2 > a[i]:
                    break
                if a[i] % j == 0:
                    flg = False
                    break
            if flg:
                div.append(a[i])
                ans += 1
    #print(i, a[i], div, ans)

if a[n-1] == a[n-2]:
    pass
else:
    if is_prime(a[n-1]):
        ans += 1
    else:
        flg = True
        for j in div:
            if j*2 > a[n-1]:
                break
            if a[n-1] % j == 0:
                flg = False
                break
        if flg:
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = sorted(list(map(int, input().split())))
flag = dict()
for a in A:
    if a in flag:
        if flag[a]:
            flag[a] = False
    else:
        flag[a] = True

N = len(flag)
B = list(set(A))
for i in range(N-1):
    for j in range(i+1, N):
        if flag[B[i]] and flag[B[j]]:
            if B[j]%B[i] == 0:
                flag[B[j]] = False

print(list(flag.values()).count(True))

Submission status: Wrong Answer

Solution code:
import bisect

n = int(input())
a = list(map(int, input().split()))
a.sort()
k = len(a)
ok = [0] * k
for i in range(k):
    if ok[i] == 1:
        continue
    if i < k - 1 and a[i] == a[i + 1]:
        ok[i] = 1
    if a[i] < 2 * 10 ** 3:
        for j in range(i + 1, k):
            if a[j] % a[i] == 0:
                ok[j] = 1
    else:
        times = 1
        while a[i] * times < a[-1]:
            r = bisect.bisect_left(a, a[i] * times)
            l = bisect.bisect_left(a, a[i] * times)
            if r != l:
                for idx in range(l, r):
                    ok[idx] = 1
            times += 1
print(len([i for i in ok if i == 0]))
# print(ok)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
if len(A) == 1:
    print(1)
    quit()
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
B = []
if A[0] != A[1]:
    B.append(A[0])
for i in range(1,N-1):
    a = A[i]
    if a != A[i-1] and a != A[i+1]:
        B.append(a)
if A[-1] != A[-2]:
    B.append(A[-1])
if len(B) == 0:
    print(0)
    quit()
a = B[-1]
P = set(primes(a))
ans = []
for i in range(len(B)):
    a = B[i]
    if a in P:
        ans.append(a)
    else:
        if all([a % gen != 0 for gen in ans]) == True:
            ans.append(a)
print(len(ans))

Submission status: Wrong Answer

Solution code:
from sys import stdin
N = int(stdin.readline().rstrip())
data = list(map(int, stdin.readline().rstrip().split()))
data_sorted = sorted(data)

count =0
if len(list(set(data_sorted))) == 1:
    print(count)

else:
    for i, p in enumerate(data_sorted):
        frag = 0
        for j in range(0,i):
            if p % data_sorted[j] == 0: #わりきれたらカウントしない
                frag = 1

        if frag == 0:
            count +=1


    print(count)

Submission status: Wrong Answer

Solution code:
import bisect
import collections
import sys
input = sys.stdin.buffer.readline

def sieve(n):
    is_prime = [True for _ in range(n)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [i for i in range(1, n+1) if is_prime[i-1]]
    return table

N = int(input())
A = list(map(int, input().split()))
A.sort()
L = collections.Counter(A)
P = sieve(100)
#print(A)
ans = 0

for i in reversed(range(N)):
    a = A[i]
    if L[a] != 1:
        continue
        
    jdg = 0
    cnt = 0
    for p in P:
        if a % p == 0:
            cnt += 1
            index = bisect.bisect_right(A,a//p)
            #print(index,a)
            for k in range(index):
                if a % A[k] == 0:
                    jdg += 1
                    break
            if jdg == 0:
                ans += 1
            break
            
    if cnt == 0:
        if a % p == 0:
            index = bisect.bisect_right(A,a//100)
            #print(index,a)
            for k in range(index):
                if a % A[k] == 0:
                    jdg += 1
                    break
            if jdg == 0:
                ans += 1
            break
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import numpy as np
import math

def solve(N: int, A: "List[int]"):
    AA = sorted(A)
    ans = 0
    for i in range(N):
        a = AA[N-i-1]
        flg = False
        for j in range(i+1):
            if flg==True:
                break
            if j!=(N-i-1):
                b = AA[j]
                if a % b ==0:
                    flg = True
        if flg != True:
            ans += 1
    print(ans)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

ans = 0

for i in A:
    for j in A:
        if i ==j:
            pass
        else:
            if i % j == 0:
                ans += 1
            else:
                pass

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

def main():
    N = int(input())
    An = list(set(list(map(int, input().split()))))
    le = len(An)
    if le == 1:
        print(0)
    else:
        ok = [False] * le
        a_An = np.array(An)
        for i, a in enumerate(An):
            temp = a_An / a
            temp[i] = 0.1
            ok = ok | (temp % 1 == 0)
        print(np.count_nonzero(ok == 0))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

    ans = resolver(N, A)
    print(ans)
    
def resolver(N, A):
    A = np.array(list(set(A)))
    A = np.sort(A)[::-1]

    count = 0
    pre = None
    if A[0] == A[-1]:
        return 0
    for i, a in enumerate(A):
        #if i % 100 == 0:
        #    print(f"i={i}", end="\r")
        if np.any(a % A[i+1:] == 0):
            continue
        count += 1
        pre = a

    return count

def test():
    N = 10**5
    A = np.random.randint(1, 10**6, N)
    print("start")
    ans = resolver(N, A)
    print(ans)

if __name__ == '__main__':
    #test()
    main()

Submission status: Wrong Answer

Solution code:
def check(i, index):
    for j in range(index):
        if a[index] % a[j] == 0:
            return False
    return True


n = int(input())
b = [int(i) for i in input().split()]
a = set(b)
a = list(sorted(a))

cnt = 0

for i in range(len(a)):
    if check(a[i], i):
        cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
import bisect
import math

n = int(input())
a = [int(num) for num in input().split()]
b = [0] * 1000001
for i in range(n):
    b[a[i]] = 1
    
ans = 0

for i in range(n):
    fl = True
    for j in range(1,int(math.sqrt(a[i])) + 2):
        if a[i] % j == 0 and (b[j] > 0 or b[a[i] // j] > 0):
            fl = False
            break
    if fl:
        ans += 1
        
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import deque
import heapq
import itertools
from decimal import Decimal
import bisect
from operator import itemgetter
MAX_INT = int(10e18)
MIN_INT = -MAX_INT
mod = 1000000000+7
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

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

    return divisors

N = I()
a = IL()
a.sort()
ans = N

data = [0]*(a[-1]+1)
for i in range(N):
  if i < N-1:
    if a[i] == a[i+1]:
      ans -= 1
    else:
      yakusuu = make_divisors(a[i])
      for j in yakusuu:
        if data[j] >= 1:
          ans -= 1
          break
  else:
    yakusuu = make_divisors(a[i])
    for j in yakusuu:
      if data[j] >= 1:
        ans -= 1
        break
  data[a[i]] = True

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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