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:
# 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
                fact_nums[f[0]] = 1
                continue
            fact_nums[f[0]] = 1
            is_ok = False
            break
        is_ok = True
        fact_nums[f[0]] = 1
    if is_ok:
        count += 1

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

# output
print(count)

Submission status: Wrong Answer

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

A_n.sort(reverse =True)
ans = 0

if N==1:
    ans=1
else:
    for i in range(N):
        if i != N -1:
            if A_n[i] ==A_n[i +1]:
                continue
        elif A_n[N-1] !=A_n[N-2]:
            ans +=1
            break        
        for j in range(i+1,N):
            if A_n[i]%A_n[j] != 0 and j != N-1:
                continue
            elif A_n[i]%A_n[j] != 0 and j == N-1:
                ans +=1
            else:
                break
    

print(ans)

Submission status: Wrong Answer

Solution code:
def func(x):
    l=p[:x+1]
    for j in range(x+1,len(p)):
        if p[j]%p[x]!=0:
            l.append(p[j])
    return l

n=int(input())
p=list(map(int,input().split()))
c=0
p=list(set(p))
p.sort()
#print(p)
for i in range(len(p)):
    p=func(i)
print(p)

Submission status: Wrong Answer

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

C=[1 for i in range(10**6+1)]
for i in range(N):
    if C[A[i]]==0:
        continue
    for j in range(2,10**6//A[i]-1):
        C[A[i]*j]=0

ans=0
for i in range(N):
    if i!=N-1 and A[i]==A[i+1]:
        C[A[i]]=0
        continue
    if C[A[i]]==1:
        ans+=1
        C[A[i]]=0

print(ans)

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:
	d2 = deque([])
	ans += 1
	num = d.popleft()
	for i in range(len(d)):
		tmp = d.popleft()
		if tmp % num != 0:
			d2.append(tmp)
	d = deepcopy(d2)


print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
line = list(map(int, input().split()))
line.sort()
count = []
for i in range(0, n):
	f = False
	ai = line[i]
	for j in range(i+1, n):
		aj = line[j]
		if aj % ai == 0: f = True
	if f is False and line[i] not in count: count.append(line[i])
print(len(count))

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:
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 not (a % v == 0 and ((v in dp) or (a // v in dp))):
                        ans += 1
                    break
                if a % v == 0:
                    break
            else:
                ans += 1

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

    print(ans)

    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
ans = [0]*n
warizai_index = set()

for i in range(n):
    for wari in warizai_index:
        if a[i]%a[wari] == 0 and i != wari:
            ans[i] = 1
            if i in warizai_index:
                warizai_index.remove(i)
            break
    if ans[i] == 1:
        continue
    
    for j in range(i+1,n):
        if i == j:
            continue
        if a[i]%a[j] == 0:
            ans[i] = 1
            if i in warizai_index and a[i] != a[j]:
                warizai_index.remove(i)
            warizai_index.add(j)
            break

print(ans.count(0))

Submission status: Wrong Answer

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

a = sorted(set(a))
w = 0
h = 0
while True:
    h = 1
    while True:
        if w + h == len(a):
            '''
            print(a)
            '''
            break
        if a[w+h] % a[w] == 0:
            '''
            print(h)
            '''
            del a[w+h]
        else:
            '''
            print(a[w+h], h, w, a)
            '''
            h += 1
    w += 1
    if w == len(a):
        print(len(a))
        exit()

Submission status: Wrong Answer

Solution code:
N = int(input())
Mylist = input().split()
Mylist = [int(s) for s in Mylist]
ANS = 0

Mylist.sort()

for i in range(1,N):
    cheack = 0
    for j in range(i):
        print(str(Mylist[i]) + "%" + str(Mylist[j]) +"=" +str(Mylist[i] % Mylist[j]))
        if Mylist[i] % Mylist[j] != 0:
            cheack += 1
    if cheack == (i):
        ANS += 1

if Mylist[0] != Mylist[-1]:
    ANS = ANS + 1
print(ANS)

Submission status: Wrong Answer

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

a=int(input())
b=[int(x) for x in input().split()]
b=sorted(b)
d={}
for i in b:
  if i not in d:
    d[i] = 1
  else:
    d[i] += 1
c=0
for i in range(0, a):
  if d[b[i]] > 1:
    c+=1
  elif not is_prime(b[i]):
    for j in range(0, i):
      if b[i] % b[j] == 0:
        c+=1
        break
print(a-c)

Submission status: Wrong Answer

Solution code:
n = int(input())
li = list(map(int, input().split()))
li.sort()
inf = (10**6)+1
isprime = [False]*(inf)
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, 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())
list_ = list(map(int, input().split()))
cnt = 0

for i in range(n):
    flag = True
    same_cnt = 0
    for j in range(n):
        if i == j:
            continue

        if list_[i] == list_[j]:
            same_cnt += 1
            continue

        if list_[i] % list_[j] == 0:
            flag = False
            break

    if flag and same_cnt != n - 1:
        cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
n = int(input())
arg = list(map(int, input().split()))

ans = 0
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        else:
            if arg[i] < arg[j]:
                continue
            num = arg[i] % arg[j]
            if num == 0:
                ans += 1
                break

if ans == 0:
    print(ans)
else:
    print(n - ans)

Submission status: Wrong Answer

Solution code:
import math

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

a = sorted(a)
ans = 1
lst.append(a[0])

for i in range(1,n):
    flg = 0
    for j in range(len(lst)):
        if lst[j] > math.ceil(a[i]/2):
            break
        if a[i] % lst[j] == 0:
            flg = 1
            break
    if flg == 0:
        lst.append(a[i])

print(len(lst))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
MAX = 10 ** 6 + 10

one = a.count(1)
if one > 0:
  print(one)
  exit(0)

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
m = [0] * MAX
for i in range(n):
  m[a[i]] += 1
#print(m[:30])
mx = max(a)
ans = 0
for i in range(2, mx + 1):
  if m[i] != 1:
    continue
  divs = make_divisors(i)
  flg = True
  #print('i : ', i)
  #print(divs)
  for j in range(len(divs)):
    div = divs[j]
    if div == i:
      continue
    
    if m[div] > 0:
      flg = False
      break
  if flg:
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A={int(x) for x in input().split()}


ans=0
B=[]
if len(A)==1:
    ans=0
else:
    A=sorted(A)
    while True:
        B.append(A[0])
        A=[a for a in A[1:len(A)] if a%A[0]!=0]
        if len(A)==0:
            break
    ans=len(B)

print(ans)

Submission status: Wrong Answer

Solution code:
M = int(input())
A=list(map(int,input().split()))
A=list(set(A))
A.sort()
k=0
if len(A)==1:
    print(0)
else:
    while True:
        if k>=len(A)-1:
            break
        for i in range(len(A)-1,k,-1):
            if A[i]%A[k]==0:
                A.pop(i)
        k+=1

    print(len(A))

Submission status: Wrong Answer

Solution code:
import sys
N = list(map(int, input().split()))
A= list(map(int, input().split()))
A=list(set(A))
count=0
if len(A)==1:
    print('0')
    sys.exit()
for n in range(len(A)):
    judge=0
    for j in range(len(A)):
        if n!=j and A[n]%A[j]==0:
            judge=1
            break
    if judge==0:
        count+=1
print(count)

Submission status: Wrong Answer

Solution code:
#d
n = int(input())
a = list(map(int, input().split()))
a_l = sorted(a)
count = 0
for i in range(len(a_l)):
    flag = 0
    if a_l.count(a_l[i])>1:
        flag=1
        break
    for j in range(i):
        if a_l[i] % a_l[j] == 0:
            flag = 1
            break
        if a_l[i] < 2*a_l[j]:
            break
    if flag == 0:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

A.sort()
d = deque()
for i in range(N-1):
    if A[i] != A[i+1]:
        d.append(A[i])
if A[N-1] != A[N-2]:
    d.append(A[N-1])

ans_que = deque()
while len(d):
    num = d.popleft()
    ok = 1
    ind = 0
    while ok and ind < len(ans_que):
        x = ans_que.popleft()
        ans_que.append(x)
        if num % x == 0:
            ok = 0
        
        ind += 1
    if ok:       
        ans_que.append(num)

print(len(ans_que))

Submission status: Wrong Answer

Solution code:
### ----------------
### ここから
### ----------------

import sys

def resolve():
    readline=sys.stdin.readline

    #n,m,k=map(int, readline().rstrip().split())
    n=int(readline())
    arr=list(map(int, readline().rstrip().split()))
    if n==1:
        print(0)
        return

    arr.sort()
    #print(arr)
    ans=0
    for i in range(n):
        flg=0
        if i==0:
            if arr[i]!=arr[i+1]:
                ans+=1
            continue

        h=int(arr[i]**(1/2))+1
        for j in range(0,i):
            if arr[i]%arr[j]==0:
                flg=1
                break
            if arr[j] > h:
                break
        if flg==0:
            if (i+1)<n:
                if arr[i]==arr[i+1]:
                    flg=1
        if flg==0:
            ans+=1
    print(ans)
    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Wrong Answer

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

counter = 0
for i in range(n):
    for j in range(i):
        if i == j:
            continue
        if a[i]/a[j] == a[i]//a[j]:
            break
    else:
        counter += 1

print(counter)

Submission status: Wrong Answer

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

res = []

if 1 not in pi:
    sorted_p = sorted(pi)
    max_p = sorted_p[-1]

    if sorted_p[0] != max_p:
        for p in sorted_p:
            flag = True
            for div in res:
                if p % div == 0 and p != div:
                    flag = False
                    break
            if flag:
                res.append(p)

print(len(res))

Submission status: Wrong Answer

Solution code:
import numpy as np
#input()

def no_Divisible(num,num_list):
    for row in set(num_list):
        if num%row==0:
            return 0
    return 1

input_list = np.array(sorted(list(map(lambda x:int(x),input().split(" "))),reverse=True))
count = 0
prev_num = 0
for i,num in enumerate(input_list):
    if num == prev_num:
        continue
    #print(num)
    #print(input_list[i+1:]%num)
    #if sum(input_list[i+1:]%num==0):
    if no_Divisible(num,input_list[i+1:]):
        count += 1
    prev_num = num
print(count)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

c = Counter(a)
new = []
for key, val in c.most_common():
    if val == 1:
        new.append(key)

ans = 0
for i in range(len(new)):
    flag = True
    for j in range(len(new)):
        if i != j and new[i] % new[j] == 0:
            flag = False
            break

    if flag:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
def resolve():
    N = int(input())
    A = list(map(int,input().split()))
    B= set(A)

    A.sort()

    count = 0
    for idx,i in enumerate(A):
        if i == A[idx -1]:
            continue
        if idx != N-1 and i == A[idx +1]:
            B.discard(i)

        deleted =set()
        for j in B:
            if i == j:
                count+=1
            if j % i ==0:
                deleted.add(j)
        B.difference_update(deleted)

    print(count)

resolve()

Submission status: Wrong Answer

Solution code:
import collections
N = int(input())
A = list(map(int,input().split()))
counter = collections.Counter(A)
B = list(set(A))
count = 0
for i in range(len(B)):
    if counter[B[i]]>1:
        continue
    if B[i]==1:
        count += 1
        continue
    else:
        check = 0
        for j in range(1,int(B[i]**0.5)+1):
            if B[i]%j==0 and (j in counter or B[i]//j in counter):
                check += 1
                break
        if check==0:
            count += 1
print(count)

Submission status: Wrong Answer

Solution code:
def main():
    from collections import Counter
    n= int(input())
    inlis = list(map(int, input().split()))
    inlis.sort()
    for num in inlis:
        if num > inlis[-1]/2:
            break
        else:
            new = [e for e in inlis if e % num == 0]
            new.sort()
            #print(new)
            if len(new) > 1:
                if new[0] != new[1]:
                    for i in range(1, len(new)):
                        inlis.remove(new[i])
                else:
                    for i in range(0, len(new)):
                        inlis.remove(new[i])
            

    print(len(inlis))

    
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
ans = [True] * len(A)


A.sort()

for i in range(len(A)):
        if A[i] > 450:
                break
        for j in range(len(A)):
                if i == j:
                        continue
                if A[j] % A[i] == 0:
                        ans[j] = False


count = 0
for i in ans:
        if i:
                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()))
setA = set(A)

count = 0
for i in range(len(A)):
    flag = False
    for div in make_divisors(A[i]):
        if div <= 1:
            continue
        if div == A[i]:
            if div in A[:i]:
                flag = True
                break
            if div in A[i+1:]:
                flag = True
                break
        else:
            if div in setA:
                flag = True
                break
    if not flag:
        count += 1

print(count)

Submission status: Wrong Answer

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

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

for i in range(N):
    for j in range(i):
        if A[i]%A[j] == 0:
            s += 1
            break

s += len(B)

print(N-s)

Submission status: Wrong Answer

Solution code:
def input_int():
    return map(int, input().split())

def one_int():
    return int(input())

def one_str():
    return input()

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

import bisect

N=one_int()

As = many_int()

def hoge(As, N):
    same = -1 if len(set(As))==1 else 0
    As = sorted(As)
    count=0
    for a in As:
        ind = bisect.bisect_left(As, a//2 + 1)

        flg=True
        for b in As[:ind]:
            if a%b==0:
                flg=False
                break
        if flg:
            count+=1

    print(count+same)
hoge(As, N)

Submission status: Wrong Answer

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

print(ans)

Submission status: Wrong Answer

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

if len(A)==1:
    print(0)
else:
    for i, b in enumerate(A):
        if i==0:
            s.add(b)
            continue
        else:
            t = 1
            for j in range(2, int(b**0.5)+1):
                while b%j==0:
                    b //= j
                    t *= j
                    if t in s:
                        ans -= 1
                        break
                if not b:
                    break
            s.add(b)

    print(ans)

Submission status: Wrong Answer

Solution code:
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

  
n = int(input())
a_list = list(sorted(list(map(int,input().split()))))
sosuu = []
hukusuu = []

for i in range(len(a_list)-1,0,-1):
  if a_list[i] == a_list[i-1]:
    hukusuu.append(i)
    hukusuu.append(i-1)
    
hukusuu = sorted(list(set(hukusuu)),reverse=True)
for i in hukusuu:
  a_list.pop(i)

if len(a_list) == 0:
  print(0)
else:
  for i in range(len(a_list)-1,-1):
    if len(factorization(a_list[i])) == 1:
      sosuu.append(a_list[i])
      a_list.pop(i)
  while len(a_list) != 0:
    num = a_list.pop()
    iranai = False
    for i in sosuu:
      if num % i == 0:
        iranai = True
        break
    if iranai == False:
      sosuu.append(num)

  print(len(sosuu))

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
a = Counter(map(int, input().split()))
ans = n
for num, count in a.items():
    if count > 1:
        ans -= count
        continue
    if 1 in a:
        ans -= 1
        continue
    i = 2
    while i * i <= num:
        if num % i == 0:
            if i in a or (num // i) in a:
                ans -= 1
                break
        i += 1
print(ans)

Submission status: Wrong Answer

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

ans = 0
for i in range(1,n):
    v = a[0:i-1]
    for itm in v:
        if int(a[i]/2) < itm:
            break
        
        if a[i] % itm == 0:
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))

from collections import Counter

n = ii()
A = iil()
di = Counter(A)
A.sort()

ans = 0
l = set()
for item in A:
    if di[item] > 1:
        if item not in l:
            for i in range(1,1000000//item):
                l.add(item*i)
        continue
    if item not in l:
        for i in range(1,1000000//item):
            l.add(item*i)
        ans += 1
print(ans)

Submission status: Wrong Answer

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

cnt = 0

while cnt < len(A):
  div = A[cnt]
  for l in range(cnt):
    if div%A[l] == 0:
      continue
  delete_index = []
  for k in range(cnt+1, len(A)):
    amari = A[k] % div
    if amari == 0:
      delete_index.append(k)
  for j in sorted(delete_index, reverse=True):
    A.pop(j)
  cnt += 1

if len(A)==1 and A[0]==first:
  print(0)
else:
  print(len(A))

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):
    B = copy.copy(A)
    B[i] = 0
    setA = set(B)
    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:
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:
        if c[1] == 1:
            print(1)
        else:
            print(0)
    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())
l=list(map(int,input().split()))

d={}
for i in range(n):
  if l[i] not in d:
    d[l[i]]=1
  else:
    d[l[i]]+=1
l=set(l)
l=list(l)
l.sort()
n=len(l)
ct=0
if n>1 and d[l[0]]==1:
  #print("*")
  ct=1
elif n==1 and d[l[0]]==1:
  ct=1
for i in range(1,n):
  flag=0
  for j in range(i):
    if l[i]%l[j]==0:
      flag=1
      break
  #print(flag,l[i])
  if flag==0:
    ct+=d[l[i]]

print(ct)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
INF = float('inf')
from collections import defaultdict
dic = defaultdict(lambda:INF)

used = defaultdict(lambda:0)
remove = defaultdict(lambda:0)

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

cnt1 = a.count(1)
if cnt1 == 1:
    print(1)
    exit()
elif cnt1 >1:
    print(0)
    exit()

from collections import Counter
def prime_factorize(n):
    d = Counter()
    m = 2
    while m*m <= n:
        while n%m == 0:
            n //= m
            d[m] += 1
        m += 1
    if n > 1:
        d[n] += 1
    return d

for aa in a:
    if used[aa]:
        remove[aa]=1
        continue
    c = prime_factorize(aa)
    flg = True
    for k in c.keys():
        if dic[k] == INF:
            dic[k] = aa//k
        else:
            if dic[k] > aa//k:
                dic[k] = aa//k
            elif (aa//k)%dic[k]==0:
                flg = False

    if flg:
        used[aa]=1

ans = sum(list(used.values()))-sum(list((remove.values())))
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
N = int(input())
a = [int(y) for y in input().split()]
a.sort()

cnt = 0
c = collections.Counter(a)
for i in c.values():
    if i > 1:
        cnt -= 1

while len(a) > 0:
    b = []
    res = a[0]

    for i in range(1, len(a)):
        if a[i] % res != 0:
            b.append(a[i])
    
    d = len(a)
    a = b
    cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys

stdin = sys.stdin
ns = lambda: stdin.readline().rstrip() # ignore trailing spaces
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))


def BinarySearch(num, List):
    if len(List) == 0:
        print("Erorr : list has no element")
        return
    left,right = 0,len(List)
    while left < right:
        mid  = (left+right)//2
        if num < List[mid]:#
            right = mid
        else:
            left = mid + 1
    return right


def main():
    ans = 0
    n = ni()
    atmp = sorted(na())
    a = [atmp[0]]
    flag = 0
    pre = atmp[0]
    if n > 1 and atmp[0] == atmp[1]:
        ans -= 1
        flag = 1
    for i in range(1, n):
        if pre != atmp[i]:
            a += [atmp[i]]
            pre = atmp[i]
            flag = 0
        elif flag == 0:
            ans -= 1
            flag = 1
    n = len(a)
    asub = [i for i in a]

    for i in range(n):
        ai = a[i]
        if ai != -1:
            ans += 1
            cnt = 2
            right = i
            while right != n:
                right = BinarySearch(ai*cnt, asub)
                if a[right-1] == ai*cnt:
                    a[right-1] = -1
                cnt += 1
    print(max(0,ans))
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
dup = [x for x in set(a) if a.count(x) > 1]
a = list(set(a))
for i in dup:
    a.remove(i)
a.sort()



if 1 in a:
    print(1)
    exit()
if a == []:
    print(0)
    exit()
c = 0
sosuu = []
for i in range(len(a)):
    for j in range(i):
        # print(i , j,"a[i] % a[j]" , a[i] ,a[j]  )
        if a[i] % a[j] == 0:
            # print("!!!!!!!!!!!!")
            break
        if i == j+1:
            c+=1
print(c+1)

Submission status: Wrong Answer

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))

n = I()
l = LI()
list.sort(l, reverse=True)
c = 0
for a in range(n):
  for b in l[a+1:]:
    if l[a] % b == 0:
      break
  else:
    c += 1
  
print(c)

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:
        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:
# Contest No.: ABC170
# Problem No.: D
# Solver:      JEMINI
# Date:        20200614


##### FAST INPUT #####
import os
import sys
from io import BytesIO, IOBase

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
##### END OF FAST INPUT #####
#import sys
import heapq

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

    for i in range(n):
        if not checkList[i]:
                continue
        for j in range(i + 1, n):
            if nums[j] == nums[i]:
                checkList[i] = False
                checkList[j] = False
            if nums[i] * 2 > nums[j]:
                continue

            if nums[j] % nums[i] == 0:
                checkList[j] = False
        #print(nums)
        #print(checkList)
    print(sum(checkList))


    
    return

if __name__ == "__main__":
    main()