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:

def solve():
    memo = [1]*n
    cnt = 0
    for i in range(n):
        for j in range(2,n+1):
            #print(a[i])
#            print(a[i]%j)
            if a[i] % j == 0 and a[i] > n:
                memo[i] = 0
                #cnt += 1   
        if memo[i] == 0:
            cnt += 1

#    print(memo)
    print(cnt)

if __name__=="__main__":
    n = int(input())
    a = list(map(int, input().split()))

    solve()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N = int(input())

def divisor(n): #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

A = list(map(int, input().split()))
A.sort()
dic = defaultdict(int)
for a in A:
  dic[a] += 1
A = set(A)

for a in A:
  if a == 1:
    print(0)
    exit()
B = {}
for a in A:
  B[a] = divisor(a)

s = set()
ans = 0

for a in A:
  s = A - set([a])
  if len(s) == 0:
    continue
  if len(set(B[a]) & s) == 0:
    ans += dic[a]

print(ans)


"""E問題"""

Submission status: Wrong Answer

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

import math
def is_prime(n):
    if n == 1: return False

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

aset = set(A)
A.sort()
ans = 0
# prime = set()
hist = set()

for ix, i in enumerate(A):
    if i in hist:
        continue
    # print(is_prime(i))
    if is_prime(i):
        # 素数ならば答え+1
        # ans += 1
        # if i not in prime and i != A[ix+1]:
        if ix == 0:
                if i != A[min(ix+1, N-1)]:
                    # print(i,ix)
                    ans += 1
                    hist.add(i)

        elif ix == N-1:
                if i != A[max(0, ix-1)]:
                    # print(i,ix)
                    ans += 1
                    hist.add(i)

        else:
            if i != A[min(ix+1, N-1)] and i != A[max(0, ix-1)]:
                # print(i,ix)
                ans += 1
                hist.add(i)
    else:
        div = False
        for d in A[:ix]:
            # if d <= math.sqrt(i):
            if i%d == 0:
                div = True
                break
        
        if div == False:
            ans += 1
            # print(i, ix)
        
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
count = 0
A.sort()
c= 0
if N>1:
    if A[0]%A[1] >0:
        count+=1

for k in range(1, len(A)):
    if k<N-1:
        if A[k] == A[k+1]:
            del A[k]
            A.insert(0, 0)
            c +=1
            continue
    for j in range(c, k):
        if A[k]%A[j] ==0:
            del A[k]
            A.insert(0, 0)
            c +=1
            break
    else:
        count +=1
        #print(A[k])

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

Submission status: Wrong Answer

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


N = int(input())
A = list(map(int,input().split()))
A_set = set(A)
if len(A_set) == 1:
    print(0)
else:
    counter = 0
    for a in A_set:
        A_set.discard(a)
        if set(make_divisors(a)) & A_set == set():
            counter += 1
        A_set.add(a)
    print(counter)

Submission status: Wrong Answer

Solution code:
from collections import Counter

def main():
    N, *A = map(int, open(0).read().split())

    ctr = Counter(A)
    memo = []
    dp = set()
    ans = 0

    for a in sorted(A):
        if a == 1:
            if ctr[a] == 1:
                ans = 1
            break
 
        if ctr[a] == 1:
            for v in memo:
                if v > int(a ** 0.5):
                    if a % v != 0:
                        ans += 1
                    break
                if a % v == 0 and ((v in dp) or (a // v in dp)):
                    break
            else:
                ans += 1

        memo.append(a)
        dp.add(a)

    print(ans)

    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# Contest No.: ABC170
# Problem No.: D
# Solver:      JEMINI
# Date:        20200614

import sys
import heapq

def main():
    n = int(input())
    nums = list(map(int, sys.stdin.readline().split()))
    if n == 1:
        print(0)
        return
    nums.sort()
    #nums = list(reversed(nums))
    checkList = [True] * n

    for i in range(n - 1, -1, -1):
        if not checkList[i]:
                continue
        for j in range(0, i):
            #print(nums[i], nums[j])
            if nums[j] == nums[i]:
                for k in range(j, i + 1):
                    checkList[k] = False
                break
            if nums[i] < nums[j] * 2:
                break
            if nums[i] % nums[j] == 0:
                checkList[i] = False
                break
        #print(nums)
        #print(checkList)
    print(sum(checkList))


    
    return

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

k = 0
count = 0
flag = True
for i in range(n):
        for j in range(n):
            if a[i] > a[j]:
                k = a[i] % a[j]
                if k == 0:
                    count += 1
                    break

print(n - count)

Submission status: Wrong Answer

Solution code:
import copy
n = int(input())
li = list(map(int,input().split()))
set1 = set()
ban = set()
for i in li:
    if i in set1:
        set1.remove(i)
        ban.add(i)
    if i not in set1 and i not in ban:
        set1.add(i)
set2 = copy.copy(set1)
cnt = 0
for i in (set1):
    set2.remove(i)
    flg = False
    for j in set2:
        if flg:
            break;
        if i != j:
            if i % j == 0:
                flg = True
    if not flg:
        cnt += 1
    set2.add(i)
print(cnt)

Submission status: Wrong Answer

Solution code:
def divisor_gen(n):
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            yield i
            if i != n // i and i != 1:
                yield n // i


def resolve():
    from collections import Counter
    import sys
    input = sys.stdin.readline
    _ = int(input())
    a = list(map(int, input().split()))
    c = Counter(a)
    ans = 0
    for i in (x for x, y in c.items() if y == 1):
        for j in divisor_gen(i):
            if j in c:
                break
        else:
            ans += 1
    print(ans)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
from collections import Counter
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 and i!=1:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

n=int(input())
l=list(map(int,input().split()))
p=set(l)
cnt=0

ss=Counter(l)

for i in range(n):
    #print(set(make_divisors(l[i])))
    #print(set(make_divisors(l[i]))|p)
    pp=set(make_divisors(l[i]))
    if pp | p==pp^ p and ss[l[i]]<2:
        cnt+=1

        #print(set(make_divisors(l[i])))
        
#a=sorted(l)
#cnt2=0
#cntt=0
#for i in range(n-1):
#    if a[i]==a[i+1]:
#        if cntt==0:
#            cntt+=2
#        else:
#            cntt+=1
#    else:
#        cnt2+=cntt
#        cntt=0
#if cntt>0:
#    cnt2+=cntt
print(cnt)    
#print(cnt-cnt2)

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
a = np.array(list(map(int, input().split())))
a = np.sort(a)
ans = 0
if np.count_nonzero(a == a[0]) == n:
    print(0)
    exit()
while len(a):
    a = np.delete(a, np.where(a % a[0] == 0))
    ans += 1
print(ans)

Submission status: Wrong Answer

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

INF = float("inf")

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

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

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

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

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

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

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

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

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

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

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

def S():
    return input()

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

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

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

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

n = I()
a = RI()

b = list(set(a))

M = int( max(b)**0.5 ) + 1

a.sort()

count = 0

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

# print(count)

ans = n - count
print(ans)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy

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

ans = 0

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


# エラトステネスの篩っぽく処理
res = deepcopy(A)
ans_list = [-1 for _ in range(N)]
ind = 0

#print(res)

while -1 in ans_list[ind+1:]:
    #print(ans_list)
    ind += ans_list[ind:].index(-1)
    now = res[ind]
    #print("now", ind, now)
    for j in range(ind+1,N):
        if ans_list[j] == -1 and res[j] % now == 0:
            ans_list[j] = 0
    ans_list[ind] = 1

ans = sum(ans_list)

print(ans)

Submission status: Wrong Answer

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

for i in a:
  if len([j for j in a if i%j != 0 and i != j]) == 0:
    cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter
N = int(sys.stdin.readline().rstrip())
A = list(map(int, sys.stdin.readline().rstrip().split()))
A.sort()
A_counters = Counter(A)

def solver(n):
    divisors = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i in nums:
                return False
            if i != n // i:
                divisors.append(n // i)
                if n // i in nums:
                    return False
    return True

nums = set()
ans = 0
for a in A:
    if solver(a) and A_counters[a] == 1:
        ans += 1
        nums.add(a)
print(ans)

Submission status: Wrong Answer

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

numbers = sorted(numbers)

cnt = 0
for i in range(len(numbers)):
    num = numbers[i]
    for j in range(i+1):
        if i == j:
            continue
        if numbers[i] % numbers[j] == 0:
            cnt += 1
            break
            
print(N - cnt)

Submission status: Wrong Answer

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

a.sort()

for i in range(n):
    for j in range(n-i):
        if(((a[-i]%a[j]) == 0) and (a[-i] != a[j])):
            x += 1
print(x)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
N = int(input())
li = [True for _ in range(0, 10**6 + 1)]
A = list(map(int, input().split()))
A.sort()
used = {}
for i in range(N):
    if A[i] not in used.keys():
        used[A[i]] = 1
    else:
        used[A[i]] += 1
ans = 0
for i in range(N):
    if used[A[i]] > 1 and not li[A[i]]:
        continue
    if li[A[i]] and used[A[i]] == 1:
        ans += 1
    else:
        continue
    for j in range(A[i], 10**6 + 1, A[i]):
        li[j] = False
print(ans)

Submission status: Wrong Answer

Solution code:
import math

n = int(input())
aL = sorted(list(map(int, input().split(" "))))

ans = n
for i in range(n - 1, -1, -1):
    for j in range(i):
        if aL[i] % aL[j] == 0:
            ans -= 1
            break

d = set()
for a in aL:
    d.add(a)
if len(d) == 1:
    print(0)
    exit()

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
print(0)
sys.exit()

Submission status: Wrong Answer

Solution code:
N=int(input())
a_list=list(map(int,input().split()))
count=0

a_list=sorted(a_list, reverse=True)
for i in range(N) :

  flag=True
  for j in reversed(range(i+1,N)) :
    if i!=j :
      if a_list[i]%a_list[j]==0  :
        flag=False
        break
  if flag :
    count+=1

print(count)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
a = na()
a.sort()
b = []
ans = n

for i in a:
    for p in range(len(b)):
        j,k = b[p]
        if j > i/2:
            x,y = b[-1]
            if i == x:
                ans -= 1
                if y == 0:
                    ans -= 1
                    b[-1] = (x,1)
            break
        if i%j == 0:
            ans -= 1
            break
    else:
        b.append((i,0))

print(ans)

Submission status: Wrong Answer

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

a.sort()
sub = [-1] * n
sub[0] = a[0]
index = 1
count = 1
for i in range(1, n):
    flag = True
    for j in sub[:index]:
        if a[i] // 2 < j:
            break
        if a[i] % j == 0:
            flag = False
            break
    if flag:
        sub[index] = a[i]
        index += 1
        count += 1
print(count if a[0] != a[-1] else 0)

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 len(set(A)) == 1:
        print(0)
    elif c[1] != 0:
        print(1)
    else:
        for i in range(N-1):
            k = N-1
            if c[As[i]] >= 2:
                ans -= 1
            else:
                for j in range(N):
                    if k == i:
                        break
                    if As[i] % As[k] == 0:
                        ans -= 1
                        break

                    k -= 1

        print(ans)


if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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

sosu = []
count = 0
for i in range(len(A)):
  if (i != len(A)-1 and A[i] == A[i+1]) or (i != 0 and A[i] == A[i-1]):
    continue
  for s in sosu:
    if A[i] % s == 0:
      break
  else:
    count+=1
    sosu.append(A[i])
print(count)

Submission status: Wrong Answer

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

l.sort(reverse=True)
cnt = 0
for i in range(len(l)-1):
    for j in range(i+1, len(l)):
        if l[i] % l[j] == 0:
            break
        if j == len(l)-1:
            cnt += 1
if l.count(l[-1]) == 1:
    print(cnt+1)
else:
    print(cnt)

Submission status: Wrong Answer

Solution code:
# Problem D - Not Divisible

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

# initialization
fact_nums = {}
count = 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, cnt])

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

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

    return arr

# count
for a in a_nums:
    facts = factorization(a)
    is_ok = True
    for f in facts:
        if f[0] in fact_nums:
            if f[0]%2==1:
                is_ok = False
                continue
            is_ok = False
            break
        is_ok = True
    if is_ok:
        for f in facts:
            fact_nums[f[0]] = 1
        count += 1

if len(list(set(a_nums)))==1:
    count = 0
# output
print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
d = {}
n = A[-1]
def makePrimeChecker(n):
    isPrime = [True] * (n + 1)
    isPrime[0] = False
    isPrime[1] = False
    for i in A:
        if i > 10**3:
            break
        if isPrime[i]:
            for j in range(i * i, n + 1, i):
                isPrime[j] = False
    return isPrime
P = makePrimeChecker(n)
i = 0
ans = 0
for j in A:
    if i == j:
        continue
    else:
        i = j
        if P[i]:
            if A.count(i) == 1:
                ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline
N = int(input())
A = [int(i) for i in input().split()]
A_dict = defaultdict(int)
for a in A:
    A_dict[a] += 1
del_list = []
for key in A_dict.keys():
    if A_dict[key] >= 2:
        del_list.append(key)
for dl in del_list:
    del A_dict[dl]
A = []
for key in A_dict.keys():
    A.append(key)
A = sorted(A)
ans = []
flag = True
for a in A:
    for i in ans:
        if a % i == 0:
            flag = False
            break
    if flag:
        ans.append(a)
    flag = True
print(len(ans))

Submission status: Wrong Answer

Solution code:
import math


#n=map(int,input().split())
n=int(input())
a=list(map(int,input().split()))
count=0
a.sort()
b=[]
while True:
    if a==[]:
        break
    if a[0] in a[1:len(a)]:
        temp=a[0]
        a.pop(0)
        a.pop(a.index(temp))
        continue
    b.append(a[0])
    a.pop(0)

    atemp=[i for i in a if i % b[-1]!=0]
    a=atemp.copy()
print(len(b))

Submission status: Wrong Answer

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


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

from collections import defaultdict
ans = defaultdict(list)
ans2 = list()

for i in A:
  for j in make_divisors(i):
    if j == 1:
      continue
    if len(ans[j]) == 0 or ans[j][-1] == i:
      if j == i:
        ans[j].append(i)
    else:
      break
for i,j in ans.items():
  if len(j) >= 2:
    if j[0] != j[1]:
      ans2.append(j[0])
  elif len(j) == 1:
    ans2.append(j[0])
print(len(set(ans2)))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)
ans=0
if len(set(a))==1:
    print(0)
    exit()
for i in range(n):
    k=0
    for j in range(i+1,n):
        if a[i]!=a[j]:
            if a[i]%a[j]!=0:
                k+=1
    if k==max(0,n-1-i):
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jun 14 21:14:26 2020

@author: NEC-PCuser
"""

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

A.sort()


li = []
before_value = 0
next_flg = False
for n in A:
    if len(li) == 0:
        li.append(n)
        next_flg = True
    if before_value == n:
        if li[len(li) - 1] == n:
            li.pop(len(li) - 1)
        next_flg = False
        before_value = n
        continue
    before_value = n
    if next_flg is True:
        next_flg = False
        continue
    for n2 in li:
        if (n % n2 == 0):
            break
        if (n < n2 * n2):
            li.append(n)
            break
    else:
        li.append(n)

print(len(li))

Submission status: Wrong Answer

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

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

print(A)

for i in range(N):
    a = A[i]
    if(i+1<N and a==A[i+1]):
        sonzai[i] = False
    for ii in range(i+1,N):
        if(A[ii] % a == 0):
            sonzai[ii] = False

print(sonzai.count(True))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(set(list(map(int, input().split()))))
A = sorted(A)
n = len(A)
if N != n:
    res = N - n + 1
else:
    res = 0
for i in range(1, n):
    a = A[i]
    sra = int(a ** 0.5) + 1
    for j in range(0, i):
        b = A[j]
        if a % b == 0:
            res += 1
            break
        if b > sra:
            break
print(N - res)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
num = int(input())
array = list(map(int,input().split()))
count = 0
res = 0
for i,j in enumerate(array):
    for m,n in enumerate(array):
        if i != m:
            if j % n != 0:
                #print(j,n)
                #print(j % n)
                count += 1
                #print(count)
                if count == num - 1:
                    res += 1
            else:
                break
    count = 0
                    
print(res)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
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:
    ct = 1
    for i in range(N):
        if i == 0:
            continue
        else:
            for j in range(i):
                if A[i]%A[j] == 0:
                    break
                if j == i-1:
                    ct = ct +1
    print(ct)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = sorted([int(i) for i in input().split()])
tested = [True for i in range(N)]

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

if A[0] != A[1]:
    ans = [A[0]]
else:
    ans = []

for i in range(1, N):
    flg = True
    if A[i] == A[i-1]:
        continue
    for j in ans:
        if j > A[i] // 2:
            break
        if A[i] % j == 0:
            flg = False
    if flg:
        ans.append(A[i])

print(len(ans))

Submission status: Wrong Answer

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

def solve():
    N = int(input())
    As = list(map(int, input().split()))

    setA = set(As)

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

    dic = {}
    duplicates = set()
    for a in As:
        if not a in dic:
            dic[a] = 0
        else:
            duplicates.add(a)
        dic[a] += 1


    ans = 0
    for a in As:
        is_ok = True
        for d in divisor(a):
            if d in setA:
                is_ok = False
                break

        if is_ok:
            ans += 1

    for x in duplicates:
        ans -= dic[x]

    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

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

ans = 0

for i in range(N):
    tmp = True
    if not A[i] in A:
        for j in range(i):
            if A[i] % A[j] == 0:
                tmp = False
                break
    else: tmp = False
    if tmp: ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
a=list(set(a))
ans=[]
ans.append(a[0])
#print(*a)
for i in range(len(a)):
    cnt=0
    for l in range(len(ans)):
        if a[i]%ans[l]==0:
            cnt+=1

            break
    if cnt==0:
        ans.append(a[i])
    #print(*ans)
if len(ans)!=len(a):
    print(len(ans))
else:
    print(0)

Submission status: Wrong Answer

Solution code:
import sys

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

As = sorted(As)

# 例外処理
if len(set(As)) == 1:
  print(0)
  sys.exit()

cnt = [True]*n
for i in range(0, n):
  for j in range(i+1, n):
    if As[j]%As[i] == 0:
      cnt[j] = False
    if As[j] == As[i]:
      cnt[i] = False

print(sum(cnt))

Submission status: Wrong Answer

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

a.sort()
d = {}

ans = 0
for i in range(n):
    if a[i] not in d.keys():
        ans += 1
        for j in range(1,1000):
            if j == 1:
                d[a[i]*j] = 1
            else:
                d[a[i]*j] = 0
    else:
        if d[a[i]] == 1:
            ans -= 1
            d[a[i]] = 2

print(ans)

Submission status: Wrong Answer

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

A = sorted(A)
num = len(A)

res = 1
if len(A) > 1 and A[0] == A[1]:
  res = 0
i = 1
while i < num:
  divisible = False
  for j in range(i):
    if A[i] % A[j] == 0:
      divisible = True
      A.pop(i)
      num -= 1
      i -= 1
      break
  i += 1

  if not divisible:
    res += 1
print(res)

Submission status: Wrong Answer

Solution code:
import os
import numpy as np

if os.path.exists('input.txt'):
    test_mode = True
else:
    test_mode = False

if test_mode:
    f = open('input.txt')
    
def get_input():
    if test_mode:
        return f.readline().rstrip()
    else:
        return input().rstrip()

def int_list(l):
    for i in range(len(l)):
        l[i] = int(l[i])


N = int(get_input())
A = get_input().split()
int_list(A)
A.sort()
ans = 0

for i in range(1, N):
    wareta = False
    for j in range(0, i):
        if A[i] % A[j] == 0:
            wareta = True
            break
    if not wareta:
        print(i, j)
        ans += 1
print(ans)
    
if test_mode:
    f.close()

Submission status: Wrong Answer

Solution code:
#4問目
import math
N = int(input())
A = list(map(int, input().split()))
LCM_a = [0] * N
count = 0
for i in range(N):
    #自分と他の数の最小公倍数を出す
    for j in range(N):
        if A[i] > A[j]:
            if A[i] % A[j] == 0:
                count += 1
                break
print(count)

Submission status: Wrong Answer

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

c = 0
for i in range(n):
    p = True
    for j in range(n):
        if a[i] > a[j]:
            if a[i]%a[j] == 0:
                p = False
                break
    if p:
        c += 1
print(c)

Submission status: Wrong Answer

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

#if n>1:
#    if li[0]==li[1]:
#        ans -= 1

import math
import bisect
from collections import Counter
chou = [i for i in li if li.count(i) >= 2]
se = set(chou)
#print(se)
li = list(set(li))
li.sort()
while len(li)>0:
    ba = li.pop(-1)
    if ba in se:
        continue
    s_ba = math.ceil(math.sqrt(ba))
    index = bisect.bisect_right(li, s_ba)
    tmp_li = li[:index+1]
    #print(ba,tmp_li)
    for tt in tmp_li:
        if ba%tt == 0:
            break
    else:
        ans += 1
print(ans)

Submission status: Wrong Answer

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


a=sorted(a,reverse=True)

cnt=0
for i in range(n):
    flg=0
    for j in range(i+1,n):
        if a[i]%a[j]==0:
            flg+=1
    if i==n-1:
        if a[i]%a[i-1]==0:
            flg+=1
            
    if flg==0:
        cnt+=1

print(cnt)

Submission status: Wrong Answer

Solution code:
def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True
n=int(input())
A=list(map(int,input().split(" ")))
g=0
for i in range(n):
  if is_prime(A[i]):
    for j in range(n):
      if A[i]==A[j]:
        g=g+1
        break
  else:
    for j in range(n):
      if i!=j:
        if A[i]%A[j]==0:
          g=g+1
          break
print(n-g)

Submission status: Wrong Answer

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys
input = sys.stdin.readline
ipnl = lambda n: [int(input()) for _ in range(n)]
inp = lambda :int(input())
ip = lambda :[int(w) for w in input().split()]

n = inp()
x = ip()
if len(set(x)) == 1:
    print(0)
else:
    ans = n
    for i in range(n):
        for j in range(n):
            if i != j:
                if x[i]%x[j] == 0:
                    ans -= 1
                    break
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N = int(input())
arr1 = [int(i) for i in input().split()]
arr = []
Dict = defaultdict(int)
for i in range(N):
    Dict[arr1[i]] += 1
for i in range(N):
    if Dict[arr1[i]] == 1:
        arr.append(arr1[i])
n = int(10**6)
prime = [False for i in range(n + 1)]
#arr.sort()
for p in arr:
    if not prime[p]:
        for j in range(p+p, n+1, p):
            prime[j] = True
count = 0
#print(prime)
for i in arr:
    if not prime[i]:
        #print(arr[i])
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
c=1
j=1
for i in range(n+1):
    if j<n:
        if i!=j:
            if a[j]%a[i]!=0:
                c+=1
                j+=1
    j+=1
if c==1:
    print(0)
else:
    print(c-1)