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

sosu = [1 for _ in range(10**6+2)]
sosu[:3] = [0,0,1]
i = 2
while i < len(sosu):
    if not sosu[i]:
        i += 1
        continue
    j = i + i
    while j < len(sosu):
        sosu[j] = 0
        j += i
    #     print(j)
    # print(i)
    i += 1
sosu_set = set()
for i in range(len(sosu)):
    if sosu[i]:
        sosu_set.add(i)

a_dic = {}
for i in a:
    if not i in a_dic:
        a_dic[i] = 0
    a_dic[i] += 1
res = 0
for i in a:
    j = 1
    flag = 1

    if i in sosu_set:
        if a_dic[i] == 1:
            res += 1
        continue

    while j * j <= i:
        if i % j == 0:
            x = j
            if (x == i and a_dic[x] >= 2) or (x != i and x in a_dic and a_dic[x] >= 1):
                flag = 0
                break
            x = i//x
            if (x == i and a_dic[x] >= 2) or (x != i and x in a_dic and a_dic[x] >= 1):
                flag = 0
                break

        j += 1
    # print(flag)
    if flag:
        res += 1

# print(a_dic)
print(res)


# p = []
# for i in range(2, 10**6+1):
#     flag = 1
#     j = 2
#     while j * j <= i:
#         if i % j == 0:
#             flag = 0
#             break
#         j += 1
#
#     if flag:
#         p.append(i)
#
# print(len(p))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
b=set()
kas=set()
for i in a:
    if len(b)==0:
        b.add(i)
    elif i in b:
        kas.add(i)
    else:
        flag= True
        for j in b:
            if j>10**3:
                break
            if i % j ==0:
                flag=False
                break                
        if flag:
            b.add(i)
print(len(b)-len(kas))

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    N = int(sys.stdin.readline())
    X = list(map(int, sys.stdin.readline().split()))
    X.sort(reverse= True)
    ans = [0 for i in range(N)]
    for i in range(N):
        for j in range(i+1, N):
            #print(X[i]%X[j], X[i])
            if X[i]%X[j]==0:
                ans[i]+=1
                break
    z = ans.count(0)
    if z ==1:
        print(0)
    else:
        print(z)
            
            
            
    


if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin


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

    # divisors.sort()
    return divisors


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    N = int(_in[0])  # type:int
    A_arr = list(map(int, _in[1].split(' ')))  # type:set(int)
    A_arr_set = set(A_arr)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    A_div = []
    for i, A in enumerate(A_arr):
        _ = make_divisors(A)
        _.remove(1)
        A_div.append(set(_))

    ans = 0
    for i, A_d in enumerate(A_div):
        _ = A_d & A_arr_set
        if len(_) == 1:
            if A_arr.count(list(_)[0]) == 1:
                ans += 1
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#: Author - Soumya Saurav
import sys,io,os,time
from collections import defaultdict
from collections import OrderedDict
from collections import deque
from itertools import combinations
from itertools import permutations
import bisect,math,heapq
alphabet = "abcdefghijklmnopqrstuvwxyz"

input = sys.stdin.readline

########################################
def gcd(a,b):
	return math.gcd(a,b)

n = int(input())
arr = list(map(int , input().split()))
if 1 in arr:
	print(1)
	exit()
arr = list(set(arr))
ans = 0
if len(arr) == 1:
	print(0)
	exit()
for i in range(len(arr)):
	f = 1
	for j in range(len(arr)):
		if i == j: continue
		if arr[i]%arr[j]==0:
			f = 0
	if f:
		ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
cnt = 0
same = []
d = [0]*(10**6+1)
a.sort()
for i in range(n):
    if i != n-1 and a[i] == a[i+1]:
        same.append(a[i])
    if d[a[i]]: continue
    cnt += 1
    res = a[i]
    while res <= 10**6:
        d[res] = 1
        res += a[i]
print(cnt-len(set(same)))

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import defaultdict

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

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

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

count = 0
f = np.ones_like(A, dtype=bool)
for i, x in enumerate(A):
    if not f[i]:
        continue

    # print(i, x, count, f)
    if counter[x] == 1:
        count += 1

    if x <= 10**3+1:
        f[i+1:] &= (A[i+1:] % x != 0)

print(count)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

A.sort()

ans = 0

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

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

for i in range(1, N):
    flag = True
    if i<N-1 and A[i]==A[i+1]:
        continue
    for j in range(0, i):
        if i==j:
            continue
        if A[i] % A[j] == 0:
            flag = False
            break
        if A[j]*A[0] > A[i]:
            break
    if flag:
        # print(i)
        ans += 1

print(ans)

Submission status: Wrong Answer

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

counter = 0

for i in range(l):
  for j in range(l):
    if n[i] == u[j]:
      pass
    elif u[j] % n[i] == 0:
      counter += 1
      break
    else:
      pass

print(l - counter)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
if 1 in a:
  if len(list(filter(lambda x:x==1, a))) > 1:
    print(0)
  else:
    print(1)
else:
  a.sort()
  ps = []
  tmp = 0
  ans = 0
  for i in range(n):
    if tmp == a[i]:
      continue
    else:
      tmp = a[i]
      for p in ps:
        if tmp % p == 0:
          break
      else:
        ans += 1
        ps.append(tmp)
  print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
import collections
import bisect


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


N = int(input())

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

A.sort()

ans = 0
ans = N
for i in range(N):
    divs = divisor(A[i])
    divs.sort()
    print(A[i], "divs", divs)
    for d in divs:
        if i < N - 1:
            if A[i] == A[i + 1]:
                ans -= 1
                break
        if i != 0 and d != 1:
            tmp = bisect.bisect_left(A[:i], d)
            if len(A[:i]) <= tmp:
                break
            if A[:i][tmp] == d:
                ans -= 1
                break
print(ans)

Submission status: Wrong Answer

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

A.sort()
L = []
pre_val = A[0]
count = 0
for a in A:
    if pre_val == a:
        count += 1
    else:
        temp = [pre_val, count]
        L.append(temp)
        count = 1
        pre_val = a
L.append([pre_val, count])

res = 0
for i in range(len(L)):
    flag = False
    Ai = L[i][0]
    for j in range(i):
        Aj = L[j][0]
        if Ai % Aj == 0:
            flag = True
            break
    if flag is False:
        res += L[i][1]
if len(L) == 1:
    print(0)
else:
    print(res)

Submission status: Wrong Answer

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

count = 0

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

print(count)

Submission status: Wrong Answer

Solution code:

import sys
import math
import itertools
import collections


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

def solve(N:int,A:list) -> int:
    A.sort()
    if(A[0] == 1):return N
    counter = 0
    primes = []
    not_primes = []
    black = []
    for a in A:
        target = factorization(a)
        if(len(target) == 1 and target[0][1] == 1 and (target[0][0] in black) == False):
            if a in primes:
                counter -= 1
                black.append(a)
            else:
                counter += 1
                primes.append(a)
        else:
            for t,_ in target:
                if t in primes:
                    break
            else:
                for np in not_primes:
                    if a % np == 0:
                        break
                else:
                    not_primes.append(a)
                    counter += 1
    return counter
def main():
    N = int(input())
    A = list(map(int,input().split()))
    # solve()
    print(solve(N,A))

if __name__ == "__main__":
    main()


# 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

Submission status: Wrong Answer

Solution code:
import math
from collections import Counter
import sys

input=sys.stdin.readline

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

#O(nlogn)
A.sort()

cnt= 0 if Counter(A)[min(A)]==1 else -1

while len(A)>0:
  #iの先頭要素を取り出す
  a = A[0]
  prev_len_A=len(A)
  #aで割り切れるやつは削除する
  A = [a_ for a_ in A if a_ % a != 0]
  cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
a = list(map(int, input().split()))
que = deque(sorted(a))
ans = []
while que:
    if len(que) == 1:
        ans.append(que.popleft())
        break
    x = que.popleft()
    ans.append(x)
    tmp = deque()
    while que:
        next = que.popleft()
        if next % x != 0:
            tmp.append(next)
    que = tmp
    

if a.count(a[0]) == n:
    print(0)
else:
    print(len(ans))

Submission status: Wrong Answer

Solution code:
N = int(input())
List = list(map(int, input().split()))
res = 0
New_List = sorted(List)
Flag = [1]*N
for i in range(1,N):
  print(Flag)
  if Flag[i] ==1:
    for j in range(i):
      if New_List[i] == New_List[j]:
        Flag[i] = 0
        Flag[j] = 0
      if Flag[j] == 1:
        if New_List[i] % New_List[j] == 0:
          Flag[i] = 0
        else:
          pass
      elif Flag[j] == 0:
        pass
  else:
    pass
res = Flag.count(1)
print(res)

Submission status: Wrong Answer

Solution code:
from collections import deque
from copy import deepcopy

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

d = deque(a)
if len(d) == 1:
	print(0)
	exit()

ans = 0
while len(d) > 0:
	ans += 1
	num = d.popleft()
	for i in range(len(d)):
		tmp = d.popleft()
		if tmp % num != 0:
			d.append(tmp)


print(ans)

Submission status: Wrong Answer

Solution code:
import copy
import numpy as np

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

aset = list(set(al))

if len(aset) == 1:
    print(0)
    exit()

ar = np.array(aset)

for i in range(len(ar)):
    new = ar%ar[i]
    if i == 0:
        ans = set(ar[new!=0].tolist())
        ans.add(ar[i])
    else:
        tmp = set(ar[new!=0].tolist())
        tmp.add(ar[i])
        ans = ans & tmp

print(len(ans))

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

A.sort()

c = Counter(A) 

B = []
for i, j in c.items():
    if j == 1:
        B.append(i)

if len(B) == 0:
    print(0)

else:
    B.sort()
    C = [B[0]]
    for i in range(1, len(B)):
        Flag = True
        for c in C:
            if B[i] % c == 0:
                Flag = False
                break
        if Flag == True:
            C.append(B[i])
    
    print(len(C))

Submission status: Wrong Answer

Solution code:
#!python3.8
# -*- coding: utf-8 -*-
# abc170/abc170_d
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N = i2n()
    A = sorted(int(c) for c in i2s().split(' '))
    max_ = A[-1]
    B = {}
    if N == 1:
        print(1)
        return
    for i in range(N):
        if i == 0:
            if A[i] == A[i+1]:
                continue
        elif i == N - 1:
            if A[i] == A[i-1]:
                continue
        elif A[i-1] == A[i] or A[i+1] == A[i]:
            continue
        B[A[i]] = True
    for b in B:
        if not B[b]:
            continue
        for i in range(2, max_ // b + 1):
            if b * i in B:
                B[b * i] = False
    res = 0
    for v in B.values():
        if v:
            res += 1
    print(res)
    return

main()

Submission status: Wrong Answer

Solution code:
n = int(input())
A = sorted(map(int, input().split()))
used = set()

U = A[-1]+1
is_prime = [1]*U
cnt = [0]*U
depri = 0
for a in A:
    cnt[a] += 1
    if cnt[a] == 2 and is_prime[a]:
        depri += 1
    if is_prime[a]:
        used.add(a)
        for q in range(2*a, U, a):
            is_prime[q] = 0
print(used)
print(len(used)-depri)

Submission status: Wrong Answer

Solution code:
from bisect import bisect
from bisect import bisect_right
from bisect import bisect_left

n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
b = set(a)
m = len(b)
ans = 0
#print(a)
#print(b)

for i in b:
    if bisect_right(a, i) - bisect_left(a, i) > 1:
        pass
    else:
        for j in range(2, int(i**0.5 + 2)):
            if (i/j in b) or ((i/j)%1==0 and (j in b)):
                break
        else:
            ans += 1
            #print(i)
print(ans)

Submission status: Wrong Answer

Solution code:
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:
        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-2] == a[n-1]:
    pass
else:
    flg = True
    for j in div:
        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 = list(map(int, input().split()))
a.sort()
ans = 0
for i in range(n):
  for j in range(i+2):
    if a[i] % a[j] == 0:
      break
  else:
    ans += 1
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# coding:utf-8


def main():
    N = int(input())
    A = list(map(int, input().split()))
    M = list(set(A))
    len_m = len(M)

    if len_m == 1:
        print(0)
    else:
        ans = len_m
        for i in range(len_m):
            ai = M[i]
            for j in range(len_m):
                if not i == j and ai % M[j] == 0:
                    ans -= 1
                    break

        print(ans)

    return


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

if a[-1] == 1:
    print(1)
    exit()

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

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

if n > 1:
    if a[-2] != a[-1]:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

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

for i in a:
    flag = 0
    tmp = make_divisors(i)
    for j in tmp:
        if j in sy:
            flag = 1
            break
    if not flag:
        count += 1
    sy.add(i)
print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
li = list(map(int, input().split()))
li.sort()
inf = (10**6)+1
isprime = [False]*(inf+1)
for i in li:
    isprime[i] = True
for i in range(len(li)):
      if i+1<len(li):
            if li[i] == li[i+1]:
                isprime[li[i]] = False
for i in li:
    if not isprime[i]:
        continue
    for k in range(i+i, inf+1, i):
        isprime[k] = False
prime_list = []
for i in range(1, inf+1):
    if isprime[i]:
        prime_list.append(i)
print(len(prime_list))

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    A = [int(i) for i in input().split()]
    from collections import Counter
    c = Counter(A)
    bl = set()
    for k, v in c.items():
        if v >= 2:
            bl.add(k)
    if c[1] == 1:
        return print(1)
    elif c[1] > 1:
        return print(0)
    A.sort()

    ans = 0
    used = set()
    for a in A:
        if a in bl:
            continue
        ok = True
        for i in range(2, int(a**0.5)+1):
            if a % i == 0:
                if i in used:
                    ok = False
                if a//i in used:
                    ok = False
            if not ok:
                break
        if ok:
            ans += 1
        used.add(a)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter

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


exists = [False] * (2 * (10 ** 5) + 1)

input = raw_input
n0 = int(input())
As_0 = map(int, input().split(" "))

out = 0

counter = Counter(As_0)
As = counter.keys()


for A in As:
    try:
        exists[A] = True
    except:
        pass

for A1, num in counter.items():
    try:

        if num >= 2:
            continue
        
        exist = False

        ds = make_divisors(A1)
        for d in ds:
            if exists[d]:
                if d != A1:
                    exist = True

        if not exist:
            out += 1
    except:
        pass

print(out)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time


def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def print_matrix(mat):
    for i in range(len(mat)):
        print(*['IINF' if v == IINF else "{:0=4}".format(v) for v in mat[i]])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
show_flg = False
# show_flg = True


# def gcd(a, b):
#     if b == 0:
#         return a
#     return gcd(b, a % b)


# def lcm(a, b):
#     return a*b // gcd(a, b)


# def good(A, N):
#     # A = sorted(A)
#     ans = A[0]
#     # for i in range(1, N):
#     #     ans = fractions.gcd(A[i], ans)
#     for i in range(1, N):
#         ans = lcm(ans, A[i])
#     return ans

def primes(n):
    is_prime = [1] * (n + 1)
    is_prime[0] = 0
    is_prime[1] = 0
    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] = 0
    return is_prime


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


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def coprime(a, b):
    return gcd(a, b) == 1


def factorization(n):
    if n <= 1:
        return []

    ret = []
    while n > 2 and n % 2 == 0:
        ret.append(2)
        n //= 2
    i = 3
    while i <= math.sqrt(n):
        if n % i == 0:
            ret.append(i)
            n //= i
        else:
            i += 2
    ret.append(n)
    return ret


def main():
    N = I()
    A = LI()
    MX = 10**6 + 1
    ans = []

    # for i in range(N):
    #     n = []
    #     for j in range(N):
    #         if i == j:
    #             continue
    #         n.append(A[i] % A[j] != 0)
    #     if all(n):
    #         ans.append(i+1)

    # print(*ans)
    # print([A[i-1] for i in ans])

    a_map = Counter(A)

    n = MX
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = 1 in a_map
    for i in range(1, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        if i not in a_map:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False

    ans = 0
    for i in range(N):
        if is_prime[A[i]] and a_map[A[i]] == 1:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
a2=list(map(int,input().split()))
a1=list(set(a2))
a=sorted(a1)
g=0
for i in a:
    if a2.count(i)>1:
        g+=1
b=[a.pop(0)]
for i in range(len(a)):
    f=0
    for j in b:
        if a[i]%j==0:
            f=1
    if f==0:
        b.append(a[i])
print(len(b)-g)

Submission status: Wrong Answer

Solution code:
import copy

memo = {}
def make_divisors(n):
    if n in memo:
        return memo[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
    memo[n] =  lower_divisors + upper_divisors[::-1]
    return memo[n]


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

setA = set(A)
result = 0
for i in range(N):
    tmp = A[i]
    A[i] = 0
    setA = set(A)
    A[i] = tmp
    if 1 in setA:
        break
    divisors = make_divisors(A[i])

    for d in divisors:
        if d in setA:
            break
    else:
        result += 1

print(result)

Submission status: Wrong Answer

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

if(len(set(a))==1 and len(a)>1):
    print(0)
    exit()

    
a.sort()
#print(a)

def prime_numbers(m):
    # 素数を保持するset
    primes = set()

    # 2以上m以下の素数を数え上げる
    n = a[0]
    while n <= m:
        # 自身より小さい全ての素数で割り切れなければ、素数とみなせる
        if all(n % i != 0 and n in a for i in primes):
            primes.add(n)
        n += 1

    return primes


prime=prime_numbers(a[n-1])

print(len(prime))

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left
from fractions import gcd

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

    A.sort(reverse=True)

    G=[]
    num=[]

    skips=[]
    res=0

    for i in range(len(A)):
        if (A[i] in skips)==False:
            flag=0
            for j in range(i+1,len(A)):
                if (A[i]==A[j]):
                    skips.append(A[i])
                    flag=1
                    break
                g=gcd(A[i],A[j])
                if g!=1 and g!=A[j]:
                    G.append(g)
                    num.append(A[j])
                elif g!=1 and g==A[j]:
                    if (g in G):
                        ind=G.index(g)
                        skips.append(num[ind])
                    flag=1
                    break
            if flag==0:
                res+=1

    print(res)




if __name__=="__main__":
    main()

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:
import numpy as np
n = int(input())
p = list(map(int,input().split()))
p.sort(reverse=True)
count=0
if np.unique(p).size >1:
    count +=1
for i in range(len(p)):
    for j in reversed(range(i+1,len(p))):
        if p[i]< p[j]*2:
            count +=1
            break
        if p[i]%p[j] ==0:
            break
        if j == i+1:
            count +=1
if count >=1:
    print(count)
else:
    print(count)

Submission status: Wrong Answer

Solution code:
import sys

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

for i in a:
    for k in a:
        if i == k :
            continue
        if i % k == 0:
            r += 1
            break

print(n-r)

Submission status: Wrong Answer

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

prime = []
data=a

while len(data)!=0:
    p = data[0]
    if len(data)>=2:
        if p==data[1]:
            data = [e for e in data if e % p != 0]
            continue

    if p>=max(a)/2:
        # print(p,data)
        prime+=data
        break
    prime.append(p)
    data = [e for e in data if e % p != 0]
print(len(prime))

Submission status: Wrong Answer

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


for i in range(N):
  for j in range(N):
    if i != j:
      if num_list[i] % num_list[j]!=0:
        break
      count = count + 1       

print(N-count)

Submission status: Wrong Answer

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

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

count = 0

for i,Ai in enumerate(A):
  Aby = make_divisors(Ai)
  if A.count(Ai)>=2:
    count+=1
  del Aby[-1]
  for a in Aby:
    if a in A:
      count+=1
      break
print (N-count)

Submission status: Wrong Answer

Solution code:
n = int(input())
li = list(map(int, input().split()))
li.sort()
inf = (10**6)+1
isprime = [False]*(inf+1)
for i in li:
    isprime[i] = True
for i in range(len(li)):
      if i+1<len(li):
            if li[i] == li[i+1]:
                isprime[li[i]] = False
for i in li:
    if not isprime[i]:
        continue
    for k in range(i+i, inf+1, i):
        isprime[k] = False
prime_list = []
for i in range(1, inf):
    if isprime[i]:
        prime_list.append(i)
print(len(prime_list))

Submission status: Wrong Answer

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

cnt = 0
onaji = 0

for i in range(len(A)):
    if i >= len(A)-1:
        break
    for j in range(len(A)-1,i,-1):
        if A[i] == A[j]:
            onaji = 1
        if A[j] % A[i] == 0:
            del A[j]
            
    if onaji == 1:
        del A[i]
        onaji = 0

print(len(A))

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    N = int(sys.stdin.readline())
    X = list(map(int, sys.stdin.readline().split()))
    X.sort(reverse= True)
    ans = [0 for i in range(N)]
    for i in range(N):
        for j in range(i+1, N):
            #print(X[i]%X[j], X[i])
            if X[i]%X[j]==0:
                ans[i]+=1
    z = ans.count(0)
    if z ==1:
        print(0)
    else:
        print(z)
            
            
            
    


if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort()
from collections import Counter
D=dict(Counter(A))

n=10**6
prime = {i for i in range(2,n)}
for i in range(2,n):
    if i in prime:
        for j in range(i*2,n,i):
            if j in prime:
                prime.remove(j)
ans=0
for i in range(N):
    if D[A[i]]==1:
        if A[i] in prime:
            ans+=1
        else:
            flag=True
            for j in range(i):
                if A[i]%A[j]==0:
                    flag=False
                    break
            if flag:
                ans+=1
print(ans)