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

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

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

        else:
            if i != A[min(ix+1, N-1)] and i != A[max(0, ix-1)]:
                # print(i,ix)
                ans += 1

    else:
        div = False
        for d in range(2, int(math.sqrt(i))+1):
            if i%d == 0:
                if d in hist or i//d in hist:
                    div = True
                    break

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

    hist.add(i)
        
print(ans)

Submission status: Wrong Answer

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

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]

for i in range(0,n):
    if a.count(a[i]) != 1:
        break
    else:
        l = sa & set(make_divisors(a[i]))
        if len(l) == 1:
            ans = ans + 1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
count = 1
for i in range(N-1):
  flag = 1
  for j in range(N-1, i, -1):
    if A[i] % A[j] == 0:
      flag = 0
      break
  if flag:
      count += 1
if N == 1:
  print(1)
elif A[0] == A[1]:
  print(0)
else:
  print(count)

Submission status: Wrong Answer

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

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

heapq.heapify(A)

ans = 0
while A:
    place = []
    d = heapq.heappop(A)
    ans += 1
    while A:
        tmp = heapq.heappop(A)
        if tmp % d != 0:
            place.append(tmp)
    else:
        for p in place:
            heapq.heappush(A, p)
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    *A, = map(int, input().split())
    A.sort()

    st = set()
    B = set()
    for x in A:
        if x in st:
            B.add(x)
        else:
            st.add(x)

    ans = -len(B)
    st = set()
    for x in A:
        for d in st:
            if x % d == 0:
                break
        else:
            ans += 1
            st.add(x)

    print(ans)


if __name__ == '__main__':
    main()

# import sys
# input = sys.stdin.readline
# 
# sys.setrecursionlimit(10 ** 7)
# 
# (int(x)-1 for x in input().split())
# rstrip()
#
# def binary_search(*, ok, ng, func):
#     while abs(ok - ng) > 1:
#         mid = (ok + ng) // 2
#         if func(mid):
#             ok = mid
#         else:
#             ng = mid
#     return ok

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=[0]*(2*10**6)
c=0
for i in a:
    b[i]+=1
for i in range(10**6):
    c+=1 if b[i]==1 else 0
    if b[i]==0:
        continue
    for j in range(1,10**6+10000):
        if i*j>=10**6+10000:
            break
        b[i*j]=0
print(c)

Submission status: Wrong Answer

Solution code:
def resolve():
    import bisect
    import math
    n = int(input())
    a = list(map(int, input().split()))
    a1 = {}
    for i in range(len(a)):
        if a[i] in a1:
            a1[a[i]] += 1
        else:
            a1[a[i]] = 1

    a = sorted(list(a1.keys()))
    maxa = a[-1]
    maxi = bisect.bisect_left(a, math.ceil(maxa**0.5))
    ans = [1]*(len(a))
    for i in range(0, maxi+1):
        if ans[i] == 1:
            for j in range(i+1, len(a)):
                if ans[j] == 0:
                    continue
                if a[j] == a[i]:
                    ans[i] = 0
                if a[j] % a[i] ==0:
                    ans[j] = 0
        if a1[a[i]] != 1:
            ans[i] = 0
    print(sum(ans))
resolve()

Submission status: Wrong Answer

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

if len(list(set(a))) != 1:
    cnt += 1
    while len(a) != 1:
        judge = True
        for j in a[1: len(a)]:
            if a[0]%j == 0:
                judge = False
                break

        if judge:
            cnt += 1

        del a[0]

print(cnt)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

import numpy as np


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

print(A)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int,input().split()))
A.sort()
ans = []
data = A
if len(set(A)) == 1:
    print(0)
else:
    while len(data) > 0:
        p = data[0]
        ans.append(p)
        data = [e for e in data if e % p != 0]
    print(len(ans))

Submission status: Wrong Answer

Solution code:
from collections import Counter


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


N = int(input())
A = list(map(int, input().split()))
AC = Counter(A)
ans = 0
for key, value in AC.items():
    if value != 1:
        continue
    if make_divisors(key):
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = input().split()
a = [int(i) for i in a]
a.sort(reverse=True)


if n == 1:
    print(0)
else:
    if a[-1] == a[-2]:
        cnt = 0
    else:
        cnt = 1
    for i in range(n-1):
        if a[i] == a[i-1]:
            flg =True
        else:
            flg = False
            for j in reversed(range(i+1,n)):
                if a[i] % a[j] == 0:
                    flg = True
                    break
        if flg == False:
            cnt += 1
    print(cnt)

Submission status: Wrong Answer

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

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

C = collections.Counter(A)
cand = set(A)

ans = 0
for i in range(N):
    if C[A[i]] >= 2:
        continue

    if A[i] in cand:
        ans += 1
        cand -= set([c for c in cand if c % A[i] == 0])
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
from math import sqrt
from bisect import bisect_left
input = stdin.readline

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

is_prime = [False] * n
is_continue = [False] * n

A.sort()
ans = 0

for i, a in enumerate(A):
    if a == 2:
        is_prime[i] = True
    tmp = a
    for j in range(2, int(sqrt(a)) + 1):
        if tmp % j == 0:
            tmp //= j
    if tmp == a:
        is_prime[i] = True

prev = 0

for i in range(0, n):
    if is_continue[i]:
        continue
    if is_prime[i]:
        if A[i] != prev and (i == n - 1 or A[i] != A[i + 1]):
            ans += 1
            prev = A[i]
            continue
        else:
            prev = A[i]
            is_continue[i] = True
            continue
    else:
        k = bisect_left(A, int(sqrt(A[i])) + 1)
        for j in range(0, k + 1):
            if A[i] % A[j] == 0:
                is_continue[i] = True
                break
        if not is_continue[i]:
            ans += 1


print(ans)
# print(A)
# print(is_prime)
# print(is_continue)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = input().split()
# A = [int(a) for a in A]
As = [0]*N
for i in range(N):
    As[i] = int(A[i])

A = As

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

count = 0
found = False
for i in range(N):
    for j in range(N):
        if i != j:
            if A[i] % A[j] == 0:
                found = True
                break
            else:
                continue
        else:
            continue
    if not found:
        count = count + 1
    found = False
        


print(count)

Submission status: Wrong Answer

Solution code:
import numpy as np


def main():
    n = int(input())
    As = list(map(int, input().split()))
    if 1 in As:
        print(0)
        exit()
    As = sorted(As)
    As_arr = np.array(As)
    ans = 0

    minus_num = 0
    while np.any(As_arr):
        if np.sum(As_arr == As_arr[0]) >= 2:
            minus_num += 1
        As_arr = As_arr[np.where(As_arr % As_arr[0] != 0)]
        ans += 1
    ans -= minus_num
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

A.sort()
B=[A[0]]
ans=0
x=0
for i in range(1,N):
    for j in B:
        if A[i]%j==0:
            #if A[i]==j:
            #    x+=1
            break
    else:
        B.append(A[i])

#print(B)
#if len(A)==len(set(A)):
print(len(B))
#else:

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)

n = int(input())
a = list(map(int, input().split()))
#n, m = map(int, input().split())
#s = input()
#s,t = input().split()
#
#readline = sys.stdin.readline
#n,m = [int(i) for i in readline().split()]
#ab = [[int(i) for i in readline().split()] for _ in range(n)]

a.sort()

ans = 0

for i in range(n):
    
    x = a[i]

    l = -1; r = n # 二分探索時は探索範囲は取り得る値+-1しておく

    while l+1 < r:
        c = (l+r)//2
        if a[c] <= x//2:
            l = c
        else:
            r = c
    
    for j in range(c+1):
        if i != j and x%a[j] == 0:
            break
        elif a[i] == a[j]:
            break
    else:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(n) for n in input().split()]
ans = []
for i in range(N):
    c = 0
    for j in range(N):
        if i != j:
            if A[i] % A[j] == 0:
                break
            else:
                c += 1
                if c == N-1:
                    ans.append(i)
print(len(ans))

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    a.sort()
    c = 1
    b = 0
    d = 0
    for i in range(1, n):
        if b == 0 and a[i] == a[i - 1]:
            c -= 1
            b = 1
        elif a[i] != a[i - 1]:
            b = 0
            for j in range(i):
                d = 0
                if a[i] % a[j] == 0:
                    d = 1
                    break
                if a[j] > a[i] // 2:
                    break
            if d == 0:
                c += 1
    print(c)

main()

Submission status: Wrong Answer

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


A.sort()
counter_ = 0
i = 0
div = []
judge = True
for i in range(N):
    for div_ in div:
        if A[i] % div_ == 0:
            counter_ += 1
            judge = False
            break
    if judge:
        div.append(A[i])

for div_ in div:
    if A.count(div_) > 1:
        counter_ += 1
        
print(N - counter_)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
N=int(input())
A=list(map(int,input().split()))
D=dict()
ans=0
for i in A:
    D[i]=0
for i in list(combinations(A,2)):
    if i[0]%i[1]!=0:
        D[i[0]]+=1
        if D[i[0]]==N-1:
            ans+=1
    if i[1]%i[0]!=0:
        D[i[1]]+=1
        if D[i[1]]==N-1:
            ans+=1
print(ans)

Submission status: Wrong Answer

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

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


n = int(input())
a = lmp()
a.sort()
cnt = 0
amax = max(a)
num = [0]*int(amax+5)
for i in range(n):
    if num[a[i]] == 0:
        cnt += 1
    for j in range(a[i], int(amax+5), a[i]):
        num[j] = 1

for i in range(1,n):
    if a[0] == a[i]:
        cnt -= 1
        break
print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
S = set()
T = set()
for x in A:
    S.add(x)
    T.add(x)
cnt = 0

for x in sorted(S):
    i = 2
    while x * i <= A[-1]:
        if x * i in T:
            T.remove(x*i)
        i += 1
print(len(T))

Submission status: Wrong Answer

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

flags = [True for i in range(N)]

for i in range(N):
    if flags[i]:
        for j in range(i+1, N):
            if A[i] == A[j]:
                flags[i] = False
                flags[j] = False
            else:
                break

count = 0
for i in range(N):
    if flags[i]:
        count += 1
        for j in range(i+1, N):
            if A[j] % A[i] == 0:
                flags[j] = False
print(count)

Submission status: Wrong Answer

Solution code:
import bisect
N = int(input())
*A, = map(int, input().split())
A.sort()
a = []
b = []
last = 0
for i in range(N):
    if last != A[i]:
        a.append([A[i], 0])
        b.append(A[i])
        last = A[i]
    a[-1][1] += 1


def isPrime(n):
    # nの素数判定
    if n == 1:
        return False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False
    return True


ans = 0
for n, c in a:
    if c == 1:
        if isPrime(n):
            ans += 1
        else:
            r = bisect.bisect_right(b, n//2)
            ok = True
            for i in range(r):
                if n % b[i] == 0:
                    ok = False
                    break
            if ok:
                ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
arr = list(map(int, input().split()))
arr.sort()
count = 0
for i in range(0,n):
  for j in range(0,i):
    if(arr[i]/arr[j] == 0):
      count += 1
      break
print(n-count)

Submission status: Wrong Answer

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

l.sort()

i = 0
while i < len(l):
    if l[i] > 500000:
        break
    if i != len(l)-1 and l[i] == l[i+1]:
        k = l[i]
        h = i
        while i < len(l) and l[i] == k:
            l.remove(k)
        i += 1
    else:
        l = l[:i+1] + [j for j in l[i+1:] if j % l[i] != 0]
        i += 1

print(len(l))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
# print(A)
a = [0]*((10**6)+1)

ans = 0
reigai = a.copy()
for i in range(N):
    # print(i)
    if a[A[i]] == 0:
        ans += 1
        k = 1
        while k <= A[-1]//A[i]:
            a[A[i] * k] += 1
            k += 1
            # print("k=",k)
    if A.index(A[i]) != i:
        reigai[A[i]] = 1
        # print("hi")
        
    # print(ans)
print(ans-sum(reigai))

Submission status: Wrong Answer

Solution code:
n=int(input())
A=list(map(int,input().split()))
if n==1:
  print(1)
  exit()
A.sort()
A2=[]
before=A[0]
flag=0
Del=[]
for a in A[1:]:
  if before!=a:
    if flag==0:
      A2.append(before)
      before=a
    else:
      Del.append(before)
      before=a
      flag=0
  else:
    flag=1
if flag==0:A2.append(A[-1])

ans=len(A2)
A2=A2+Del
A2.sort()
S=[]
for a in A2:
  flag==0
  for s in S:
    if s*2>a:break
    if a%s==0:
      ans-=1
      flag=1
      break
  if flag==0:
    S.append(a)
print(ans)

Submission status: Wrong Answer

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

A.sort()

ans = 0
if N != 1:
    div = set()
    for i in range(N):
        if not A[i] in div:
            if i == N-1:
                if A[i] != A[i-1]:
                    ans += 1
            else:
                if A[i] != A[i+1]:
                    ans += 1
                    if i != N-1:
                        for j in range(i+1, N):
                            if A[j] % A[i] == 0:
                                div.add(A[j])

print(ans)

Submission status: Wrong Answer

Solution code:
_n = int(input())
_a = list(map(int, input().split(" ")))
_counter = 0

_a = list(set(_a))

for _i in range(len(_a)):
  for _j in range(len(_a)):
    if _i != _j and _a[_i] % _a[_j] == 0:
      break
    elif _j == _n - 1:
      _counter += 1
print(_counter)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict

def get_prime_factors(n):
    dd = defaultdict(lambda: 0)
    if n > 1:
        i = 2
        while i * i <= n:
            if n % i == 0:
                dd[i] += 1
                n /= i
                i = 2
            else:
                i += 1
        dd[n] += 1
    return dd


def solve(N: int, A: "List[int]"):
    A = sorted(list(set(A)))
    if len(A) == 1:
        print(0)
        return
    
    count = 0

    # dd = defaultdict(lambda: [0, -1])
    
    # for a in A:
    #     d = get_prime_factors(a)

    #     flag = True
    #     for prime, value in d.items():
    #         dd_prime, dd_mn = dd[prime]
            
    #         if dd_mn == -1:
    #             dd_mn = a

    #         if dd_prime != 0 and a % dd_mn==0:
    #             flag = False

    #         dd[prime][0] += value
    #         dd[prime][1] = min(dd_mn, a)
    #     if flag:
    #         count+= 1

    print(count)
    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:
import copy

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

a.sort()

b = copy.deepcopy(a)

for i in range(n):
    for j in range(i+1, n):
        if a[j] % a[i] == 0 and a[j] in b:
            b.remove(a[j])

print(len(b))

Submission status: Wrong Answer

Solution code:
def calc():
    n, *a = map(int, open(0).read().split())
    if n == 0:
        return 0
    if n == 1:
        return 1

    a.sort()
    count = 0
    r = set()
    prev = -1 if a[0] != a[1] else a[0]
    for x in a:
        if x == prev:
            continue
        if r & divis(x):
            continue
        r.add(x)
        count += 1
    return count

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

print(calc())

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from collections import Counter

N = int(input())
A = sorted(list(map(int, input().split())))
E = set([A[0]])
ans = 1
C = Counter(A)
for k in C.keys():
    if C[k] >= 2:
        ans -= 1
        continue
    else:
        a = k
        Flag = True
        for e in E:
            if a%e == 0:
                Flag = False
                break
        if Flag:
            ans += 1
        E.add(a)

print(ans)

Submission status: Wrong Answer

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

def main():
    from collections import Counter
    n = int(input())
    A = list(map(int, input().split()))
    s = set(A)
    c = Counter(A)
    cnt = 0
    if c[1] >= 1:
        print(1)
    else:
        for a in A:
            if c[a] > 1:
                continue
            else:
                d = set(div(a))
                if len(d & s) == 1:
                    cnt += 1
        print(cnt)
main()

Submission status: Wrong Answer

Solution code:
import bisect

n = int(input())
a = list(set(list(map(int, input().split()))))
a.sort()
k = len(a)
if k == 1:
    print(0)
    exit()
ok = [0] * k
for i in range(k):
    if ok[i] == 1:
        continue
    if a[i] < 2 * 10 ** 4:
        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)
            if a[r] == a[i] * times:
                ok[r] = 1
            times += 1
print(len([i for i in ok if i == 0]))

Submission status: Wrong Answer

Solution code:
n=int(input())
a = list(map(int,input().split()))
b=0
a.sort()
if n==1:
    print(0)
    exit()
st=[]
while a:
    if len(a)==1:
        if a[0] in st:
            break
        else:
            b+=1
            break
    else:
        p=a.pop(0)

        for i in a:
            if i%p==0:
                a.remove(i)
                st.append(p)
                if i!=p:
                    b+=1



print(b)

Submission status: Wrong Answer

Solution code:
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

import math

n=ni()
a=sorted(nl())

sa = []

ans=0

last=-1
cnt=0
for i in range(n):
  if a[i]!=last:
    cnt=0
    last=a[i]
  else:
    cnt+=1
  if cnt <= 2:
    sa.append(a[i])


l =len(sa)


for i in range(l):
  for j in range(l):
    if i==j:
      continue
    if sa[i]%sa[j]==0:
      break
  if j==n-1:
    ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import collections

N = int(input())
A = sorted(list(map(int, input().split())), reverse = True)
C = collections.Counter(A)
C_keys = np.array(list(C.keys()))
C_values = tuple(C.values())
divisible = 0
for i, c in enumerate(C_keys):
    if 0 in c % C_keys[i + 1:]:
        divisible += C_values[i]
    if C_values[i] > 1:
        divisible += C_values[i]
        
print(N - divisible)

Submission status: Wrong Answer

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

def divisor(n): #nの約数を全て求める
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i:
        divisors.append(n//i)

  return set(divisors)

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)

Submission status: Wrong Answer

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

x = set(A)
def n(n):
    return [i for i in range(2, n) if n % i == 0]

print(sum([1 for a in A if A.count(a) == 1 and not (set(n(a)) & x)]))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = sorted([int(i) for i in input().split()],reverse=True)
c = 1

for i in range(N-1):
  b = A[i]
  for y in range(i+1,N):
    if b % A[y] == 0:
      break
  else:
    c += 1
else:
  print(c)

Submission status: Wrong Answer

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    a = [int(i) for i in ipt().split()]
    a.sort()
    yn = [0]*(10**6+1)
    for i in a:
        yn[i] += 1

    def yakusu(n):
        ys = [1]
        ni = 2
        while ni**2 <= n:
            if n%ni == 0:
                ys.append(ni)
                ys.append(n//ni)
            ni += 1
        return ys
    ans = 0
    for i in a:
        f = True
        if yn[i] != 1:
            continue
        for j in yakusu(i):
            if yn[j]:
                f = False
                break
        if f:
            ans += 1

    print(ans)

    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())

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

same=set()

for i in range(n-1):
    if A[i]==A[i+1]:
        same.add(A[i])


s=set()
for i in A:
    j=2
    while i*j<=10**6:
        s.add(i*j)
        j+=1

B=set(A)-s

print(len(B)-len(same))

Submission status: Wrong Answer

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

ans = 0
for i in range(n):
    if i == 0 and n > 1:
        if A[i] % A[i+1] != 0:
            ans += 1
    for j in range(i):
        if A[i] % A[j] == 0:
            break
        if j == i - 1:
            if j + 1 < n:
                if A[i] % A[j+1] != 0:
                    ans += 1
            else:
                ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
A = [int(i) for i in input().split()]
A_np = np.array(A)
count = []

if np.all(A_np%A[0]==0):
    print(0)
else:
    for i in range(len(A)):
        count.append(np.count_nonzero(A_np%A[i] == 0) -1)
    ans = N - max(count) 
    print(ans)

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)

m = max(d, key=lambda x: x[0])[0]

while len(d):
    a, c = d.pop()
    if c == 1:
        count += 1
    if a == 1:
        break
    if a * a <= m:
        d = [elm for elm in d if elm[0] % a]

print(count)

Submission status: Wrong Answer

Solution code:

import math

N = int(input())
A = list(map(int, input().split()))
A.sort()
#A = [i for i in range(2, N+2)]

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

D = [A[0]]
E = []

for i, x in enumerate(A):
  Flag = True
  
  if i >= 1:

    if x == D[-1]:
      E.append(x)
      continue

    if is_prime(x):
      D.append(x)
      continue
    
    for j in D:
      if x%j == 0:
        Flag = False
        if x == j:
          E.append(x)
        break
    
    if Flag:
      D.append(x)

print(len(set(D)-set(E)))

Submission status: Wrong Answer

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

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

d =set()

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

print(len(d))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
from sys import stdin,setrecursionlimit
import heapq,bisect,math,itertools,string,queue,datetime,copy
setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, stdin.readline().split()))

N = int(input())
Als = inpl()

Als.sort()

def era(ls):
    result = []
    while len(ls)>=1:
        a = ls[0]
        ls = ls[1:]
        f = False
        for item in ls:
            if item==a:
                f = True
            if item%a==0:
                ls.remove(item)
        if not f:
            result.append(a)

    print(len(result))

era(Als)

Submission status: Wrong Answer

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

A.sort()

cnt = 0

for i in range(1, N+1):
    ai = A[i-1]
    for j in range(1, N+1):
        aj = A[j-1]
        if i == j and j != N:
            continue
        if ai % aj == 0 and j != N:
            break
        if j == N:
            cnt += 1
            break

print(cnt)

Submission status: Wrong Answer

Solution code:
def prime_fact(n):
    a = []
    while n % 2 == 0:
        a.append("2")
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(str(f))
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(str(n))
    return ",".join(a)


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

#    prime_factors_to_s = list(map(str,prime_factors))
#    prime_factors_string = list(map(lambda x:",".join(x),prime_factors_to_s))


##        ind = dict()
##    for i in range(n):
##        if not i in ind:
##            ind[nums[i]] = [i] #インデックスを保存
##        else:
##            ind[nums[i]].append(i) #重複も一応……)
    nums.sort()
    prime_factors = list(map(prime_fact,nums))
    #print(prime_factors)

    undivisable = [True] * n
    counter = 0
    #print(nums)
    for i in range(n-1):

        if not undivisable[i]:
            continue #すでに何かで割られた数はスルー(それより小さい数で割れる)
        divisor = prime_factors[i]
        for j in range(i+1,n):
            #print(j)
            if divisor in prime_factors[j]:
                undivisable[j] = False
            if prime_factors[j] == divisor:
                undivisable[i] = False
        #print(nums[i],undivisable)

    print(undivisable.count(True))



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

A.sort()

x = A[0]
flag = True
for a in A:
    if a % x != 0:
        flag = False
if flag:
    print(0)
    exit()

used = [False] * A[-1]
ans = 0
for idx, a in enumerate(A):
    if used[a - 1]:
        continue
    ans += 1
    for j in range(a, len(used) + 1, a):
        used[j - 1] = True
print(ans)

Submission status: Wrong Answer

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

cand = []
ans = 0
for a, val in cA.items():
    if a == 1:
        print(N)
        exit()
    elif len(cand) != 0 and val == 1:
        for t in cand:
            if a % t == 0:
                break
        else:
            #print(a)
            cand.append(a)
            ans += val
    elif val == 1:
        #print(a)
        cand.append(a)
        ans += val
    else:
        break
print(ans)